Alice and Bob play the following game on a $100\times 100$ grid, taking turns, with Alice starting first. Initially the grid is empty. At their turn, they choose an integer from $1$ to $100^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 $100$ numbers. Bob computes the sum of the numbers in each column, and his score is the maximum of these $100$ numbers. 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. Théo Lenoir, France
Problem
Source: JBMO 2023 Problem 3
Tags: combinatorics, grid, game
26.06.2023 10:29
The second player have the wining strategy.He place horizondal domino in the row $1,2,3,...,99$ but not in $100$ and make the couples: $(100^2,1),(100^2-1,2),.....,(100^2/2+1,100^2/2)$ Τhen it follows if $A$ plays a number on someone domino then $B$ plays the number of his pair on the same domino.If $A$ playw a number at last row then $B$ place the other number of the pair in the last row mixed. So $B$ can make all sums of $A$ equal and for him to be at leasy two diferrent so he win.
10.07.2023 14:10
This beautiful problem was proposed by Théo Lenoir.
11.07.2023 16:19
It's interesting to see what happens when the side of the grid is an odd number, say $n.$ This time Alice achieves at least a draw. I don't know whether she can do better, perhaps no. She first puts in the cell $ (1,1)$ the number $ n^2.$ Then she pairs the cells in each column, excluding the cells of the first row, and pairs the cells in the first row, excluding the cell $ (1,1).$ Whenever Bob puts a number $ m$ in some cell, Alice puts the number $ n^2-m$ into its paired cell. In this way, after the game is over, the sum of all numbers in the $ i$-th column is $ n^2(n-1)/2+a_{1,i}$ where $ a_{1,i}$ is the number written in cell $ (1,i).$ Therefore, the largest sum is in the first column, namely $ n^2(n-1)/2+n^2.$ But this is exactly the sum of all numbers in the first row, so Alice achieves a draw. Edit: See here for more details.
21.07.2023 11:26
Divide the table into horizontal rectangles $2\times 1$. Consider firstly the strategy of $B$ for which whenever $A$ writes $x$ in some cell of a rectangle $2\times 1$ (from the abovementioned ones), $B$ writes $100^2 + 1 - x$ in the other cell of the same rectangle. (Note that $x\neq 100^2 + 1 - x$ since $100^2+1$ is odd, so such a move of $B$ is always possible.) In this case the sum of numbers in each row is $50 \cdot (100^2 + 1)$ and since the summing through rows and summing through columns give the same result, there must be a column with sum equal to $50 \cdot (100^2 + 1)$. Therefore $A$ cannot win. In order to ensure win, it suffices for $B$ to tweak a little his strategy so that the sum in each row remains the same, but at least one column has sum larger than $50 \cdot (100^2 + 1)$. One possible way to do this is the following: if we consider the first two rectangles $2\times 1$ in the last row, then whenever $A$ plays in a cell of one of these rectangles, $B$ plays in a cell in the other rectangle. (For all others $2\times 1$ rectangles the strategy from the first paragraph does not change.) If we suppose, for contradiction, that $B$ does not win, then the only possibility is that all coiumns have sum $50 \cdot (100^2 + 1)$. But since $2\times 1$ rectangles in the first two columns, apart from the last one, are with pairs of numbers of the form $(x, 100^2 + 1 - x)$ (with sum $100^2 + 1$), it follows that the sum of the numbers in the $2\times 1$ rectangle in the last row (and in the first two columns) is $2\cdot 50 \cdot (100^2 + 1) - 99 \cdot (100^2 + 1) = 100^2 + 1$, so it also consists of a pair of the form $(t, 100^2 + 1 - t)$, contradicting $B$'s strategy. Therefore $B$ guarantees a win.
20.01.2024 23:02
We claim that Bob has a winning strategy. Let $K=100^2+1$. WLOG let Alice place a number $n$ first in the bottom left cell. Then, Bob places $K-n$ in the right most cell in the bottom row. From there on, Bob plays as follows: If Alice plays a number $k$, Bob places $K-k$ on his turn in the same row that Alice placed $k$ in. Bob plays in the first $2$ columns iff Alice played in one of those two columns on the turn before. Note that in each row there are $50$ pairs of numbers that sum to $K$. Therefore, each row has sum $50K$, meaning Bob will win unless all columns sum to $50K$. But this is impossible since in the first $2$ columns, each of the first 99 rows sums to $K$. However, the numbers in the bottom row can't sum to $K$ by construction since the ``complement'' of the bottom left number is not the 2nd number in the bottom row. Therefore, the first $2$ columns cant sum to $99K+K$ or $100K$, so all columns cant have the same sum. This implies that Bob will win.
25.04.2024 16:10
Solved with MathLuis even though we both finished individually me ending up headsolving on the way to the garage. It turns that the problem for a general $n\times n$ grid is drastically easier for even $n$. It should be interesting to see what happens when $n$ is odd. We claim that Bob always wins, when the game is played for a $n\times n$ grid where $n\equiv 0 \pmod{2}$. To see why, consider the following winning strategy of Bob's. First, we pair the board into pairs of cells, where the cell $(i,j)$ is paired with the cell $(i,n-j)$. Since $n$ is even, such a pairing exists for each cell and is unique. Now, Bob's strategy is, when Alice assigns the number $1\leq r \leq n^2$ to any cell, Bob immediately assigns $n^2+1 - r$ to the cell which this cell is paired to under the above described pairing. This is clearly always possible since Alice goes first. Thus, Bob can always guarantee atleast a draw since the sum of all the rows in the ending configuration will simply be $\frac{n(n^2+1)}{2}$, which is the average, so there must exist some column, with atleast that sum. Now, Bob has to tweak this strategy a bit to ensure a win. What he does is this. There must exist a first move where numbers have been assigned to all cells but one (say cell $\mathcal{C}$) in some column and Alice decides to assign a number to some cell of the row $R$ cell $\mathcal{C}$ is in. Thus, there exists two columns $C_1$ and $C_2$ which have all but one entry filled (due to the nature of Bob's strategy). Then, there are 2 cases. Case 1 : Alice assigns a number to either $\mathcal{C}$ or its pair (under the previously described pairing). Here, Bob simply changes the pairing as follows. $\mathcal{C}$ is now paired to a cell $\mathcal{C'}$ directly to its left or right which was not its pair under the previous pairing. Further, the previous pair of $\mathcal{C}$ is paired to the previous pair of $\mathcal{C}$. All other pairs remain unchanged. Now, Alice assigns a number $r$ to $\mathcal{C}$ (or its pair in what follows WLOG assume its $\mathcal{C}$) such that the resulting column sum is exactly the average $\frac{n(n^2+1)}{2}$ since otherwise Bob can win. But then, the pair of $\mathcal{C}$ must be assigned exactly $n^2 + 1 -r$ in order to guarantee that this column sum is also exactly the average (due to the reflective nature of Bob's algorithm for paired columns). Thus, when Bob places $n^2+1-r$ in this newly paired cell, it is taken up and as a result, the pair of $\mathcal{C}$ is assigned an incorrect number guaranteeing Bob a win. Case 2 : Alice assigns a number to some cell of row $R$ besides $\mathcal{C}$ or its pair. Here, the new pairing pairs $\mathcal{C}$ with the cell to which the number was assigned by Alice, and the corresponding pairs are paired with each other. All other pairs remain the same. By the same argument as before, Bob can guarantee a win here as well. Thus, in all cases Bob can ensure a win, implying that Bob has a winning strategy when the game is played on a $100 \times 100$ grid as claimed..
28.06.2024 09:50
This was C3 at last year's shortlist.