Two players play alternately on a $ 5 \times 5$ board. The first player always enters a $ 1$ into an empty square and the second player always enters a $ 0$ into an empty square. When the board is full, the sum of the numbers in each of the nine $ 3 \times 3$ squares is calculated and the first player's score is the largest such sum. What is the largest score the first player can make, regardless of the responses of the second player?
Problem
Source: IMO Shortlist 1994, C1
Tags: algorithm, combinatorics, game, game strategy, IMO Shortlist
jgnr
24.12.2008 05:09
We first prove that the second player can keep $ A\le 6$. Place 10 dominoes on the board as shown in the diargam. Whenever the first player marks a 1 on a cell of a domino, the second player marks a 0 on the other cell of the same domino if it is still empty. Since any $ 3\times 3$ square contains 3 complete dominoes, there are at least 3 0's inside. It follows that $ A\le 6$.
We now prove that the first player can make $ A=6$. Label the board $ (a,b,c,d,e)\times (1,2,3,4,5)$. Start by marking a 1 on c3. By symmetry, we may assume that second player's response is made on row 4 or 5. Disregard these two rows from now on. The first player then marks a 1 on c2. If the second player does not mark a 0 on c1, the first player will mark a 1 there in the next turn. Then either $ (a,b,c)\times(1,2,3)$ or $ (c,d,e)\times (1,2,3)$ contains 3 1's and no 0's. The first player can put three more 1's in that $ 3\times3$ square. If the second player's second move is on c1, the first player can guarantee 2 1's in $ (b)\times (1,2,3)$ as well as 3 1's in $ (a,d)\times(1,2,3)$. Hence either $ (a,b,c)\times(1,2,3)$ or $ (b,c,d)\times(1,2,3)$ will contain at least 6 1's. It follows that we can have $ A=6$.
Attachments:
math154
12.07.2010 20:34
I have a slightly different solution... As in the first solution, a tiling shows that the second player can keep the score at $6$, so it remains to prove that the first player can guarantee a score of $6$. The numbers in the unit squares below represent the number of $3\times3$ squares that they belong to. After the game is over, define $V$ to be the sum over all squares of the values of the squares times the numbers on the squares (i.e. each square contributes its value if it has a $1$ on it and $0$ otherwise). This is clearly equal to the sum of the sums of the $1$'s in the $3\times3$ squares. Let the first player play on C3 and the second player play, without loss of generality, in the first two rows. Now let the first player play on C4. If the second player does not play on C5, then at least one of the $3\times3$ squares with centers B4 and D4 will be void of $0$'s, so the first player can get a score of $6$ by repeatedly playing in that square. Now assume the second player does play on C5, which has a value of $3$. If the second player's first move was not on C2 (we assumed it was in the first two rows, so this means the first move had value at most $4$), then by the greedy algorithm the first player can guarantee \begin{align*} V\ge9(1)&+4(0)+6(1)+3(0)+6(1)+6(0)+6(1)+4(0)+4(1)+4(0)\\ &+3(1)+3(0)+3(1)+2(0)+2(1)+2(0)+2(1)+2(0)+2(1)\\ &+2(0)+2(1)+1(0)+1(1)+1(0)+1(1)=47>9\cdot5, \end{align*}which means at least one $3\times3$ square has to have $6$ ones at the end. So assume the second player's first move was on C2, and let the first player play on B3. If the second player doesn't move on D3, then again a greedy algorithm will guarantee that the first player has $6$ ones in some square since here the second player's move has value at most $4$ so \begin{align*} V\ge9(1)&+6(0)+6(1)+3(0)+6(1)+4(0)+6(1)+4(0)+4(1)+4(0)\\ &+3(1)+3(0)+3(1)+2(0)+2(1)+2(0)+2(1)+2(0)+2(1)\\ &+2(0)+2(1)+1(0)+1(1)+1(0)+1(1)=47>9\cdot5, \end{align*}But if the second player moves on D3, then the $3\times3$ square with center B4 will have at least $6$ ones if the first player keeps playing in that square, so we are done.
Attachments:
Ali-Seyedpour13
31.03.2023 14:40
This one was a bit messy for C1 The part that maximum is smaller than 7 was too easy but the proof for 6 was nasty