Problems

Prove that the following facts are true for any graph:

a) The sum of degrees of all vertices is equal to twice the number of edges (and therefore it is even);

b) The number of vertices of odd degree is even.

A traveller rents a room in an inn for a week and offers the innkeeper a chain of seven silver links as payment – one link per day, with the condition that they will be payed everyday. The innkeeper agrees, with the condition that the traveller can only cut one of the links. How did the traveller manage to pay the innkeeper?

During a chess tournament, some of the players played an odd number of games. Prove that the number of such players is even.

In the rebus in the diagram below, the arithmetic operations are carried out from left to right (even though the brackets are not written).

For example, in the first row "\(** \div 5 + * \times 7 = 4*\)" is the same as "\(((** \div 5) +*) \times 7 = 4*\)". Each number in the last row is the sum of the numbers in the column above it. The result of each \(n\)-th row is equal to the sum of the first four numbers in the \(n\)-th column. All of the numbers in this rebus are non-zero and do not begin with a zero, however they could end with a zero. That is, 10 is allowed but not 01 or 0. Solve the rebus.

Decode this rebus: replace the asterisks with numbers such that the equalities in each row are true and such that each number in the bottom row is equal to the sum of the numbers in the column above it.

48 blacksmiths must shoe 60 horses. Each blacksmith spends 5 minutes on one horseshoe. What is the shortest time they should spend on the work? (Note that a horse can not stand on two legs.)

There are 6 locked suitcases and 6 keys for them. It is not known which keys are for which suitcase. What is the smallest number of attempts do you need in order to open all the suitcases? How many attempts would you need if there are 10 suitcases and keys instead of 6?

A schoolboy told his friend Bob:

“We have thirty-five people in the class. And imagine, each of them is friends with exactly eleven classmates...”

“It cannot be,” Bob, the winner of the mathematical Olympiad, answered immediately. Why did he decide this?

Cowboy Joe was sentenced to death in an electric chair. He knows that out of two electric chairs standing in a special cell, one is defective. In addition, Joe knows that if he sits on this faulty chair, the penalty will not be repeated and he will be pardoned. He also knows that the guard guarding the chairs on every other day tells the truth to every question and on the alternate days he answers incorrectly to every question. The sentenced person is allowed to ask the guard exactly one question, after which it is necessary to choose which electric chair to sit on. What question can Joe ask the guard to find out for sure which chair is faulty?

Harry, Jack and Fred were seated so that Harry could see Jack and Fred, Jack could only see Fred, and Fred could not see anyone. Then, from a bag which contained two white caps and three black caps (the contents of the bag were known to the boys), they took out and each put on a cap of an unknown color, and the other two hats remained in the sack. Harry said that he could not determine the color of his hat. Jack heard Harry’s statement and said that he did not have enough information to determine the color of his hat. Could Fred on the basis of these answers determine the color of his cap?