Notes and Answers to the Puzzles

1. [problem] The polynomial has a term `(K-K)`, so it's 0. *grin*

2. [problem] `(2-sqrt(3)) = 1/(2+sqrt(3)) < 1`, and
```(2+sqrt(3))n + (2-sqrt(3))n = 2 * sum (k=0..[(n+1)/2]; Binomial(n,2k)*2(n-2k)*3k)```
-- even!

3. [problem] The answers are: the length is 100 stairs, the boys were running along the escalator which was moving with the same speed as the slow boy. Solution: in the time the fast boy stepped on 75 stairs, the slow one could step on only 25, so, since he stepped on 50, he spent twice as much time on the escalator as the fast one. Therefore his speed relative to the ground was half that of the fast boy, therefore the escalator's speed was the same as the speed of the slow boy, and he counted exactly half the stairs. Another way is to use algebra (omitted).

4. [problem] The answer: The only other examples are `[2;0;2;0]` and `[2;1;2;0;0]`, as well as the family `[n-3;2;1;0...0;1;0;0;0]`. You might find useful the following relationships: `a0+a1+...+an=n+1` and `a1+2a2+3a3+...+nan=n+1`.

5. [problem] This product is actually a Fibonacci number. You can replace "`3`" with another integer and still get an integer product, with a similar recurrent relationship. As a function of this number, this polynomial is closely related to the Tchebyshev polynomials.

6. [problem] It is easy to prove that such a set would not be measurable: its indicator function has an integral of `1/2` of the measure of the set it was integrated on, thus it is `1/2` almost everywhere - a contradiction, It is also easy to construct such a set using so called "nonstandard analysis": just fix an infinite number `Z` and take all numbers that have `1` in the `Z`-th place in their binary representation. This shows how drastically different nonstandard analysis is: to construct a non-measurable set, the conventional analysis needs the full power of Zermelo's `AC` (Axiom of Choice).

7. [problem] The answer is: the harmonic average (the reciprocal of the arithmetic average of the reciprocals) of the walk and bike speeds. This is because both walk and bike equal distances.

8. [problem] The hard way is to recall that, if `l` and `m` are diagonals, `ac+bd >= lm` (equality iff the quadrilateral is inscribed in a circle) and `lm >= S` (equality iff the diagonals are orthogonal).

The easy way is to note that `ab+cd >= S` and flip one of the triangles into which the quadrilateral is split by its diagonal.

9. [problem] An `n`-dimensional ellipsoid is a set `{x|(Ax,x)=1}` for some positive operator `A`. A circumscribed parallelepiped determines a coordinate system `ei`, in which `A` can be represented by a (symmetric) matrix. The diagonal is ```sqrt(sum((vi,ei)2, i=1..n))```, where ```vi=A-1ei/ sqrt((A-1ei,ei))``` is the `i`-th point tangency of the parallelepiped and the ellipsoid. This means that the diagonal is `sqrt(Trace(A-1))` and thus is independent on the coordinate system.

10. [problem] Obviously, for `N=1` the answer is 1. When we add one car which is faster than anything we had before, there is one in `N` chance that it will be in front of the rest and this is the only way the number of packets can be increased. Thus `MN=MN-1+1/N` where `MN` is the `N`-the mean. Therefore `MN=1+1/2+1/3+...+1/N` (which is approximately `ln(N)`).

11. [problem] Yes, and she will have an 11-minute lead on the monster!
The steps are like this:
1. Turn up two diagonal spikes.
2. Turn up two adjacent spikes. Now she is either free or she has 3 up spikes and 1 down spike.
3. Grab two diagonal spikes. If they are opposite, turn the down one up and she is free, otherwise reverse one of them - now two adjacent are up and two are down.
4. Grab two adjacent spikes. If they are co-oriented, reverse both of them and she is free, otherwise reverse both of them anyway - now two diagonal spikes are up and two other diagonal spikes are down.
5. Reverse two diagonal spikes - she is free now!

12. [problem] Parabola has a nice property: the midpoints of all parallel sections lie on a line parallel to the axis. So take any two parallel sections, draw a line through their midpoints, then a section perpendicular to it, then the midpoint perpendicular to that last section will be the `y` axis, while the line perpendicular to it passing through its intersection with the parabola will be the `x` axis.

Note that the property in question was not part of the standard secondary school curriculum in the USSR.

13. [problem] The circle is `S`, the point is `A`. Choose 4 arbitrary points on `S`: `B`, `C`, `E`, and `E`. Draw the 5-pointed star through these 5 points. Let `F` be the intersection of `AD` and `CE` and `G` be the intersection of `AC` and `BD`. Let `H` be the intersection of `EB` ("shoulders") and `FG` ("waist"). Then `AH` is tangent to `S`.

