Puzzles 1

Puzzles Csaba Bir´o 1. In a TV-quiz, a player has an option to choose one of three doors. Behind two doors there is a goat (or something of little worth) and behind the third one there is a car – the player wins the item behind the door. After the player chooses one of the doors, the quiz-master opens one door out of the two unchosen, behind which there is a goat. Then the player has the opportunity to change her mind and switch to the other closed door or hang on to her first decision. Is it worth it to change? 2. Prove, that if you write down the numbers, 1,2,...,101 in an arbitary order, you can pick 11 numbers that make a monotonous sequence if they are considered in the order they were written down. 3. Prove, the following: In a party, where 6 people participate, there must be 3 people who know each other, or 3 people who don’t know each other. 4. In a village, there are n wives who know each other. All of them know a rumor. If one sends a letter to another one she writes about every rumor she knows. At least how many letters must be sent to get every wife to know every rumor. 5. In a village, there are n wives who know each other. All of them know a rumor. If one calls another one over the telephone, they can share every rumor they know. At least how many calls are necessary to get every wife to know every rumor. Remark: This exercise is much harder than the previous one. 6. There is a village where 100 couples live. Every husband knows about every wife if she cheats on her husband, except about his own wife. There is an ancient tradition in the city: if a husband finds out that her wife cheats on him, he shall throw her into the creek in the following morning. One day, a wanderer arrives in the village. After a few discussions with the men in the village, he calls the men together and states: “There is a woman in the village who cheats on her husband.” Nothing happens after the first 99 mornings. What will happen on the 100th morning? 7. The previous puzzle is not very difficult, so I disclose the solution. If you don’t want to know it, stop reading here and skip this puzzle. You can return to it after you solved the previous one, or gave up thinking on it. 1

In the 100th morning, every wife will be thrown into the creek, because then every husband finds out that his wife cheats on him. The interesting thing is that the wanderer stated something that had been known by every husband. How is it possible then, that this statement started this process? 8. There are n people who shall solve a puzzle. They are aligned in a straight line and then a cap is put on everyone’s head. They can see all the caps on people in front of them, but they can’t see their own cap and the caps on people behind them. Starting from the front of the line they have to guess the color of their own cap. Their common aim is to find out as many colors as possible. Before they are aligned, they have the opportunity to develope a strategy to use. What is the best strategy (i. e. the strategy that provides the maximum number of caps guessed in the worst case)? 9. Three guys, call them A, B and C fight a duel. They stand in the vertices of an equilateral triangle and shoot to each other. A is a bad shooter, he hits once out of three on average; B is much better: he hits twice out of three and C is the best: all of his shoots hit! A starts the duel, then B will fire and then C and then A again, until only one man is alive. What is the best strategy for A? 10. There are n prisoners in a jail. The guards call them together and tell them that they will be carried sometimes to the yard of the jail (one at a time) for a walk. They won’t know the frequency of walks. They will be carried out randomly, so it is possible that somebody will be carried out several times while another prisoner won’t have been carried out at all till that time. On the yard there is a switch that has 2 states: call them 0 and 1. When a prisoner is carried out for a walk, he can recognize the state of the switch, and he has the opportunity to change the state. They don’t know the initial state of the switch. If a prisoner sometimes says to the guard: “We all have been carried out at least once.” and he is right, the prisoners will be released. But if he is wrong, they will be kept in jail for life. They have the opportunity to to develope a strategy to use. Find a strategy for them! 11. A wanderer approaches a crossroads where 4 people stands. Two of them are honest: they always tell the truth, and the other two are capricious: they sometimes tell the truth, sometimes tell a lie, sometimes they don’t listen to the question. The wanderer wants to know which is the right way to her destination. At least how many questions does she need to ask to find the right way? 12. There is couple, the wife has brown eyes, the husband has blue eyes. The the wife’s parents both have brown eyes, but the wife’s sister has blue eyes. Denote ξ the random variable that shows how many children they have had when their first blue-eyed child is born. For any k positive integer, calculate P(ξ = k).

2

