There are \(16\) cities in the kingdom. We would like to build roads between these cities so that one can get from any city to any other without passing through more than one city on the way. To save cost, we would like to have no more than four roads coming out of each city. Prove that such a system of roads is unfortunately impossible to build.
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.
There are \(6\) points in three dimensional space. To connect some of the points we draw \(10\) segments. Show that there is at least one fully drawn triangle (with all vertices and sides).