Proof: as usual with ruler-only constructions, we can use an arbitrary projective transformation to simplify the picture. Move the tangent `t` to `S` at `A` to be the line at infinity. Now `S` is a parabola and a simple algebraic exercise will show that `EB` ("shoulders") and `FG` ("waist") are parallel, i.e., that they intersect `t` at the same point.

There are 2 ideas here:

1. you are not going to buy the computer you are talking to
2. you ask a double negation question to nix the difference between the Japanese and the Chinese computers

From Charles Floyd: An alternative to the double negation question for this specific problem is to ask the computer number 1: "is the computer number 2 more likely to tell me the truth than the computer number 3?" and then, if the answer is "yes" buy the computer number 3, and if the answer is "no" buy the computer number 2:

1. if you are talking to the Japanese computer, then the "less truthful" of the remaining 2 computers is the Chinese one, and that is what you want
2. if you are talking to the Chinese computer, then the "less truthful" of the remaining 2 computers is the Russian one, but the Chinese computer will lie and tell you that the Japanese is "less truthful"
3. if you are talking to the Russian computer, it does not matter which of the other two computers to buy

15. [problem] Separate the 12 coins into 3 sets of 4 coins each and compare 2 of the sets. If they are the same, the counterfeit coin is in the last group of 4 and we compare 3 coins from this last group with any 3 coins from the other 8 genuine ones. If they weigh the same, the counterfeit is the 4th and we still have one more weighting to find out whether the counterfeit is lighter or heavier than the genuine one. If they weigh different, we know whether the counterfeit is lighter or heavier than the genuine one and we have 3 coins, one of which is counterfeit. We compare two of them and are done.

If the first weighting revealed a discrepancy, we have 3 sets of coins, 4 each: light, heavy and genuine. Compare 2 groups: llh and llh. If they are the same, we compare the two remaining h's with each other and the heavier is counterfeit. If one of them, say the first one, is heavier, we have to choose between the h from the first group and the two l's from the second group, so we compare the two l's: is they are the same, the h is counterfeit, otherwise the lighter of them is counterfeit.

Note that each weighting gives us 1 trit of information, so 3 weightings should allow us to distinguish between 27 variants. Indeed, if we knew whether the counterfeit coin is lighter or heavier, we could have detected it among 27 coins. The way the problem us stated though, we could only distinguish between 24 variants (1 out of 12 coins times 1 out of 2 heavies/lighter variants).

16. [problem] First of all, projecting the center of the sphere on the plane perpendicular to our plane and passing through the two points, we reduce the area, so the problem is thus reduced to a planar one: given two points and a line separating them in a plane, find the circle through these two points with the shortest intersection with the line.

Let the line be `l`, points `A` and `B` and the line `AB` intersects the line `l` at the point `K`, while the circle intersects the line `l` at points `X` and `Y`. Then, `XK*KY = AK*KB = constant` therefore `XY = XK+KY` is minimal when `XK = KY`, i.e., the center of the circle is the intersection of the midpoint perpendicular to `AB` and the perpendicular to `l` at `K`.

17. [problem] The trick is to send the slowest people together: `FM+F+CG+M+FM` is 17 minutes.

18. [problem] Light the first fuse from both ends and the second one from one end. Two minutes later the first fuse will be spent and the second one will still have 2 minutes left in it. Light it from the other (not-yet-burning) end. One minute later it will be spent. Together it makes three minutes.

19. [problem] Cut the rope in two pieces - 10m and 20m, tie a bowline at one end of the short piece, attach the other end to the roof, slide the long piece through the noose and fold it in half. Now you have a 20m composite rope, enough to get to the midpoint. Attach one end of the long piece to the ring and slide it out of the noose. Now you have a 20m rope to go 20m down.

20. [problem] You put the diamond in the box, lock it and mail it. The recipient locks the box he got from you with his own lock and sends it back to you. You remove your lock and mail the box again.

This problem is related to the private key encryption when the private keys commute.

Assuming the locks are "padlocks", there is another solution: lock an empty box, send it to the recipient, he adds his lock so that it goes through one half of a latch and sends it back, you open the box (it is locked only with your lock), put the diamond in and lock it, putting your lock through the other latch and your recipient's lock (so that the box is locked with the the chain of two locks), then send it to the recipient, who opens the his lock and thus unlocks the box.

