Prove that a graph with \(n\) vertices, the degree of each of which is at least \(\frac{n-1}{2}\), is connected.
In the Far East, the only type of transport is a carpet-plane. From the capital there are 21 carpet-planes, from the city of Dalny there is one carpet-plane, and from all of the other cities there are 20. Prove that you can fly from the capital to Dalny (possibly with interchanges).
In a country coming out of each city there are 100 roads and from each city it is possible to reach any other. One road was closed for repairs. Prove that even now you can get from every city to any other.
There is a group of islands connected by bridges so that from each island one can get to any of the other islands. The tourist has bypassed all the islands, walking on each bridge exactly once. He visited the island of Three-isle three times. How many bridges are there on Three-isle if the tourist
a) did not start on it and did not finish on it?
b) started on it, but did not finish on it?
c) started on it and finished on it?
a) A piece of wire that is 120 cm long is given. Is it possible, without breaking the wire, to make a cube frame with sides of 10 cm?
b) What is the smallest number of times it will be necessary to break the wire in order to still produce the required frame?
There are three groups of stones: in the first – 10, in the second – 15, in the third – 20. During one turn, you are allowed to split any pile into two smaller ones; the one who cannot make a move loses.
Numbers from 1 to 20 are written in a row. Players take turns placing pluses and minuses between these numbers. After all of the gaps are filled, the result is calculated. If it is even, then the first player wins, if it is odd, then the second player wins. Who won?
Two players take turns to put rooks on a chessboard so that the rooks cannot capture each other. The player who cannot make a move loses.
On a board there are written 10 units and 10 deuces. During a game, one is allowed to erase any two numbers and, if they are the same, write a deuce, and if they are different then they can write a one. If the last digit left on the board is a unit, then the first player won, if it is a deuce then the second player wins.
The numbers 25 and 36 are written on a blackboard. Consider the game with two players where: in one turn, a player is allowed to write another natural number on the board. This number must be the difference between any two of the numbers already written, such that this number does not already appear on the blackboard. The loser is the player who cannot make a move.