Remark: The answer is obviously not independent of k. (Because then P ∞ k=1 P(ξ = k) ≤ 1 would imply P(ξ = k) ≡ 0.) This is the beauty of the exercise: the eye colors of the first few kids affect the probabilities of the eye colors of the following children. 13. Sinbad, the sailor saves the sultan, and the sultan is so grateful, that he offers a lady of his harem to Sinbad. Sinbad can choose one of the lady in the following way: the ladies come into the room, one after the other, and for each one Sinbad has to decide if he wants to spend the night with her or not. If he says “yes”, the procedure ends and he has no opportunity to change his mind. If he says “no”, the lady goes away and he has no opportunity to choose that lady later. He knows the number of ladies. At the last one, he must choose that one. Sinbad wants to choose the most beautiful lady of the harem; that would be the only success for him. For any two ladies, he can decide which is the more beautiful. What is the optimal strategy for Sinbad? 14. There are 12 bastions on a wall of a fortress, and a watchman in each bastion. You don’t know neither the shape of the wall nor the distribution of the bastions on the wall. At midnight, every watchman starts from his bastion in a direction on the wall. Every watchman proceeds at constant speed, so that he would walk around the wall in 1 hour. When two watchmen meet, both turn back. They go through a bastion without any delay. Prove that at noon, every watchman arrives to his original bastion. 15. A death-row prisoner is said to be executed on the next week. They say that he will not know the day of execution before the morning of the execution. He is thinking in the following way: “I can’t be executed on Sunday, because if I won’t be executed till Saturday night, then I will learn the day before Sunday morning. So I must be executed on a day from Monday to Saturday. But in this case, I can’t be executed on Saturday, because then on Friday night I will know the day, because I’ve already excluded Sunday. So I must be executed on a day from Monday to Friday. But in this case I can’t be executed on Friday, and so on, I can’t be executed on Thursday, Wednesday and Tuesday. So I will be executed on Monday. But it is also impossible, because then I know the day now.” Is the prisoner right? 16. Merlin, King Arthur’s magician is different from other people, because he is able to think over finite cases in 0 time (that is why he is called a magician). There are 100 ladies-in-waiting and 100 knights in the royal court, and one day King Arthur decides to marry the ladies to the knights. He asks the ladies to choose; he asks them to write the names of the knights on a paper whom they are willing to marry. Then he gives the papers to Merlin and commands him to make pairs. 3

Merlin is able to find every possible matching in 0 time, and he quickly realizes that there is no proper matching. So he tells it to King Arthur. But King Arthur feels suspicious about Merlin that he was too lazy to find a matching and he just wants to get away from the work in this way. So he commands Merlin to show him why there is no matching, so that Arthur could check the reason in a second; otherwise he has Merlin beheaded. For example, if Merlin could show a lady, who hasn’t written down any names, it is a good reason for the non-existence of a proper matching. Can Merlin escape from beheading? 17. In a tipical class (30 students) what is the probability that there are two people, who were born in the same day of year? 18. Imagine the following machine. There are twelve drums, all are cylindrical with one ellastic membrane as one of its circular plane. Stick a lead cube to the membrane, inside the drum. If the drum stands vertically with the membrane up, the membrane would be concave. If the membrane is down, it would be convex. Now stick all the drums on a wheel in the same direction and put the machine into water.

The drums on the left have less volume, so they displace less water, therefore the buoyancy acting on the left drums is less than the bouyancy acting on the right drums. So the wheel starts to turn counterclockwise, and since the membranes change their shape, the wheel is continuously turning around (moreover, it is accelarating). You only have to gain the 4

energy from the axle! We invented a perpeetum mobile! What is the error? (Don’t shoo off the problem with an easy argument about different pressure, friction, or something like these. Most of these arguments can be refuted by taking larger or smaller wheel, or drums, etc.) 19. There are three prisoners in a jail, and they are said that two of them will be executed on the following day, but they don’t know who. One of the prisoners goes to the guard and tells him: “One prisoner of the other two will be executed (maybe both). Please tell me one of their names, who will be executed. You don’t disclose any secret, because I already know that one of them will be executed.” The guard tells him a name, and asks him why he wanted to know it. “Because before I knew it, I knew that the probability that I would be executed was 2/3. Now there are only two possibilities, so the probability has decreased to 1/2.” Is he right? 20. A sports club organizes a tabletennis tournament. The tournament is divided into rounds. If there are 2k or 2k + 1 competitors in a round, the organizers draw k pairs who play against each other; the winner gets into the next round, the looser is out. The one, who doesn’t have a pair, because there is odd number of competitors in that round, gets into the next round automatically. In the first round, every competitor takes part, and the tournament lasts until in the last round there is only one competitor – the winner. How many games will be played, if the number of participants is n? 21. We will show, that 90◦ = 91◦ . Let AB be a straight line with end points A and B. Let AC be a straight line perpendicular to AB, and let BD be a straith line so that the length of BD is equal to the length of AC and the angle DBA is of 91◦ . We will show that the angle CAB is equal to the angle DBA. Draw a line through C and D. Let e and f be the perpendicular normal bisector of CD and AB respectively. Let I be the intersection of e and f . See the diagram below. (The diagram is intentionally distorted to make the difference between the two angles obvious.)