21. [problem]
1. Open the refrigerator, put in the giraffe and close the door. [This question tests whether you tend to do simple things in an overly complicated way.]
2. Open the refrigerator, take out the giraffe, put in the elephant and close the door. [This tests your ability to think through the repercussions of your actions.]
3. The Elephant - he is in the refrigerator. [This tests your memory.]
4. You swim across - all the Crocodiles are attending the Animal Meeting! [This tests whether you learn quickly from your mistakes.]
According to Andersen Consulting World Wide, around 90% of the professionals they tested got all questions wrong. But many pre-schoolers got several correct answers. Andersen Consulting says this conclusively disproves the theory that most management consultants have the brains of a four year old.

22. [problem] If two slugs meet at the same point, the line going through them always stays parallel to a certain direction. Therefore, since `A` and `B` meet, we see that the lines `AC` and `BC` must coincide (similarly, `AD`=`BD`), thus all 4 slugs remain on the same line at all times.

Another solution (by Tanya Khovanova) is to consider the 3-dimensional space-time, where the trajectories (world lines) of the slugs are straight lines. The condition that two slugs meet means that the corresponding world lines intersect, which implies that all 4 lines lie in the same plane, thus they all intersect (since their projections on the spatial dimensions intersect).

23. [problem] The answer is 1/2. When they cast `n` coins each, the result can be
1. 1st has more heads - this is unfavorable regardless of the last coin of the 2nd person
2. 2nd has more heads - this is favorable regardless of the last coin of the 2nd person
3. 1st and 2nd have the same number of heads - then there is a 50:50 chance that the last coin of the 2nd person would make the result favorable.
Since [1] and [2] have equal probabilities and [3] is split into two equal-probability groups, we observe that the two events, that the 2nd person has (strictly) more heads than the 1st one and that the 1st one has at least as many heads as the 2nd one, have equal probabilities.

24. [problem] As soon as the end soldiers turn outside, they will never turn again, thus induction shows that the situation will stabilize with the left-most `k` soldiers looking left and the right-most `l` soldiers looking right. It will take at most `N-1` (`N` being the the number of soldiers) turns to stabilize, the maximum being achieved in the `N-1` cases when some left-most soldiers are looking right and the rest are looking left. The average number of turns divided by `N` seems to be converging to about `0.6` from below.

Since whenever two soldiers look at each other's faces they turn around, the number of soldiers looking left and right is constant, so the number of soldiers who will be finally looking left (right) is the same as the number of soldiers who were looking left (right) initially.

If we encode a left-looking soldier as `1` and a right-looking soldier as `0`, this is a parallel sorting routine, where at each step the neighboring unordered digits are transposed.

25. [problem] The answer is `2g` (`g=9.81m/sec2` is the acceleration of the free fall). Since the ball was dropped from a significant height, it was moving at a constant speed when it hit the ground, i.e., the resistance of the air at that speed was equal to the free fall acceleration. After bouncing the ball was moving in the opposite direction with the same speed, so the air resistance was the same but acting in the opposite direction.

26. [problem] The answer is `2` and `6`. The smallest number with two permissible product decompositions is `12=2*6=3*4`. If the second mathematician had `7=3+4`, he would have to be deciding between `3,4` and `2,5`. Since `10=2*5` has only one product decomposition, it is out, so the second mathematician would have known the answer (`3,4`) after the first mathematician answered no the first time. Therefore it could not have been `7=3+4`. If the numbers were larger, the negative answer of the second mathematician would not have given enough information to the first.

27. [problem] If both sexes have the same probability 1/2, then whatever the first child is, the couple will have to have on average 2 more kids to get the other sex, so the answer is `3`. For arbitrary probabilities using generating functions, see the details.

28. [problem] The answer is `14`. The strategy is to drop the first ball from the `K`-th story; if it breaks, you know that the answer is between `1` and `K` and you have to use at most `K-1` drops to find it out, thus `K` drops will be used. It the first ball does not break when dropped from the `K`-th floor, you drop it again from the `(K+K-1)`-th floor, then, if it breaks, you find the critical floor between `K+1` and `K+K-1` in `K-2` drops, i.e., again, the total number of drops is `K`. Continue until you get above the top floor or you drop the first ball `K` times. Therefore, you have to choose `K` so that the total number of floors covered in `K` steps, which is `K(k+1)/2`, is greater that 100 (the total size of the building). `13*14/2=91` -- too small. `14*15/2=105` -- enough.

Obviously, the only possible strategy is to drop the first ball with some "large" intervals and then drop the last ball with interval 1 inside the "large" interval set by the two last drops of the first ball. If you claim that you can finish in 13 drops, you cannot drop the first ball for the first time from a floor above 13, since then you won't be able to detect the critical floor 13. The next cannot be above 25 etc.

