Notes for the Puzzle TOAD

These are partial notes for the answers (and some of my ideas when trying to work out them) for the problems in Puzzle Toad.

"*” means fun in the list.

Problem 39

We find $L$ with dishes one by one. At one round, we can compare any two dishes. When more than a half prefers one dish, then it beats the other. We can find one dish beats at least a half of other dishes. We add this in $L$ and delete this and the dishes $d$ beaten by it. Now recursively do this, by $1024=2^{10}$, we can terminate in $| L | \le 10$.

Problem 38 (Expectation, *)

The problem is interesting! First we let the saucers on a triangular grid, then with calculation we can get the area of the saucers is $(3\pi/4) / (3\sqrt{3}/2) = \pi/2\sqrt{3} > 0.9$. Now we move the grid, by linearity we know the expected points to be covered is $10\pi/2\sqrt{3} > 9$, so we know it must be possible to achieve $10$.

Problem 37 (*)

Do things by this algorithm in one turn (with length $n$, $n$ is the worm’s length):

• If no $0 \rightarrow 1$, we perform $1 \rightarrow 0$.
• If at least once $0 \rightarrow 1$, we perform $1 \rightarrow 1$.

Then in every turn, it will become $0$ or the binary number will increase.

So at last we can get the worm $0…0$.

Problem 36 (IMO2011, hard, *)

The point is: in the whole procedure, the number of points on the left or right remains the same (exclude the pivot), which can be proved by imagining one turn of pivot changing.

Now consider a general coordinate with every two points differ in both $x$ and $y$. We let the line to be on $+y$ direction, rotating clockwise from the point whose $x$ coordinate is the $\lfloor n/2 \rfloor - th$ smallest. Then after it rotating $\pi$, we can find what’s the pivot by above!

Then the fact is, for any point, it may be the starting or ending pivot, or it may cross the line, which requires it to be a pivot at some time. Therefore, we know every point is struck down.

Problem 35 (hard)

Problem 34

The problem is equivalent to: for odd $n$, show that in $F_2$, symmetric matrices with diagonal entries $0$ are singular. We may calculate the determinant to prove this (not trivial).

Problem 33 (easy)

A easy probability problem. First assume they are just on the side of the circle, and one is on angle $0$, then draw a square area to represent the other two angles and discuss the area for them to contain the center. It is easy to get that every turn the probability is $1/4$, then just deal with the expectation.

Problem 32 (*)

An interesting construction problem. A simple approach is $1\ 1\ 1\ 1\ 1\ 1$ $\rightarrow$ $3\ 0\ 3\ 1\ 1$ $\rightarrow$ $12\ 0\ 1\ 1$ $\rightarrow$ $2048\ 0\ 1$ $\rightarrow$ $2^{2048}$. The solution find that sometimes using button $A$ is better and gives a better answer: $3\ 0\ 3\ 1\ 1$ $\rightarrow$ $14\ 0\ 1\ 1$ $\rightarrow$ $20480\ 0\ 1$ $\rightarrow$ $5 \times 2^{20479}$. Of course we should buy this, do the operation and find that this is much better than a lottery.

Problem 31 (easy)

(a) The first player delete 50 first, then every turn he maintains the amount of two sides of $50$ to be the same by deleting numbers from inner to outer. Then the last two are on different sides of $50$. He delete $54$ numbers, so the gap is at least $55$.

(b) The first player delete $2$ and now we see it as $5$ $1,2,3,4,5$s with an extra $1$. Now make it into pairs $(1+4),(2+3)$, then the first player can delete the number in the same pair after the second player. Then there remains an $1$ and 5 $5$s. The player can delete $1$ first after any deletion of $5$ or delete a $5$ after the deletion of $1$. Then the remain numbers form a pair or are two $5$s.

Problem 30 (hard)

Problem 29

Of course we can induction to get the conclusion, but informally we can think this: the answer will be yes if someone goes to the last person’s seat, and the answer will be no if someone goes to seat 17. The probabilities must be the same in any random move. Then the answer is $1/2$.

Problem 28 (hard,*)

A short and beautiful proof is given by solution. Consider $n$ walkers, for the edges with $1,2,…,m$, swap the walkers on the edge in turn. Then after $m$ turns the $n$ walkers walks $2m$ in total, which shows that at least one walks with distance $2m/n$.

