# Problems And Puzzles

Some of these are very simple, some are not so simple, some are just jokes.

1. (from Adam Wasserman)

What is the degree of the highest exponent of K when you complete the operation:

` (K-A)(K-B)(K-C)...(K-Y)(K-Z) `

[solution]

2. (from Ilya Sharapov)

Prove that for any integer `n` the number `[(2+sqrt(3))n]` is odd. (`[x]` is the integer part of `x`)

[solution]

3. 2 kids, John and Jim, are running on an escalator (a moving stairway). John is running three times as fast as Jim, and by the time they are off the escalator, John has stepped on 75 stairs while Jim has stepped on 50 stairs. How many stairs does the escalator have? How is its speed related to the speed of the boys? Were they running with or against the escalator?

[solution]

4. Consider a sequence of `n+1` integers `a0, a1, ..., an` such that `ak=#{j|aj=k}`. I.e., `a0` is the number of zeros in the sequence, while `a20` in the number of 20-ies in it. E.g., the sequence of length 4 `[1;2;1;0]` satisfies the condition: these is only one zero there, so `a0=1`, there are two ones, so `a1=2`, there is one two, so `a2=1`, and there are no threes, so `a3=0`. Describe all such sequences.

[solution]

5. (from Bruno Haible)

Prove that for any positive integer n, the finite product
`prod (1 <= k <= floor(n/2), 3 + 2 cos (2 k pi / n))`
is a rational number.

[solution]

