$k$ marbles are placed onto the cells of a $2024 \times 2024$ grid such that each cell has at most one marble and there are no two marbles are placed onto two neighboring cells (neighboring cells are defined as cells having an edge in common). a) Assume that $k=2024$. Find a way to place the marbles satisfying the conditions above, such that moving any placed marble to any of its neighboring cells will give an arrangement that does not satisfy both the conditions. b) Determine the largest value of $k$ such that for all arrangements of $k$ marbles satisfying the conditions above, we can move one of the placed marble onto one of its neighboring cells and the new arrangement satisfies the conditions above.
Problem
Source: 2024 Vietnam National Olympiad - Problem 4
Tags: combinatorics
05.01.2024 12:46
05.01.2024 18:05
Davsch wrote:
We have to determine the largest value of $k$, and there may exist a value $k > 2023$ that satisfies question $b$
05.01.2024 18:17
05.01.2024 21:56
Insane. Writeup was annoying.
09.01.2024 10:50
wassupevery1 wrote: Insane. Writeup was annoying.
Solution has some omissions, and the given examples lack generality. When the cell number of empty diagonal is less than non-empty diagonal, it is not possible to find a suitable operation when non-empty diagonals are completely filled. Additional reasoning is needed in this case.
15.06.2024 09:47
Here's a full classification of which $k$ work for part (b). We claim that $k \le 2023, 2025 \le k \le 4045$ work. Proof that $k = 2024$ does not work. This is part (a). Fill in the main diagonal lol. Proof that $k \ge 4046$ do not work. Note that $k \le \frac{2024^2}{2}$ by constraints. Take a $4046$ token configuration which is a diagonal rectangle which is one off the main diagonal. Then greedily fill largest diagonals of the same parity, place excess in the middle of the diagonal rectangle. [asy][asy] size(10cm); int N = 10; for (int i = 0; i <= N; ++i) { draw((0,i)--(N,i)); draw((i,0)--(i,N)); } for (int i = 0; i <= N-1; ++i) { for (int j = 0; j <= N-1; ++j) { if ((i + j) % 2 == 0) { if (((i - j) * (i - j) == 4) || (i + j) == 2 || (i + j) == 2*N-4) { fill(shift(i,j)*unitsquare, white+blue); } else if (i == j) { fill(shift(i,j)*unitsquare, white+red); } else { fill(shift(i,j)*unitsquare, white+green); } } } } [/asy][/asy] In order, fill blue, then green, then red. Proof $k \le 2023$ work. FTSOC suppose not. Take the convex hull of tokens. By extremal it follows that the edges of the convex hull consist of entire diagonals $A_1A_2, A_3A_4, A_5A_6, A_7A_8$ such that $A_2A_3$ is the opposite border of the board as $A_6A_7$. Note that these diagonals are disjoint else we get a path of length $2024$. Claim: There exists a path between any two tokens $a, b$ such that $t_0 = a, t_n = b$ and the taxicab distance between $t_i, t_{i+1}$ is $2$. Proof. Suppose not, then spam along both tokens up and down to get two disjoint chains of length $1012$, contradictions. $\blacksquare$ Claim: There exists a path between $A_2$ and $A_3$ such that each move between adjacent $A_2$ and $A_3$ has nonzero vertical component in direction $A_2$, $A_3$. Proof. Spam going towards $A_3$ from $A_2$ and spam going towards $A_2$ from $A_3$. These paths then must intersect. $\blacksquare$ Then the path from $A_1$ to $A_2$ and $A_5$ to $A_6$ can't intersect else that implies a path of length $2024$. Now take paths $A_8-A_1-A_2-A_3$, $A_4-A_5-A_6-A_7$ which are disjoint, and both have length at least $1012$, for a total at least $2024$, contradiction. [asy][asy] draw(unitsquare); draw((0.3,0)--(0,0.3), blue); draw((0.8,0)--(1,1-0.8), blue); draw((0.7,1)--(1,0.7), blue); draw((0.4,1)--(0,1-0.4), blue); draw((0,1-0.4)..(0.2,0.5)..(0,0.3), green); draw((1,0.7)..(0.8,0.5)..(1,1-0.8), green); dot("$A_1$", (0, 1-0.4), W); dot("$A_2$", (0, 0.3), W); dot("$A_3$", (0.3, 0), S); dot("$A_4$", (0.8, 0), S); dot("$A_5$", (1, 1-0.8), E); dot("$A_6$", (1, 0.7), E); dot("$A_7$", (0.7, 1), N); dot("$A_8$", (0.4, 1), N); [/asy][/asy] Proof $2025 \le k \le 4045$ work. FTSOC suppose this is possible. We show that $k \ge 4046$, contradiction. We also give a diagram for the $n = 10$ case. As above, all squares must be a subset of the checkerboard pattern, else you can force two edges to touch by taking a vertical line through one of them and a horizontal one of an opposite parity. Consider the diagonals from top left to bottom right of the same parity as the checkerboard and WLOG let the bottom left square be part of the checkerboard. Call the diagonal from top left to bottom right the divider and the other main diagonal the snake. We once again get two distinct minimal diagonals (draw in blue and potentially corners) such that one lies below the divider and one lies above the divider. Claim: For each diagonal between these two diagonals, at least two squares are filled in. Proof. If the minimal diagonals isn't a single corner block, then inductively fill in diagonals starting from that diagonal to get the result (consider the extremal pieces in the diagonal). Else, WLOG suppose the bottom right minimal diagonal is a single corner. If the diagonal above this one has two or three elements, we induct as before. Else, it follows that the next square in the snake is the only square filled in. This must keep occuring until either we get that all the squares directly below the divider are empty, which forces only the snake to be filled in, contradiction, or we get a case where for some diagonal below the divider, all squares in it but at most one are filled. Then clear everything below this diagonal and move one token if necessary to fill in the diagonal, and repeat the process. $\blacksquare$ We draw in the relevant squares in light blue. As such, if we project the minimal diagonals to the edge (draw in red), then all diagonals but the corners have $2$, and the corners have $1$. This gives at least $2 \cdot 2024 - 2 = 4046$ squares, contradiction. [asy][asy] size(10cm); int N = 10; for (int i = 0; i <= N; ++i) { draw((0,i)--(N,i)); draw((i,0)--(i,N)); } for (int i = 0; i <= N-1; ++i) { for (int j = 0; j <= N-1; ++j) { if ((i + j) == 4 || (i + j) == 2*N-6) { fill(shift(i,j)*unitsquare, white+blue); } else if ((i - j) == -6 | (i - j) == 6) { fill(shift(i,j)*unitsquare, white+lightblue); } } } pen gr = lightgray; fill(shift(7,5)*unitsquare, gr); fill(shift(5,7)*unitsquare, gr); fill(shift(5,3)*unitsquare, gr); fill(shift(5,5)*unitsquare, gr); fill(shift(7,3)*unitsquare, gr); fill(shift(5,1)*unitsquare, gr); fill(shift(3,3)*unitsquare, gr); fill(shift(2,4)*unitsquare, gr); fill(shift(2,6)*unitsquare, gr); fill(shift(1,5)*unitsquare, gr); fill(shift(3,7)*unitsquare, gr); fill(shift(4,4)*unitsquare, gr); pen lr = white+red; fill(shift(0,0)*unitsquare, lr); fill(shift(2,0)*unitsquare, lr); fill(shift(0,2)*unitsquare, lr); fill(shift(N-0-1,N-0-1)*unitsquare, lr); fill(shift(N-2-1,N-0-1)*unitsquare, lr); fill(shift(N-0-1,N-2-1)*unitsquare, lr); [/asy][/asy]