Houses on a Farm

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?

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.

Game of Coins

Kuku and Pipi decide to play a game. They arrange 50 coins in a line on the table, with various nominations. Then alternating, each player takes on his turn one of the two coins at the end of the line and keeps it. Kuku and Pipi continue doing this, until after the 50th move all coins are taken. Prove that whoever starts first can always collect coins with at least as much value as his opponent.

Let’s assume Kuku starts first. In the beginning, he calculates the total value of the coins placed on odd positions in the line and compares it with the total value of the coins placed on even positions in the line. If the former has a bigger total value, then on every turn he takes the end coin which was placed on odd position initially. If the latter has bigger value, then on every turn he takes the end coin which was placed on even position initially. It is easy to see that he can always do this because after each of Pipi’s turns there will be one “odd” coin and one “even” coin at the ends of the line.

Normal Person

I caused my mother’s death and didn’t get convicted.
I married 100 women and never got divorced.
I got born before my father, but I am considered perfectly normal?

Who am I?

A priest, whose mother dies from labor, who marries 100 women to 100 men, and whose father attends his birth.

Crashing Light Bulbs

You are living in a 100-floor apartment block. You know that there is one floor in the block, such that if you drop a light bulb from there or anywhere higher, it will crash upon hitting the ground. If you drop a light bulb from any floor underneath it however, the light bulb will remain intact. If you have two light bulbs at your disposal, how many drop attempts do you need such that you can surely find which the floor in question is?

The answer is 14 drops. You can do this by throwing the first bulb from floors 14, 27, 39, 50, 60, 69, 77, 84, 90, 95, 99, 100 (notice that the difference decreases always by 1) until it crashes and then start throwing the second bulb from the floors in between. For example, if the first bulb crashes at floor 69, you start throwing the second bulb from floors 61, 62, 63, etc. This way the total number of throws would be always at most 14.

Proving that 14 is optimal is done using the same logic. In order to use at most 13 throws, the first throw should be made from floor 13 or lower. The second throw should be made from floor 13+12 or lower, the third throw should be made from floor 13+12+11 or lower, etc. Continuing with the same argument, we conclude that the 13th drop should be made from floor 13+12+…+2+1=91 or lower. However, if the first light bulb does not crash after the last throw, you will not be able to find out which number among 92-100 is X.

The Majority Name

In a long list of names, one of the names appears more than half of the time. You will be read the names one at a time, without knowing how many they are, and without being able to write them down. If you have a very weak memory, how can you figure out which is the majority name?

Remember the first name and then keep track of whether it has been repeated more than half of the time. To do that, simply add 1 if you hear the name or subtract one when you hear another name. If the list finishes and your counter is positive, then the first name is the majority. If your counter drops to 0, simply restart the procedure with the next name you hear.

This algorithm, invented by R. Boyer and J. Moore, works, because if the counter ends up at 0, then each of the names up to that moment has been read at most half of the time. Therefore, the majority name appears more than half of the time in the remainder of the list.