6. Is it possible to split the unit segment `I=[0;1]` into two "uniformly same-size" subsets `A` and `I-A`, i.e., so that any subsegment `J=[a;b]` of `I` would intersect `A` and `I-A` on sets of the same Lebesgue measure? (If you don't know what "Lebesgue measure" is, don't worry - it's just a generalization of the ordinary length to "bad" sets).

[solution]

7. 2 pedestrians have one bike. They travel as follows: the first one rides the bike for some time, then drops it and continues walking in the same direction, while the second follows him by foot. Eventually, the second one finds the bike and rides it until he overtakes the first one. Then he gives the bike to the first one etc. Assuming that they walk with the same speed and bike faster than they walk, what is the speed of their travel?

[solution]

8. (from Eli Minkov)

Prove that for any quadrilateral with sides `a`, `b`, `c` and `d` and area `S`, the following inequality holds: ```ac+bd >= S``` (when does the inequality turns into equality?)

[solution]

9. Prove that all rectangles circumscribed around a given ellipse have the same diagonal. Generalize.

[solution]

10. N cars, each having a different speed, are going along a 1-lane road, so no passing is possible. Eventually, the cars will accumulate in packets, with the "fast" cars tailgating the "slow" ones. E.g., if the initial order was 1,5,2,4,3 (1 being the slowest, 5 being the fastest), we will end up with 3 packets: {1}, {5,2} and {4,3}. Find the average number of packets as a function of N.

[solution]

11. A lady is locked in a dungeon, while the vile monster went to get firewood. When the monster is back in 15 min, he will cook and eat the lady. The lock is an advanced coded one: it has 4 oriented (top/bottom) spikes in a drum, arranged in a square and invisible. The lady can put her two hands into the drum, feel 2 of the spikes (adjacent or diagonal), determine their orientation and change it as she wishes. If all 4 spikes end up the same direction (up or down), the lock opens and she can escape. If not, the drum rotates quickly for 1 min (so that she does not know which spikes she touched), then stops and she can try again. Can she escape? How?

[solution]

12. A parabola `y=x2` was drawn, then the coordinate axes were erased. Restore the axes with a compass and a ruler.

This problem was given during the Moscow State University Faculty of Mechanics and Mathematics entrance oral mathematics examination to a Jew, a graduate of my high school, in the Summer 1988 (3 years into "perestrojka"). The guy could not do the problem in the 15-20 minutes allowed, so his two examiners failed him. He went home and consulted a friend of his (a specialist on the matters related to the admission process), and was advised that the problem is unsolvable. So the poor chap went back to appeal his failing grade (one could appeal on the day of the exam only). He found his two tormenters and told them that the problem had no solution. They said it did. He asked them to provide it. They said "this is an appeal hearing, not a consultation" (the usual answer to such a question). He said: "do you know the solution?" They said: "yes, of course." He said: "which one of you does?" They looked at each other and changed his grade from failing to passing, so he was admitted to the University.

[solution]

13. Draw the tangent to a circle at a given point using only a ruler (no compass).

[solution]

14. You are at a computer store which sells 3 computers: the Japanese one, which always answers any Yes-or-No question correctly, the Chinese one, which always answers any Yes-or-No question IN-correctly, and a Russian one, which sometimes tells the truth and sometimes lies - you never know. You can ask one Yes-or-No question to any one of the three computers, after which you must buy any one of the three. You don't want the Russian computer, but each of the other two is okay. What can you do?

[solution]

15. You have 12 coins, one of which is counterfeit (lighter or heavier than the others - you do not know that), and a scales which lets you compare the weights of any two sets of coins. You may use the scales 3 times. Determine which coin is counterfeit and whether it is heavier or lighter than the true ones.

[solution]

16. Given a plane in the 3D space and 2 points on the different sides of the plane, find the spere passing through the two points which minimizes the area of its intersection with the plane.

[solution]

17. A family of 4 is trying to cross a bridge at night. One needs a flashlight to cross the bridge, and only two persons can cross the bridge at the same time, moving at the speed of the slower of the two. Father crosses the bridge in 1 minute, Mother in 2 minutes, Child in 5 minutes and Granny in 10. What is the fastest way for them to cross the bridge?

The obvious solution is for `F` to always carry the flashlight back, i.e., `FM+F+FC+F+FG` which means 19 minutes (the notation means: first, `F` and `M` cross, then `F` carries the flashlight back, third, `F` and `C` cross together, fourth, `F` carries the flashlight back again, finally, `F` and `G` cross). Can you do faster?

It is alleged that this is the standard problem given at an interview at Microsoft.

[solution]

18. You have two 4-minute fuses. They are not homogeneous, i.e., one half will not burn for 2 minutes. Can you measure a 3 minute interval with these 2 cords?

[solution]

19. You are on top of a 40 meter high building, you have a 30 meter long rope, and you may not jump or fall. There are no windows or doors, the only way down is along the flat wall with a single solid ring at midpoint (20 meters from both roof and ground), to which you can attach your rope. You can cut and tie the rope as much as you like, disregard the length of the rope you spend on knots. Can you get to the ground?

[solution]

20. You have to send a diamond over the mail. The post office sells boxes of all sizes equipped with multiple latches, as well as locks and keys (you can duplicate keys, and you can put more then one lock on the same box). The boxes cannot be broken, so the recepient must have a key to open the box. A key cannot be sent outside of a box, and an unlocked box cannot be mailed. How can you send the valuable diamond?

[solution]

21. The following short quiz consists of 4 questions and tells whether you are qualified to be a "manager".
1. How do you put a giraffe into a refrigerator?
2. How do you put an elephant into a refrigerator?
3. The Lion King is hosting an animal conference, all the animals attend except one. Which animal does not attend?
4. There is a river you must cross, but it is inhabited by crocodiles, and there is no bridge. How do you manage it?

[solution]

22. 4 slugs are moving along 4 straight lines at constant speeds. None of the lines are parallel and no 3 of them pass through the same point (so called general configuration). Slug `A` meets `B` where their respective lines intersect. The same holds for `A` and `C`, `A` and `D`, `B` and `C`, `B` and `D`. Prove that `C` and `D` also meet where their lines intersect.

[solution]

23. (from Tanya Khovanova)

Two people are playing heads and tails, one casts `n` coins, the other - `n+1`. What is the probability that the second one will have (strictly) more heads than the first one?

[solution]

24. A row of freshly recruited soldiers is standing before a sergeant who gives a command to turn right. Some soldiers turn right, some left, and then they try to correct their mistake: if a soldier sees the face of his neighbor, he assumes that he turned the wrong way and turns around. Will the situation stabilize and how? How long will it take?

[solution]

25. (from Boris Korsunsky)

What is acceleration (or, if you prefer, deceleration) of a tennis ball, dropped from a significant height, right after it bounced from the pavement?

[solution]

26. [added: 2000-07-05] (from Raffaello Giulietti)

There are two mathematicians in a room. The product of two integers `>=2` is given to the first mathematician, and the sum of the same two integers is given to the second one. Hence, the first mathematician only knows the product and the second only knows the sum of the two integers. However, both are aware that the first knows the product and the second knows the sum of the two integers.

• The first mathematician is asked whether he can determine the two numbers, and he answers no.
• The second mathematician is then asked whether he can determine the two numbers, and he too answers no.
• The first mathematician is then asked once again whether he can determine the two numbers and this time the answer is yes!
What are these two numbers?

[solution]

27. [added: 2000-11-26] A couple is determined to have at least one son and at least one daughter. What is the expected total number of children they will have?

[solution]

You have two (2) identical glass balls and a 100-storey building. If you drop such a ball from the a certain floor, it might break (obviously, if it breaks when dropped from the `i`th floor, it will also break when dropped from all floors above it. You have to find such a floor that the balls do not break when dropped from the floors below it, but do break when dropped from it and floors above it. You may expend both balls. What is the minimum number of drops you will have to make?

[solution]

29. [added: 2001-10-02] (from Sergey Kagan)

There are 1000 lockers (all locked) and 1000 kids, who lock the unlocked lockers and unlock the locked ones. The first kid touches (i.e., opens) each locker. The second kid touches (i.e., locks) all even lockers. The third kid touches (i.e., opens the locked ones and closes the unlocked ones) all lockers with number divisible by 3. The fourth kid touches the lockers number 4, 8, 12 etc. After the 1000th kid locks (or unlocks, if it was locked already) the locker number 1000, how many lockers are open?

[solution]

3 dark corridors (of the same length) meet in a small room. A cop is trying to catch a bum there. The cop runs with speed 2 meters per secons, while the bum can only make one meter per second. The cop has a weak flashlight - it lights only 1 meter of space. What is the maximum corridor length for which the cop has a winning strategy against the bum? E.g. if all the corridors are just 1 meter, then the cop will stand in the room, light the corridors one after another and catch the bum.

[solution]

31. [added: 2002-05-23] (from Bruno Haible)

For all integers numbers `m`,

``` ((m - 1) & (- m - 1)) + 1 == m & -m ```

[solution]

32. [added: 2002-07-02] (from TAOCP)

Let `X` and `Y` be two independent, identically distributed random variables with zero mean, which are more likely to be positive than to be negative. Obviously, their sum `X+Y` also has zero mean, but is it necessarily more likely to be positive than to be negative?

[solution]

33. [added: 2002-07-02] (from Mikhail Khmelnitskiy)

A stupid king decided to eliminate his Academy of Sciences (as a cost-saving measure, after he slashed taxes), and decided to do it as follows: all the scholars are put in one line, one after another, so that the first one sees everyone ahead of him (second through last), while the second sees the third scholar through the last one, and the last one does not see anyone. Then he puts a dunce cap, either red or blue, on each scholar's head, so that the first one knows the cap colors of rest of them, but not his own, the second knows the cap colors of the third through the last one etc. Finally, each scholar, starting with the first one, is asked what color his cap is, and if his guess (which all the other scholars hear) is wrong, he is executed. The scholars may agree in advance on what to do.

What should the scholars do to minimize the casualties?

E.g., they can agree that each odd-numbered scholar will say the cap color of the next one, so that the even-numbered scholars will survive. Can they do better than that?

[solution]

34. [added: 2005-07-26] (from Tanya Khovanova)

A bum makes 1 cigarette out of 4 cigarette butts. He has 24 cigarette butts. How many cigarettes can he smoke?

[solution]

An ellipse without any markings (no center, no foci, no axes) is drawn. Restore the center, foci and axes and draw the tangent to the ellipse though a given point on (or off) it using a compass and a ruler.

[solution]

An urn contains `N` black and white balls, and we do not know how many balls of each kind there is: `Pr(#white=K)=1/(N+1)` for `K=0,...,N`. The urn was sampled (with replacement) `M` times and every time the ball was while. What is the posterior probability that all balls in the urn are white?

[solution]

Placed on a 1 meter long horizontal bar, an ant moving with a speed of 1 m/s, will fall off one end in at most 1 second. When two ants run into each other, they both turn around and keep running with the same speed. Suppose 1000 ants are placed on the bar arbitrarily and start running in arbitrary directions. How long will it take them all to fall off the bar ends? Assume that ants have zero size.

[solution]

This is a ramification of a previous problem.

Suppose there are countably infinitely many scolars, and all of them can see all the others (except for oneself). They are asked all at once, i.e., they do not hear the answers of the others. They win if only finitely many of them are wrong (alternatively: if either all are wrong or all are correct).

Prove that they have a winning strategy.

[solution]

39. [added: 2009-12-29] (from jourfixe)

An equilateral triangle is inscribed in a right triangle so that one of its sides is parallel to the hypotenuse. Then everything except for the hypotenuse and the vertexes on it are erased.

Restore the full picture using a compass and a ruler.

[solution]

40. [added: 2014-05-28] (from МГУ via Tanya Khovanova)
1. There are two 6-sided dice with numbers 1 through 6 on their faces. Is it possible to "load" the dice so that when the two dice are thrown the sum of the numbers on the dice are distributed uniformly on the set `{2,...,12}`? By loading the dice we mean assigning probabilities to each side of the dice. You do not have to "load" both dice the same way.
2. Students who are trying to solve a problem are seated on one side of an infinite table. The probability that a student can solve the problem independently is 1/2. In addition, each student will be able to peek into the work of his or her right and left neighbor with a probability of 1/4 for each. All these events are independent. Assume that if student X gets a solution by solving or copying, then the students who had been able to peek into the work of student X will also get the solution. Find the probability that a specific student gets the solution.

[solution]

41. [added: 2014-09-30] (from Trevor Zablocki)

A man has 1000 barrels of wine that he wants to use in 1 day. 1 barrel is poisoned. He has 10 plants which will die in 1 day if watered by the poisoned wine. How can he determine which barrel is poisoned?

[solution]

Drop me a note with your favorite puzzle!

If you are too lazy to do the problems yourself, you can read the notes and answers.