29. [problem] The answer is `31`. The locker number `i` is accessed as many times as it has divisors. E.g., locker number `6` is accessed `4` times - by the first, second, third and sixth kids. Thus the lockers which will be open are those whose number has an odd number of divisors, i.e., full squares (since we have an involution on the set of divisors of `i`, namely, `j --> i/j` whose fixed point, if any, is the square root of `i`). The number of full squares less than `1000` is `(isqrt 1000)` which is `31`.

30. [problem] The answer is `5` meters. The cop can walk one of the corridors to the end and ensure that the bum is not there. Now he has two corridors - `A` and `B` - and he knows that the bum is farther than `a0=1` in `A` and farther than `b0=1` in `B`. The cop runs `x0=b0+1=2` meters into `A` and back in `x0` seconds. Now ```a1 = (x0+1) - x0/2 = x0/2 + 1 = 2``` (the cop inspected `x0+1` meters of the corridor `A`, but in `x0/2` seconds that he ran back, the bum could reclaim `x0/2` meters). In the corridor `B`, the bum could make it to the room in `b` seconds and run into the "clean" corridor for another `1` meter, but the cop is already in the room and he will see the bum, so he can be sure that the bum is still in `B`, so `b1=1`. Next, the cop runs `x1=a1+1=3` meters into `B` and back in `x1` seconds. Now `b2 = x1/2 + 1 = 5/2` and `a2 = 1`. Thus ```xn+1 = an+1 + 1 = (xn/2 + 1) + 1 = xn/2 + 2``` which converges to `4`, thus the maximum corridor length is `5`.

31. [problem] Both sides are equal to the largest power of 2 which divides `m`, call it `M=M(m)=2r(m)` where `r(m)` is the ruler function. To see this, write `m` in binary, then it ends with a 1 and some (possibly none) 0s (this 1 and these 0s are exactly the binary representation of `M`). `-m`, written in Two's Complement, is the same sequence inverted (i.e., 1 is replaced with 0 and 0 with 1) and 1 added, i.e., it ends with the same number of 0s as `m` (which should not be too surprising since, obviously, `M(-m)=M(m)`), thus, when you take `m & -m`, you get `M`. Similar logic works for the left hand side as well.

32. [problem] The answer is no. Consider the random variables that take the positive value `1/p` with probability `p`, and the negative value `-1/q` with probability `q=1-p` (thus the mean is 0). Since we know that the variables are more likely to be positive than to be negative, we know that `p > 1/2 > q`, thus `1/p - 1/q < 0`. Therefore, for the sum `X+Y` to be positive, both variables must be positive, `X=Y=1/p`, which happens with probability `p*p`, which does not have to be bigger that 1/2 when `p > 1/2`. E.g., when `p=2/3`, `P(X+Y>0) = 4/9 < 1/2`.

33. [problem] They can save all but one, and the one they cannot save, the first one, cannot be saved with any tricks since he has no information at all. The protocol is like this: the first scholar counts the red caps he sees and says red if this number is odd, and blue if it is even. He meets his fate, but the rest of the scholars are saved: each one of them counts the red caps ahead of him, adds to the number of times the previous scholars (including the first one!) said red, and, if the number is odd, he says red himself, otherwise he says blue.

34. [problem] The problem says smoke, not make!
• He can make 6 cigarettes out of 24 cigarette butts,
• then smoke them and have 6 cigarette butts;
• then make 1 cigarette out of 4 butts and save 2 butts;
• then smoke it and have 1+2=3 butts;
• then borrow 1 butt from a fellow bum, make a cigarette, smoke it, and return the butt