5

The length of AC equals the length of BD, because of the choice of BD. The length of AI equals the length of BI, because f is a perpendicular normal bisector. The length of CI equals the length of DI, because e is a perpendicular normal bisector. So the triangles ACI and BDI are congruent. That means that the angle CAI equals the angle DBI. And since ABI is an isosceles triangle, the angles IAB and IBA are also equal, therefore the angle CAB is equal to the angle DBA. What is the error in the proof? 22. On a cyclic road there are n gas stations. The total amount of gas in the gas stations is strictly enough to go around the cyclic road. You have a car with no gas. Prove, that there exists a gas station from which you can go around the road clockwise. 23. There is game played on a circular table with quarters. In each turn, both players put a quarter on the table, one after the other, so that the quarters should not overlap. The player, who cannot move (who has no space to put the coin on the table) looses. Describe a winning strategy! 24. Give the most simple form of the product (x − a)(x − b)(x − c)(x − d) · · · (x − z)

6

25. Is that true, that for any two irrational numbers a and b, the power ab is irrational? 26. Draw a circle and pick n points on it. Now join every point to every other point and suppose that the points have been picked so that no 3 chords go through one point (i. e. every intersection is the intersection of exactly 2 chords). How many domains are generated? Remark: If you found that the solution is 2n−1 , try n = 6. 27. John has 20 dollars and he wants to have 40. He goes into a casino and stops at the roulette. He is thinking about choosing a playing startegy, and he has 2 ideas: (a) He places 20 dollars on RED. It pays 1:1; if he wins, he will have 40 dollars, otherwise all his money is gone. (b) In every turn, he places 1 dollar on RED. He stops is he has 40 dollars or if he has lost all his money. (The probalility of that RED wins slightly less than 1/2. In american roulette it is 18/38, in europian it is 18/37.) Which is the better strategy? From this example, can you derive a general hint for gamblers? 28. A company that produces cereal puts coupons to the cereal boxes. There are 5 different coupons, and if you buy a box of cereal, you exactly have the chance 1/5 to get each specific coupon regardless of what kind of coupons you have. If you collect a set of 5 different coupons, you win a prize. Denote ξ the random variable that shows how many boxes you have bought until you collect the complete set. Calculate E(ξ). 29. We will prove that 1 = −1. p √ √ √ 1 = 1 = (−1)(−1) = −1 −1 = i · i = i2 = −1 What is the error? 30. You have a car and you want to cross a desert. You have infinite gas but a finite tank. You can make arbitary stores in the desert. What is the maximum size of desert that you can cross in this way? 31. You have some cards with letters on one side, and numbers on the other side. One of your friends lays the following cards on the table:

7

By turning as few cards as possible, decide if the following statement is true for the cards on the table: “If a card has a vowel on one side, it has an even number on the other side.” Remark: I’m almost sure that you can solve this puzzle, but please rethink it twice, because it is easy to give a wrong solution. Some social psychologists made several experiments with this exercise and logically equivalent ones. It’s quite amazing that they got completely different results from logically equivalent exercises. 32. We will show, that every real number is equal to 0. We know that for any real x, x2 − x 2 = x 2 − x 2 . So x(x − x) = (x + x)(x − x).

Dividing both sides by x − x we get

x = x + x = 2x. This is only possible when x = 0. 33. There is a stick leant against the wall. Its bottom is starting to slip away from the wall, until the stick lies horizontally on the floor. What curve will be described by its midpoint? 34. We cut a circular hole with radius r into a rectangular (and not squared) metal plate. If we heated the plate, would the hole shape be • a circle with radius r,

• a circle with radius < r,

• a circle with radius > r,