Problem 27 (easy)

$n$ people guess the sum to be odd, while other $n$ guess the sum to be even.

It is a technique to make local guesses related to global situations to give a win probability. A more complex example is about the permutation, which is also a classical problem.

Problem 26

First guess where they are: one shop is likely to be placed on the center by symmetry. The other $6$ then can each cover a $60$ degree part of the circle. By calculation we can find that the radius can be $1/2$ when we place the shops on the midpoints of endpoints of the $60$ degree arcs.

To prove the optimality we consider the circumference. A circle with radius < $1/2$ cannot cover a $60$ degree arc, so we need $7$ cycles all intersect the circumference. But in this case, the center is not covered.

Problem 25

If yes, WLOG we can suppose the period is a multiple of $100$, so we can suppose the sequence is started from $f(0)=0$. We soon find that $f(i)$ is the parity of number of $1$s in the binary expansion of $i$. Then if for $i \geq 2^k$ there’s a period $t=1…$ with $p$ digits, $p«k$. We consider two $k$-digit numbers $10…0$ and $10…010…0$ with the last $p$ digits $10…0$, then it’s easy to see there’s a contrast. The official solution gives a stronger conclusion.

Problem 24 (*)

A simpler version is to choose from $n$ numbers so that the sum is divided by $n$. This is a special case for it. But in this problem the solution is similar. We need a new definition of “residue” by listing $a_1…a_n$ and $b_1…b_n$, suppose the sum of array $a$ is not less than $b$, then define the residue $r_k= \sum_{i=1}^{k}b_i - \sum_{i=1}^{l} a_i$, $l$ is chosen to make $r_k$ smallest but non-negative. Then there’s some $k$ such that $r_k=0$, or there are two $r_k$ being the same. Both situations leads to a solution.

Problem 23

Surprisingly, yes. Consider the middle point of the ray, by expand the reflection, it must be on one of four grids, decided by the parity of horizontal and vertical reflections. To get a grid, using four points is enough, so we need at most $16$ in total.

Problem 22

We consider to decrease the length of the number in half (ignoring $0$s in the end): for the first half ($ \lfloor n/2 \rfloor $), give the same number; for the second half, give the complement, then the length after one turn is at most $\lfloor n/2 \rfloor + 1$. We can use $O(logn)$ turns to decrease it into a one or two digit number. Then it is easy to solve the restricted problem in $O(1)$ turns.

Problem 21

To locate a direction which can go within $1m$ to the truth needs $O(1/D)$ radius and thus needs $\Omega(D)$ tries to search at that distance. But we can balance the accuracy and the tries used since we can use $O(\sqrt{D})$ tries to get the accuracy within $O(\sqrt{D})$ and then after $D$ steps the remaining distance is in $O(\sqrt{D})$. Then recursively solve it.

Problem 20 (easy)

Yes. The idea is that, for the groups the president will win, make it balanced; for the groups the opposite will win, make it all opposite. Then for the case $n=3^m$, we only need $2^m$ supporters, so the number of supporters can be in $o(n)$. This problem is similar and we only need to divide it carefully.

Problem 19 (easy,*)

It’s trivial that we can query these $n$ numbers directly. On the opposite, at least we need to cut all diagonal values with its $4$ opposite values, which means the edges of the submatrices must cover the small squares surrounding them (for $(1,1)$ and $(n,n)$ we need one square containing them, so the result is the same), but one square can at most intersect $4$ edges of these small squares, which means we need $n$ queries at least.

Problem 18

Problem 17

Problem 16

Problem 15

(a) The last one can report the parity of the number of white hats of the first $n-1$. So they can guarantee there’s only one elimination.

(b) Informally, let’s consider a error correcting code, then do this: when the other digits is in the code, guess the opposite (its neighbor). They are eliminated only when the situation is in the code or the situation is not in the neighbors. The solution gives analysis about the winning probability.

(c) Consider all possible situations, if for one situation the first response is the quickest, then change the responder’s hat color will make him wrong.

With extra information, one can induction that, at time $t$, “there’s at least $t$ black hats” is a common knowledge, so the ones with black hats will know it if they only see $t-1$ black hats, they need to report. Then the ones with white hats (if exist) report.