35. [problem]
1. Similar to parabola, the midpoints of all parallel sections lie on a line ("centerline for these sections") though the center, so by choosing two non-parallel sections, we can get the center `O` at the intersection of their centerlines.
2. A suitable circle centered at the center intersects ellipse at 4 points that determine the directions of the axes.
3. Take a non-axis section, its centerline, and a line parallel to the section through the intersection `I` of the section with the ellipse (it will be tangent to the ellipse at `I`). Let foci be `A` and `B`. For the triangle `ABI` we have the median `IO`, the bisector at `I` (the normal to the tangent at `I`), and the line `AB` (the longer axis). The circumscribed circle for the triangle `ABI` must pass through the point `X` of the intersection of the bisector with the shorter axis and though the point `J` symmetric to `I` wrt the shorter axis (because the circle's center lies on the center perpendicular to the side `AB` that is the shorter axis). The circumscribed circle for the triangle `IJX` thus intersects the longer axis at the foci `A` and `B`.
4. The tangent at an arbitrary point `Z` on the ellipse is the normal to the bisector of the angle `AZB`.
5. If `Z` is not on the ellipse, consider all the sections `XY` of the ellipse through `Z`. The locus of points `T` between `X` and `Y` such that the distance `ZT` is the harmonic average of the distances `ZX` and `ZY` is the circle, that intersects the ellipse at two points `A` and `B`, and the lines `ZA` and `ZB` are tangent to the ellipse. This is because the cross-ratio `[X,T,Y,Z]=-1` and if we project `Z` to infinity (this preserves cross-ratio), `T` is projected to the midpoint between images of `X` and `Y` and the circle above is projected onto the centerline.

36. [problem]

This is a simple application of the Bayes formula:
```Pr(Urn has N White|Sample has M White) = Pr(Sample has M white|Urn has N White) / Pr(Sample has M white)```.
The numerator is 1, the denominator is `sum(k=0,...,N-1;(1-k/N)M)` so
```Pr=NM / sum(k=1,...,N;kM)```.
The denominator is
```N(M+1)/(M+1) + NM/2 + ...```
so, approximately,
`Pr=2(M+1)/(2N+M+1)`.
Thus, if `M=N` large, this probability is approximately `2/3`.

37. [problem]

Since the ants are indistinguishable for our purposes, their actual behavior when they bump into each other (turn around) is equivalent to the ants passing through each other, i.e., we can assume that they run independently. This means that in at most one second all ants will be gone.

38. [problem]

The essential component of the proof is the Axiom of Choice.

Placement of caps correspond to infinite sequences of 1s and 0s. We call two such sequences similar if they differ only in a finite number of places. This is an equivalence relationship, so we can factor the set of sequences by it and find a representative element in each. Since each scholar sees all caps but his own, he knows the equivalence class and can make the guess prescribed by the selected representative element.

The alternative problem: there is a homomorphism from the infinite sequences of 0s and 1s onto `Z2` which extends the notion of parity. The scholars assume that the image of the sequence is (say) 0 and guess their own hat accordingly.

39. [problem]

Construction: given hypotenuse `AB` and a point `C` on it.

1. Construct a circle on diameter `AB`.
2. Draw rays `CD` and `CE` at angles `PI/3` (60 degrees) between them and `AB`.
3. Let `AB=CD=CE`, then `AD||BE` and `DE=AB`.
4. Draw the ray `CF||AD||BE` to the intersection `F` with the circle - that is the 3rd vertex of the right triangle.
5. Points `G=intersect(AF,CD)` and `H=intersect(BF,CE)` are the missing vertexes of the equilateral triangle.

To complete the proof, we need to show that `GH||AB`, which follows from `AG:GF=BH:HF`. To prove that, we need to apply...

Lemma: In a triangle `ABC` with point `D` on `BC`, `BD:CD=(AB*sin(BAD)):(AC*sin(CAD))`

Proof: Compare areas of triangles `ADB` and `ADC`.

... to triangles `AFC`, `BFC`, `DEC`.

40. [problem]
1. The answer is no. If the first die has side probabilities `pi` and the second one `qi` for `i=1..6`, the probabilities of the sums are `ri` for `i=2..12`, define polynomials `P(x)=p1+p2x+...+p6x5`, `Q(x)=q1+q2x+...+q6x5`, and `R(x)=r2+r3x+...+q12x10`. Then `R(x)=P(x)*Q(x)`.
If all sums are equiprobable, then `R(x)=(1+...+x10)/11`, and has 10 complex mutually conjugate roots (11-degree roots of unity), so its irreducible decomposition over R has 5 quadratic polynomials and thus `R` is not a product of two real polynomials of degree 5.
2. Due to translation symmetry, each student has the same probability `p` to end up with a solution. The probability of not getting a solution is ```1-p=P(not solving onelsef) * P(not copying from left) * P(not copying from right)```.
Since `P(not solving onelsef)=1/2` and `P(copying)=P(the neighbor has the solution) * 1/4 = p/4`, we have a quadratic equation `1-p=(1-p/4)2/2` whose only positive solution is approximately `65%`.

41. [problem] Encode each barrel (0..999) in binary and water the plants (0..9) accordingly. E.g., barrel number 130=128+2, sо pour from it into plants number 7 and number 1. The set of dead plants tomorrow will determine the barrel which was poison: if, say, plants 2,4, and 6 are dead, then the poison is in barrel 4+16+64=84.