Maths Olympiad Prep

Library / /13 of 18

Combinatorics Difficulty 7.3 National olympiad, round 2 Prove it Argentina

Let n>d>0n > d > 0 be integers. Ana, Beto and Carlitos play *blind man's bluff* over an infinite grid. Initially, Ana and Carlitos are in cells at distance nn, and there is a candy in a cell which is at distance dd from Carlitos. Carlitos is blindfolded and can only see his own cell, whereas Ana and Beto can see the whole grid. Two movements are performed alternately.
1. Carlitos moves to an adjacent cell. If he finds Ana there, Carlitos loses. If he finds the candy, but not Ana, Carlitos wins. If the cell was empty, Beto shouts "hot" or "cold", at his discretion.
2. Ana moves to an adjacent cell. If she finds Carlitos or the candy, Ana wins. Otherwise, the game continues.
Find, for each dd, the least nn such that Beto and Carlitos can coordinate a strategy to ensure Carlitos' victory, regardless of the initial positions of Ana, Carlitos, and the candy.

*Remark:* Two cells are adjacent if they share a common side. The distance between cells XX and YY is the least pp for which there is a sequence of cells X=X0,X1,,Xp=YX = X_0, X_1, \dots, X_p = Y such that XiX_i is adjacent to Xi1X_{i-1} for all i=1,,pi = 1, \dots, p.

Solution

Answer: n=2d+2n = 2d + 2.

Abbreviate Ana, Beto, Carlitos and the candy by A,B,CA, B, C and DD respectively. We also write d(X,Y)d(X, Y) for the distance between XX and YY.

We claim that for n2d+1n \le 2d + 1, CC cannot ensure his victory. For the first movement there is no information. Assume without loss of generality that CC moves to the left. It could be the case that the initial configuration was the following:

      \cline26d     \cline16CDA\cline26      \cline16      \cline16n      \begin{array}{c|c|c|c|c|c} \text{ } & \text{ } & \text{ } & \text{ } & \text{ } & \text{ } \\ \cline{2-6} d & \text{ } & \text{ } & \text{ } & \text{ } & \text{ } \\ \cline{1-6} C & \cdots & D & \cdots & A & \cdots \\ \cline{2-6} \text{ } & \text{ } & \text{ } & \text{ } & \text{ } & \text{ } \\ \cline{1-6} \text{ } & \text{ } & \text{ } & \text{ } & \text{ } & \text{ } \\ \cline{1-6} n & \text{ } & \text{ } & \text{ } & \text{ } & \text{ } \end{array}

Suppose AA moves to the left on her first turn. After these moves, d(C,D)=d+1d(C, D) = d + 1 while d(A,D)nd1dd(A, D) \le n - d - 1 \le d. Therefore, no matter how CC moves, AA will get to DD before CC does if she always moves to the left.

Figure 1

We will now show that for n=2d+2n = 2d + 2, BB and CC can coordinate a strategy to win. We divide the grid into four regions labeled R1,R2,R3,R4R_1, R_2, R_3, R_4 (observe that CC's initial cell is not part of any of these regions).

On his first two movements, CC moves to the left and to the right, returning to his initial position. This way, after Ana completes her second turn we have d(A,C)2dd(A, C) \ge 2d and d(A,D)dd(A, D) \ge d.

Meanwhile, BB uses these two turns to tell CC what region contains DD, under the following convention:
(hot, hot)R1(hot, cold)R2(cold, hot)R3(cold, cold)R4 (\text{hot, hot}) \rightarrow R_1 \quad (\text{hot, cold}) \rightarrow R_2 \quad (\text{cold, hot}) \rightarrow R_3 \quad (\text{cold, cold}) \rightarrow R_4

Assume without loss of generality that DD is in R1R_1 (for the other cases, analogous strategies are obtained by rotation). BB and CC's strategy is as follows. In his third turn, CC will move upwards. From then on, BB will shout “cold” if CC is not on the same row as DD; otherwise he shouts “hot”. In this way, whenever CC hears “cold”, he will know that he must move upwards to reduce his distance to DD. And when he hears “hot”, he starts moving to the right. (Note that it is possible that CC will never hear “Hot”, meeting DD just by going up.)

Since d(C,D)d(C, D) decreases on each turn, after dd turns CC gets to DD. However, to complete the proof we must make sure that AA will not get to CC or DD before CC wins the game. Suppose CC moved x<dx < d times following the previous strategy. Then d(A,C)2d2x>0d(A, C) \ge 2d - 2x > 0 (this is because both AA and CC move to an adjacent cell on each turn, so their distance is reduced by at most 2), while d(A,D)dx>0d(A, D) \ge d - x > 0 (because the candy does not move). Hence AA cannot reach CC or DD before CC wins the game, as claimed.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.