In the Land of Linguists live \(m\) people, who have opportunity to speak \(n\) languages. Each person knows exactly three languages, and the sets of known languages may be different for different people. It is known that \(k\) is the maximum number of people, any two of whom can talk without interpreters. It turned out that \(11n \leq k \leq m/2\). Prove that then there are at least \(mn\) pairs of people in the country who will not be able to talk without interpreters.
In a graph \(G\), we call a matching any choice of edges in \(G\) in such a way that all vertices have only one edge among chosen connected to them. A perfect matching is a matching which is arranged on all vertices of the graph.
Let \(G\) be a graph with \(2n\) vertices and all the vertices have degree at least \(n\) (the number of edges exiting the vertex). Prove that one can choose a perfect matching in \(G\).
Thirteen boys and girls met to play a football match. Eleven of them shook hands with everybody else in the group. The last two shook hands with everybody else but not each other, because they were siblings and arrived together. How many handshakes took place?
The city of Konigsberg has seven bridges as depicted on the layout below. \[\includegraphics[scale=0.5]{https://problems-static.s3.amazonaws.com/production/task_images/2829/WSP-000146.png}\] Is it possible for the great mathematician Leonard Euler to have an excursion in Konigsberg visiting all islands and land banks, but crossing each bridge exactly once?
There are \(6\) people at a party. Each two people either know each other or not, and the knowledge goes both ways: if \(A\) knows \(B\), then \(B\) knows \(A\). Show that there either is a trio of people who all know each other or a trio of people who all don’t know each other.
An elven village in the woods has \(11\) treehouses. We want to link the houses by ropes so that each house is connected to exactly \(4\) others. How many ropes do we need?
Can you draw a house like the one below without lifting your pen from the paper, nor going over the same edge twice? \[\includegraphics[scale=0.5]{https://problems-static.s3.amazonaws.com/production/task_images/2833/WSP-000149.png}\]
Last week eight heads of state, (3 presidents, 3 prime ministers and 2 emperors), got together for a conference. According to a reporter, each president shook hands with 6 heads of state, each prime minister shook hands with 4, and each emperor with 1. Is this possible?
In the Kingdom of Rabbitland some cities are connected with each other by a railroad. There are two ways of getting from Longears city to Pufftown, one of them passes through an even number of other cities, and the other passes through an odd number of other cities. Show that in the Kingdom of Rabbitland there is a cycle of an odd number of distinct cities, such that each is connected to the next by a railroad, and the last one is connected to the first one by a railroad.
During a chess tournament some people played 5 games and some people played 6. Prove that the number of people who played 5 games is even.