$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
Davsch
05.01.2024 12:46
Simply arrange all marbles along one of the two main diagonals.
We claim that $k=2023$ is the largest such value. Part a) shows that $k\leq 2023$. We have to show that there is a way to move a marble if $k<2024$. For this, assume there are $2024-n$ marbles placed on the grid, where $n\geq 1$, such that no such move is possible.
Since there are less than $2024$ marbles, there will always be columns and rows of the grid which contain no marbles, which we will call free. Assume there are $p$ free columns and $q$ free rows. Without loss of generality, we may assume that $p\geq q$, since otherwise we could reflect the grid along a diagonal.
Consider now the $p$ free columns.
Claim 1. No two free rows are adjacent.
Proof. Assume we have a block of free rows with size at least $2$. Since this block can't be the entire grid, there must a marble in a cell adjacent to this block. However, then we could simply move this marble inside the block and obtain a valid arrangement.
Claim 2. The leftmost column is not free.
Proof. Assume it was. Then we could simply move one of the leftmost marbles one step to the left.
Together, the two claims imply that for each of the $p$ free columns, the column immediately to the left is not free and contains some marble. Clearly, if a marble positioned at $(x,y)$ is to the left of a free column, then there must also be a marble placed at $(x+2,y)$, as otherwise we could move the original marble to $(x+1,y)$.
Since we have $p$ free columns, there must be at least $p$ such pairs of marbles whose "distance" is the vector $(2,0)$. Note that any two such marbles are located in the same row. Hence, these $2p$ marbles* together use up $p$ rows and the remaining $2024-n-2p$ marbles can use up at most $2024-n-2p$ rows. This shows that at most $p+2024-n-2p=2024-n-p$ rows have marbles, i.e. at least $p+n$ rows are free. This is a contradiction since we assumed $p\geq q$.
*Note: It is possible to have a chain where the marbles are positioned like $(x,y),(x+2,y),(x+4,y)$ (or even longer chains). Then, the number of marbles involved in these pairs will be less than $2p$, but the number of rows used up also goes down by $1$, so the inequality remains valid.
zenkichihitoyoshi
05.01.2024 18:05
Davsch wrote:
Simply arrange all marbles along one of the two main diagonals.
We claim that $k=2023$ is the largest such value. Part a) shows that $k\leq 2023$. We have to show that there is a way to move a marble if $k<2024$. For this, assume there are $2024-n$ marbles placed on the grid, where $n\geq 1$, such that no such move is possible.
Since there are less than $2024$ marbles, there will always be columns and rows of the grid which contain no marbles, which we will call free. Assume there are $p$ free columns and $q$ free rows. Without loss of generality, we may assume that $p\geq q$, since otherwise we could reflect the grid along a diagonal.
Consider now the $p$ free columns.
Claim 1. No two free rows are adjacent.
Proof. Assume we have a block of free rows with size at least $2$. Since this block can't be the entire grid, there must a marble in a cell adjacent to this block. However, then we could simply move this marble inside the block and obtain a valid arrangement.
Claim 2. The leftmost column is not free.
Proof. Assume it was. Then we could simply move one of the leftmost marbles one step to the left.
Together, the two claims imply that for each of the $p$ free columns, the column immediately to the left is not free and contains some marble. Clearly, if a marble positioned at $(x,y)$ is to the left of a free column, then there must also be a marble placed at $(x+2,y)$, as otherwise we could move the original marble to $(x+1,y)$.
Since we have $p$ free columns, there must be at least $p$ such pairs of marbles whose "distance" is the vector $(2,0)$. Note that any two such marbles are located in the same row. Hence, these $2p$ marbles* together use up $p$ rows and the remaining $2024-n-2p$ marbles can use up at most $2024-n-2p$ rows. This shows that at most $p+2024-n-2p=2024-n-p$ rows have marbles, i.e. at least $p+n$ rows are free. This is a contradiction since we assumed $p\geq q$.
*Note: It is possible to have a chain where the marbles are positioned like $(x,y),(x+2,y),(x+4,y)$ (or even longer chains). Then, the number of marbles involved in these pairs will be less than $2p$, but the number of rows used up also goes down by $1$, so the inequality remains valid.
We have to determine the largest value of $k$, and there may exist a value $k > 2023$ that satisfies question $b$
khanh20
05.01.2024 18:17
Davsch wrote:
Solution to a)Simply arrange all marbles along one of the two main diagonals.
Solution to b)We claim that $k=2023$ is the largest such value. Part a) shows that $k\leq 2023$. We have to show that there is a way to move a marble if $k<2024$. For this, assume there are $2024-n$ marbles placed on the grid, where $n\geq 1$, such that no such move is possible.
Since there are less than $2024$ marbles, there will always be columns and rows of the grid which contain no marbles, which we will call free. Assume there are $p$ free columns and $q$ free rows. Without loss of generality, we may assume that $p\geq q$, since otherwise we could reflect the grid along a diagonal.
Consider now the $p$ free columns.
Claim 1. No two free rows are adjacent.
Proof. Assume we have a block of free rows with size at least $2$. Since this block can't be the entire grid, there must a marble in a cell adjacent to this block. However, then we could simply move this marble inside the block and obtain a valid arrangement.
Claim 2. The leftmost column is not free.
Proof. Assume it was. Then we could simply move one of the leftmost marbles one step to the left.
Together, the two claims imply that for each of the $p$ free columns, the column immediately to the left is not free and contains some marble. Clearly, if a marble positioned at $(x,y)$ is to the left of a free column, then there must also be a marble placed at $(x+2,y)$, as otherwise we could move the original marble to $(x+1,y)$.
Since we have $p$ free columns, there must be at least $p$ such pairs of marbles whose "distance" is the vector $(2,0)$. Note that any two such marbles are located in the same row. Hence, these $2p$ marbles* together use up $p$ rows and the remaining $2024-n-2p$ marbles can use up at most $2024-n-2p$ rows. This shows that at most $p+2024-n-2p=2024-n-p$ rows have marbles, i.e. at least $p+n$ rows are free. This is a contradiction since we assumed $p\geq q$.
*Note: It is possible to have a chain where the marbles are positioned like $(x,y),(x+2,y),(x+4,y)$ (or even longer chains). Then, the number of marbles involved in these pairs will be less than $2p$, but the number of rows used up also goes down by $1$, so the inequality remains valid.
Click to reveal hidden textThe official solution proves that $k_{\text{max}}=4045$
wassupevery1
05.01.2024 21:56
Insane. Writeup was annoying.
Place the cells on the main diagonal. We are done.
The answer is $k=2 \cdot 2023 - 1 = \boxed{4045}$.
First, note that, if the a placement satisfies the problem conditions, then $k \leq \frac{2024^2}{2}$.
Proof that k>=4046 failTo prove that all $4046 \leq k \leq \frac{2024^2}{2}$ fail, consider the following figure (This is for $n=8$, we can easily generalize)
Place the first $4046$ marbles on the spots marked $X$, then on each diagonal, starting with the diagonal with the most cells, place the marbles onto that. If eventually it is not enough, place them on the main diagonal. This is always possible because once impossible to place them on the diagonals, there are less than $2022$ marbles left.
Now, since each diagonal is filled, moving the marbles will give a new placement adjacent to a marble in either the upper diagonal, current diagonal, or lower one. This means all $k \geq 4046$ fail.
Proof that k=4045 worksNow assume $k=4045$, and assume there exists a configuration such that we cannot move one of the placed marbles onto one of its neighboring cells and the new arrangement still satisfies the conditions above. Color the board like the chessboard pattern, with the top-left corner filled colored white.
Let $a, b$ be the number of cells such that there is a marble on the cell and it is colored white, black respectively.
By symmetry, WLOG assume that $a<b$. Then $0 \leq a \leq 2022$.
If a != 0If $a \neq 0$, consider the diagonals which consists of only white cells as follows (The following is for $n=8$, which can easily be generalized to $2024$).
There are $2023$ such diagonals, so there must be at least one that is empty. In addition, there is a diagonal containing at least one marble, so we consider the empty diagonal that is adjacent to the non-empty diagonal. WLOG, assume the diagonals are the following, with the red denoting an empty diagonal, and the blue one denoting a non-empty diagonal (the figure is for $n=10$, and WLOG we choose the non-empty cell to be $X_1$. Similar cases are proved similarly).
Consider a marble placed on cell $X_1$. If we move $X_1$ upwards, then $X_1$ is adjacent to $X_2$ and two empty cells. This implies cell $X_2$ must contain a marble. We repeat this until we reach the top. This implies cell $Y$ contains a marble. But moving $Y$ upwards gives the marble to be adjacent to empty cells, contradiction.
If a=0If $a=0$, meaning that $b=4045$, consider the black diagonals now, which is labelled as follows (The following is an example for $n=10$).
If there is one diagonal having cells with no marbles, we repeat the same argument on the case $a \neq 0$ to finish.
So consider the $2022$ diagonals, each containing at least $3$ cells. Note that $4045-2=4043 < 2 \cdot 2022$, so there must be a diagonal containing exactly one cell having a marble. Furthermore, $4043>2022$, so there must be a diagonal containing at least two cells having a marble. So consider the following figure, and WLOG assume the red diagonal means the diagonal containing exactly one marble, the blue diagonal means the diagonal containing at least 2 marbles, adjacent to each other.
Consider the only cell containing the marble, WLOG $Y$, and a cell $Z$ in the blue diagonal such that $Y, Z$ share a vertex. Since the blue consists of at least two marked marbles, there must be a cell, different from $Z$, containing a marble. WLOG, assume it is $X_1$. We repeat the same argument in the case $a=0$ to prove that $T$ has a marble, but moving it upwards gives a configuration that satisfies the problem, contradiction.
So we have considered all cases which all lead to contradiction, so the problem is solved.
Ntafiys
09.01.2024 10:50
wassupevery1 wrote: Insane. Writeup was annoying.
Place the cells on the main diagonal. We are done.
The answer is $k=2 \cdot 2023 - 1 = \boxed{4045}$.
First, note that, if the a placement satisfies the problem conditions, then $k \leq \frac{2024^2}{2}$.
Proof that k>=4046 failTo prove that all $4046 \leq k \leq \frac{2024^2}{2}$ fail, consider the following figure (This is for $n=8$, we can easily generalize)
Place the first $4046$ marbles on the spots marked $X$, then on each diagonal, starting with the diagonal with the most cells, place the marbles onto that. If eventually it is not enough, place them on the main diagonal. This is always possible because once impossible to place them on the diagonals, there are less than $2022$ marbles left.
Now, since each diagonal is filled, moving the marbles will give a new placement adjacent to a marble in either the upper diagonal, current diagonal, or lower one. This means all $k \geq 4046$ fail.
Proof that k=4045 worksNow assume $k=4045$, and assume there exists a configuration such that we cannot move one of the placed marbles onto one of its neighboring cells and the new arrangement still satisfies the conditions above. Color the board like the chessboard pattern, with the top-left corner filled colored white.
Let $a, b$ be the number of cells such that there is a marble on the cell and it is colored white, black respectively.
By symmetry, WLOG assume that $a<b$. Then $0 \leq a \leq 2022$.
If a != 0If $a \neq 0$, consider the diagonals which consists of only white cells as follows (The following is for $n=8$, which can easily be generalized to $2024$).
There are $2023$ such diagonals, so there must be at least one that is empty. In addition, there is a diagonal containing at least one marble, so we consider the empty diagonal that is adjacent to the non-empty diagonal. WLOG, assume the diagonals are the following, with the red denoting an empty diagonal, and the blue one denoting a non-empty diagonal (the figure is for $n=10$, and WLOG we choose the non-empty cell to be $X_1$. Similar cases are proved similarly).
Consider a marble placed on cell $X_1$. If we move $X_1$ upwards, then $X_1$ is adjacent to $X_2$ and two empty cells. This implies cell $X_2$ must contain a marble. We repeat this until we reach the top. This implies cell $Y$ contains a marble. But moving $Y$ upwards gives the marble to be adjacent to empty cells, contradiction.
If a=0If $a=0$, meaning that $b=4045$, consider the black diagonals now, which is labelled as follows (The following is an example for $n=10$).
If there is one diagonal having cells with no marbles, we repeat the same argument on the case $a \neq 0$ to finish.
So consider the $2022$ diagonals, each containing at least $3$ cells. Note that $4045-2=4043 < 2 \cdot 2022$, so there must be a diagonal containing exactly one cell having a marble. Furthermore, $4043>2022$, so there must be a diagonal containing at least two cells having a marble. So consider the following figure, and WLOG assume the red diagonal means the diagonal containing exactly one marble, the blue diagonal means the diagonal containing at least 2 marbles, adjacent to each other.
Consider the only cell containing the marble, WLOG $Y$, and a cell $Z$ in the blue diagonal such that $Y, Z$ share a vertex. Since the blue consists of at least two marked marbles, there must be a cell, different from $Z$, containing a marble. WLOG, assume it is $X_1$. We repeat the same argument in the case $a=0$ to prove that $T$ has a marble, but moving it upwards gives a configuration that satisfies the problem, contradiction.
So we have considered all cases which all lead to contradiction, so the problem is solved.
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.
YaoAOPS
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]