Maths Olympiad Prep

Library / /6 of 8

Combinatorics Difficulty 7.5 National Olympiad, round 2 Prove it JBMO

Problem:

Alice and Bob play the following game on a 100×100100 \times 100 grid, taking turns, with Alice starting first. Initially the grid is empty. At their turn, they choose an integer from 11 to 1002100^{2} that is not written yet in any of the cells and choose an empty cell, and place it in the chosen cell. When there is no empty cell left, Alice computes the sum of the numbers in each row, and her score is the maximum of these 100100 sums. Bob computes the sum of the numbers in each column, and his score is the maximum of these 100100 sums. Alice wins if her score is greater than Bob's score, Bob wins if his score is greater than Alice's score, otherwise no one wins.
Find if one of the players has a winning strategy, and if so which player has a winning strategy.

Solution

Solution:

We denote by (i,j)(i, j) the cell in the ii-th line and in the jj-th column for every 1i,jn1 \leq i, j \leq n. Bob associates the following pair of cells: (i,2k+1),(i,2k+2)(i, 2k+1), (i, 2k+2) for 1i1001 \leq i \leq 100 and 0k490 \leq k \leq 49 except for (i,k)=(100,0)(i, k) = (100, 0) and (100,1)(100, 1), and the pairs (100,1),(100,3)(100, 1), (100, 3) and (100,2),(100,4)(100, 2), (100, 4).
Each time Alice writes the number jj in one of the cells, Bob writes the number 1002+1j100^{2} + 1 - j in the other cell of the pair.
One can prove by induction that after each of Bob's turns, for each pair of cells, either there is a number written in each of the cells of the pair, or in neither of them. And that if a number jj is written, 1002+1j100^{2} + 1 - j is also written. Thus Bob can always apply the previous strategy (since j=1002+1jj = 100^{2} + 1 - j is impossible).

At the end, every line has sum (1002+1)×50\left(100^{2} + 1\right) \times 50.

Assume by contradiction that Alice can stop Bob from winning if he applies this strategy. Let cjc_{j} be the sum of the numbers in the jj-th column for 1j1001 \leq j \leq 100: then cj50(1002+1)c_{j} \leq 50\left(100^{2} + 1\right). Note that:
100×50(1002+1)c1++c100=1++1002=1002(1002+1)2=100×50(1002+1) 100 \times 50\left(100^{2} + 1\right) \geq c_{1} + \cdots + c_{100} = 1 + \cdots + 100^{2} = \frac{100^{2}\left(100^{2} + 1\right)}{2} = 100 \times 50\left(100^{2} + 1\right)
Thus we have equality in the previous inequality: c1==c100=50(1002+1)c_{1} = \cdots = c_{100} = 50\left(100^{2} + 1\right). But if aa is the number written in the cell (100,1)(100, 1) and bb the number written in the cell (100,2)(100, 2), then c1b+c2c=99(1002+1)c_{1} - b + c_{2} - c = 99\left(100^{2} + 1\right). Thus b+c=100(1002+1)99(1002+1)=1002+1b + c = 100\left(100^{2} + 1\right) - 99\left(100^{2} + 1\right) = 100^{2} + 1: by hypothesis cc is also written in the cell (100,3)(100, 3) which is a contradiction.

Thus Bob has a winning strategy.

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 reproduced verbatim; metadata (topic, difficulty) added by this project.