• an ellipsis horizontally flattened, • an ellipsis vertically flattened?

35. Consider the following game. You pay some dollars for a round. Then the bank starts to toss a coin until the result is heads. You win 2k−1 dollars, where k is the number of tosses. In other words, if the first toss is heads, you win 1 dollar; if the first is tails and the second is heads, you win 2 dollars; if the first and the second is heads and the third is tails you win 4 dollars, etc. The question is: at most how many dollars can be paid for a round so that the game should not be losing for you? This amount is clearly the expected value of the prize. Let’s calculate it! If ξ is the random variable showing the prize, then E(ξ) =

∞ X i=1

P(the first heads comes out in the ith round) · 2i−1 = 8

=

∞ ∞ X 1 i−1 X 1 = 2 =∞ 2i 2 i=1 i=1

This means that you can pay any money for a round, it will be profitable for you, but no sentient person would pay more than $50 for it! Where is the mistake (if there’s any)? Remark: this famous puzzle is called “paradox of St. Petersburg”. 36. Cut off one squares each from two opposite corners of a regular chessboard. Can this “defective chessboard” be covered with regular 2 × 1 dominoes? 37. There is 5 × 5 chessboard and a ladybug is sitting on every square. Once they start to walk: every ladybug walks to an adjacent square. Is it possible that after this action there will be exactly one ladybug on each square again? 38. A wanderer arrives to a river with his properties: a wolf, a goat and a head of cabbage. He finds a boat but it is too small: only one of his properties can go in after him. If the goat is left alone with the cabbage it eats it, and if the wolf is left alone with the goat it eats it. (If all three are left alone it is undefined if the goat can eat the cabbage before the wolf eats the goat.) How can the wanderer bring them all to the other side without losing any of his properties? 39. At a night, a family consisting of a young boy, his father, mother and his grandmother arrives to a creek with a narrow and weak bridge on it. The bridge is so weak that only two people may stay on it at the same time. They have only one flashlight and it is also needed to walk through the narrow bridge (and they mustn’t throw it, of course). The boy is able to go through the bridge in 1 minute, this lasts 2 minutes for the father, 5 minutes for the mother and 10 minutes for the grandmother. How can they all go to the other side of the creek in 17 minutes? 40. Define the following sequence: a0 = 1 a1 = cos a0 = cos 1 a2 = cos a1 = cos cos a0 = cos cos 1 .. . an = cos an−1 Determine if this sequence converges, and if yes, calculate the limit! Remark: On a regular scientific calculator (which calculates the cosine of the number displayed on the screen immediatelly when you press the “cos” button) you can type “1” and press the “cos” button again and again to see the sequence on the screen. 9

41. A 60 miles long railroad connects two cities. Two trains left the two cities in the same moment and they are heading in the direction of each other at a speed of 60 mph. They will crash in the middlepoint of the railroad. A fly began to fly from the windshield of one of the trains along the railroad when the train left the city. The speed of the fly is 90 mph. When the fly arrives to the windshield of the other train, it immediately turns back and flies back at the same speed to the windshield of the first train, where it turns back again, etc. until it is smashed between the two crashing train. What is the total distance travelled by the fly? 42. A king has his birthday. So he decides to let go some of his prisoners. He actually has 100 prisoners at the moment. They are each in a separate cell, numbered from 1 to 100. Well, he is a high tech king. He can close or open any prison door by a single click on the cell’s number on his royal laptop. When he clicks at a closed door, it opens. When he clicks at an open door, it closes. At the beginning, every door is closed. First the king clicks on every number from 1 to 100 (therefore opening every door). Then he clicks on every second number from 1 to 100, (i.e. 2, 4, 6, 8, 10,...). Then he clicks on every third number. And so on. Finally, he only clicks on the number 100. Then he orders that the prisoners that find their doors open may go free. Who gets to go and who has to stay? Remark: A surprisingly frequent wrong answer is that the prisoners with prime numbered cells will be free.

Acknowledgements Many of these puzzles are widely known but I heard a number of them from my teachers, colleagues or gathered them from books, internet, etc. I try to list those people who were important sources of these exercises. So I want to say thank you to Lajos P´ osa, Ray Smullian, J´ ozsef Kosztol´ anyi, Istv´ an Vincze, Zolt´ an Kov´ acs, Egmont Koblinger, M´ arta Hideg.

10