Problem 14 (hard,*)

A simpler question is that, when there are only A and B, using one question to know the proper restroom. This is done by asking one what’s the other’s answer, which will be always false.

Now we want to avoid asking C using one question. The question in solution is “For the two other people, who is more likely to tell truth?” Then the one not in the answer must be A or B. Then ask the problem above.

Problem 13

Problem 12

Think a configuration, where they are on the same height, and at least one is on a local minimum/maximum. Then for them both going up or down, they have two or four choices, except the two configurations showing the starting and ending situations. Now we can certainly build a graph. The starting and ending nodes have degree 1, while others have degree 2 or 4. Then they must be in the same component since a component cannot a single odd-degree node, which means they can achieve this.

Problem 11

Problem 10 (hard)

A famous question. The strategy is, everyone first find his table, look at the card and continually go to the table given by the card until he find his card or he fails.

Then we can see that, although everyone has a winning probability $1/2$, their probabilities are correlated by the length of cycles in the permutation! We can calculate the probability for having a cycle > $1/2$ size, which is easy, and we will find the winning probability high.

Problem 9

(a) Notice that if two ants intersect, then they going through each other gives the same situation. So we can simply calculate the time by one ant from one side to the other.

(b) This is similar as above but more tricky. First, from above we can see that they will end up in the same location (but there may be a permutation). Also we know that the relative location don’t change for two ants. Let the name “Alice” pass on as well when two ants intersect. Then we can see “Alice” will be the name of the original Alice if it passes with $kn$ times. Calculating this can know that if Alice goes clockwise, then there are $0$ or $n/2$ (when $n$ is even) going anti-clockwise. So we can calculate the probability.

(c) This is easy, but notice the corner cases in which Alice can infect nobody.

Problem 8 (easy,*)

After problem 38, it seems to be easy. We know the (weighted) expectation may be exactly $H_n$ if we cleverly assign every path’s weight and let every node on layer $i$ be passed with probability equally $1/i$. The weight assignment of every path can be done by an assignment on every edge with multiplication (consider the case only going left or right on the pascal triangle).

Problem 7 (*)

The answer is yes since $k<n$. The construction for $n$ is simple. When $k<n$, consider the boundary length of the garbage area. We notice that the procedure won’t increase it! Then we can notice that it will not exceed $4n$ with $k<n$.

Problem 6

First we should prove that, the maximum possible candy number of everybody is bounded. Then we should prove that, at least one lowest value will increase if it is not equally divided. After that, we can reach the conclusion.

Problem 5

Problem 4 (easy)

Consider $\sum 1/2^{a_i}$. We can prove that, by equal division, this value can always be $\geq 1$ if the original one $\geq 1$. In contrast, by deleting the set with more value, this value can always be $< 1$ if the original one $< 1$. Then we can reach the conclusion.

Problem 3

Consider we have found singular states $a_1<…<a_k$, the next singular state $a_{k+1}$ is $a_k+a_l$, where $l$ is the smallest number that $a_k$ can be chosen after $a_l$. On $a_k<b<a_{k+1}$, the first one can take the chips to $a_k$ left to win if $b \leq a_k+a_{l-1}$. Otherwise take it to $a_k+a_{l-1}$ and win using two steps. On $a_{k+1}$, the first one can’t take $\geq a_l$. Then the second one can guarantee that he can take the last chip of first $a_l$, then the last $a_k$.

Problem 2

Consider the case when $n=a \times 2^b$, $a>1$ is odd. Then for two lights with distance $2^b$, Merlin can always let them be one on and the other off. If $n$ is a power of $2$, then we want to induction by letting the opposite lights be of the same number. Consider “different” as “off”, “same” as “on”, then we can actually do induction! After that, we see opposite lights as a whole and operate simultaneously, then we see the conclusion can be reached by induction.

Problem 1

$(a)$ Consider they form a queue. Every time, ask the head of the queue about the one chosen, then pop. If yes, add $1$ to the counter; if no, add $-1$. If the chosen one is with counter $0$, kick him and choose the head with counter $1$.

$(b)$ The managers can pretend to have two groups of engineers with the same size and say that the others are managers. Then by symmetry we know it can’t be identified.

$(c)$ (solution: may not)