In the Padurea forest there are 100 rest stops. There are 1000 trails, each connecting a pair of rest stops. Each trail has some particular level of difficulty with no two trails having the same difficulty. An intrepid hiker, Sendeirismo has decided to spend a vacation by taking a hike consisting of 20 trails of ever increasing difficulty. Can he be sure that it can be done?
He is free to choose the starting rest stop and the 20 trails from a sequence where the start of one trail is the end of a previous one.
SOLUTION
Place one hiker in each of the rest stops. Now, go through the trails in the forest one by one, in increasing difficulty, and every time you pick a trail, let the two hikers in its ends change places. This way the 100 hikers would traverse 2000 trails in total, and therefore one of them would traverse at least 20 trails.
In the country of Bulmenia there are 40 big cities. Each of them is connected with 4 other big cities via paths, and you can get from any city to any other via these paths.
Show that you can create a trip passing through every path exactly once that ends in the city it starts from.
Show that you can create one or multiple trips, such that every trip passes through different cities, ends in the city it starts from, and also every city is part of exactly one trip.
Remark: The paths can intersect each other, but you cannot switch from one path to another midway.
SOLUTION
Let us call a trip that ends in the city it starts from a “loop”. Start from any city and keep traveling without using any path twice. If at some point you can’t continue, stop, creating a loop, and modify your trip as follows. Pick any city you have visited from which there are unused paths going out, and once again start traveling along the unused paths until you can’t continue further. Add the newly formed loop to the original trip and continue this procedure until there are no unused paths left, thus completing a loop passing through every path exactly once. This method works because there is an even number of paths going out from every city and you can get from any city to any other.
Use the loop from 1. and color every second path on it in black. Then, notice that there are 2 black paths going out from every city. Therefore, these black paths create one or multiple disjoint loops passing through every city in Bulmenia exactly once.
Is it possible to connect each of the houses with the well, the barn, and the mill, so that no two connections intersect each other?
SOLUTION
No, it is impossible. Here is a convincing, albeit a informal proof.
Imagine the problem is solvable. Then you can connect House A to the Well, then the Well to House B, then House B to the Barn, then the Barn to House C, then House C to the Mill, and finally the Mill to House A. Thus, you will create one loop with 6 points on it, such that houses and non-houses are alternating along the loop. Now, you must connect Point 1 with Point 4, Point 2 with Point 5, Point 3 with Point 6, such that the three curves do not intersect each other. However, you can see that you can draw no more than one such curve neither on the inside, nor the outside of the loop. Therefore, the task is indeed impossible.
More rigorous, mathematical proof can be made using Euler’s formula for planar graphs. We have that F + V – E = 2, where F is the number of faces, V is the number of vertices, and E is the number of edges in the planar graph. We have V = 6 and E = 9, and therefore F = 5. Since no 2 houses or 2 non-houses can be connected with each other, every face in this graph must have at least 4 sides (edges). Therefore, the total number of sides of all faces must be at least 20. However, this is impossible, since every edge is counted twice as a side and 20/2 > 9.
100 guests go to a party and some of them shake hands with each other. Show that there are two guests who handshake the same number of people.
SOLUTION
Each of the people at the party has shaken hands between 0 and 99 times. However, if someone has shaken hands 0 times (with nobody), it is impossible that another one has shaken hands 99 times (with everybody). Therefore there are at most 98 different options for the number of handshakes at the party, and thus two of the guests have shaken hands the same number of times.
