Maths Olympiad Prep

Library / /348 of 397

Combinatorics Difficulty 6.9 National Olympiad Prove it Taiwan

Player A and B play a painful game on the real line. Player A has a pot of paint with four units of black ink. A quantity pp of this ink suffices to blacken a (closed) real interval of length pp. In every round, player A picks some positive integer mm and provides 12m\frac{1}{2^m} units of ink from the pot. Player B then picks an integer kk and blackens the interval from k2m\frac{k}{2^m} to k+12m\frac{k+1}{2^m} (some parts of this interval may have been blackened before.) The goal of player A is to reach a situation where the pot is empty and the interval [0,1][0, 1] is not completely blackened.
Decide whether there exists a strategy for player A to win in a finite number of moves.

Solution

No, B can ensure that the interval [0,1][0, 1] must be completely blackened by the time the ink runs out. At the beginning of round rr, let xrx_r be the largest real number such that [0,xr][0, x_r] has already been completely blackened (let x1=0x_1 = 0.) Suppose A chooses mm, and let yry_r be the integer satisfying
yr2mxr<yr+12m \frac{y_r}{2^m} \le x_r < \frac{y_r+1}{2^m}
Notice that I0r:=[yr/2m,(yr+1)/2m]I_0^r := [y_r/2^m, (y_r+1)/2^m] is the leftmost interval, among those that can be blackened in this round and have not yet been blackened.
B's strategy is to consider the next interval I1r:=[(yr+1)/2m,(yr+2)/2m]I_1^r := [(y_r + 1)/2^m, (y_r + 2)/2^m]. If I1rI_1^r has not yet been blackened, then B chooses to blacken I1rI_1^r; otherwise, B chooses to blacken I0rI_0^r. (For convenience, we assume that [1,2][1, 2] has already been completely blackened from the start.) To prove that the above strategy works, our goal is to estimate the amount of ink used at the end of each round. We will prove by induction that, if before the start of round rr, [0,1][0, 1] has not yet been completely blackened, then

1. The amount of ink used to blacken [0,xr][0, x_r] is at most 3xr3x_r.

2. For each mm, B blackens at most one interval to the right of xrx_r of the form [k/2m,(k+1)/2m][k/2^m, (k+1)/2^m].

The above conditions clearly hold for r=0r=0. Suppose they hold for all rk1r \le k-1; then at r=kr=k, consider the interval B blackens.

- If B blackens I1rI_1^r, it is easy to see that xr+1=xrx_{r+1} = x_r, and hence 1. holds by the induction hypothesis. Moreover, if at the beginning of round rr there is an interval of length 2m2^m to the right of xrx_r that has been blackened, then by this strategy it is easy to see that this interval must be I1rI_1^r, but this contradicts the fact that B chose I1rI_1^r, a contradiction. Hence 2. also holds.

- If B blackens I0rI_0^r, but [0,1][0, 1] has not yet been completely blackened. It is easy to see that 2. automatically holds. Notice that in this case both I0rI_0^r and I1rI_1^r will be blackened, so xr+1x_{r+1} will advance at least to the right endpoint of I1rI_1^r, that is, xr+1=xr+αx_{r+1} = x_r + \alpha, where α>1/2m\alpha > 1/2^m. Also notice that any interval that was already blackened before round rr and intersects (xr,xr+1)(x_r, x_{r+1}) must lie within [xr,xr+1][x_r, x_{r+1}]; by 2., these intervals all have different lengths, and all lengths are greater than 1/2m1/2^m, so the amount of ink used on them is less than 2/2m2/2^m. Therefore, the amount of ink used on [0,xr+1][0, x_{r+1}] is no more than
3xr+2/2m+1/2m=3(xr+1/2m)<3xr+1. 3x_r + 2/2^m + 1/2^m = 3(x_r + 1/2^m) < 3x_{r+1}.
Hence 1. also holds. This completes the proof of the induction step.

Now, suppose that after round r1r-1, [0,1][0, 1] has not yet been completely blackened. By 2., the intervals blackened by B in [xr,1][x_r, 1] must all have different lengths, with lengths 2k,k1xr2^{-k}, k \le 1-x_r. Hence the amount of ink blackened in [xr,1][x_r, 1] is at most 2(1xr)2(1-x_r). And by 1., the amount of ink blackened in [0,xr][0, x_r] is at most 3xr3x_r, so the total amount does not exceed 3xr+2(1xr)<33x_r + 2(1-x_r) < 3, that is to say, the ink has not yet been used up. Therefore A cannot win.

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 translated into English from zh; metadata (topic, difficulty) added by this project.