A natural number is written in each square of an $ m \times n$ chess board. The allowed move is to add an integer $ k$ to each of two adjacent numbers in such a way that non-negative numbers are obtained. (Two squares are adjacent if they have a common side.) Find a necessary and sufficient condition for it to be possible for all the numbers to be zero after finitely many operations.
Problem
Source: IMO Shortlist 1989, Problem 19, ILL 64
Tags: combinatorics, invariant, Chessboard, algorithm, IMO Shortlist
19.07.2012 19:27
It is possible iff the sum of the number in white squares is the same as the sum in white square. It is possible -> Sums are equal: It is obvious that each move change of the same quantity the sum in black and in white. Then, cause at the end the two sum are both equal, they had to be equal also initially. Sums are equal -> it is possibile: Lemma Given three adjacent squares with $a,b,c$ it is possible to trasform them in $0,x,y$ doing only allowed moves.
Applying the lemma on each row (left to right) I succed in having all squares with zeroes apart from the last two columns. I repeat the same operation on both the last two columns (up to down) and now I have all zeroes except in the 2x2 square at bottom right corner. Now I only have to prove it for 1x1, 2x1,1x2,2x2 (the assumption that the sums are equal remains because doing the allowed operation doesn't change the difference between the sums). Since they are all easy cases the problem is finished. p.s. Sorry for my terrible english
11.06.2018 12:35
.........
11.06.2018 14:16
I'm going to rephrase dario2994's solution, as well as cleaning it up some. Color the board with alternating black and white colors like a chessboard. The claim is that it's possible to turn the whole board into zero if and only if the sum of numbers on black cells and the sum of numbers on white cells are equal. This is true even if there is no restriction that numbers must remain non-negative throughout. First, the proof that this is necessary: each time we do such move, we change both black and white sums by an equal amount, so their difference is an invariant. At the end they are equal (to zero), so at the beginning they must also be equal. Now, the proof that this is sufficient: Given any three squares A, B, C with B being adjacent to both A and C (note that A and C don't have to be on the same row/column), we can make A to be 0. Let $a, b, c$ be the contents on A, B, C respectively. Then add $a$ to both B and C, and subtract $a$ from both A and B, to obtain $0, b, a+c$ respectively. Note that the addition clearly doesn't break the rule that there is no negative cell, and the subtraction will also be fine because we have added $a$ to B. Now, there exists a Hamiltonian path across the grid (e.g. just take a "snake" pattern that covers all cells). Using the above, we can repeatedly apply it from an end to make all but two squares zero. (If the squares are $A_1, A_2, A_3, A_4, \ldots$, first make $A_1$ zero by applying the above to $A_1, A_2, A_3$; then make $A_2$ zero by applying $A_2, A_3, A_4$, and so on.) This leaves at most two nonzero squares at the other end of the path. Let the last two squares of the path be X and Y, with numbers $x,y$ on them. Since they are adjacent squares on the path, they are of different colors. By our assumption, black sum is equal to white sum; since all other numbers are zero, we must have $x = y$ in order for the sums to be equal. This means we can just subtract $x$ from both to have all zero.
21.11.2020 14:49
Apply the checkerboard colouring on the m by n chessboard. Let $ S_b$ and $S_w$ denote sum on white and black respectively. We claim that the only restriction needed is $S_b=S_w$ Suppose otherwise, notice that $S_b-S_w$ is invariant since adjacent squares are 1 black and 1 white. So if we were to reach all 0's we would need $S_b- S_w=0 $ contradiction. Now we shall provide a construction that works. Consider a random row. Take the topmost box in that row, suppose it contains the number $a$ and a number $b$ directly below it. Operate such $(a,b)->(0,b-a)$ continue repeating this process down the same column, until all the numbers in the column except for the bottommost box is 0. Do the same for the remaining columns. Now we should have that all rows are only 0's except for the last row. Now repeat what you did for the columns with the last row. This will leave us with all boxes 0 except for the bottom rightmost box. However, note that $S_b- S_w=0$ condition already gives us that the final box must be 0, so we are done.
26.07.2021 11:16
Cool problem. Let's tag the squares as $a_1, a_2, \ldots, _n$ The necessary conditions are: 1. $\sum a_i = 2k$, in other words the summation of the numbers must be even. 2. Let's color the board white and black. Let the summation of numbers in black and white cells be $S_b$ and $S_w$ respectively. Then, \[S_b = S_w\] First of all, let the total sum be $X$. After each move $X$ becomes, $x - 2k$. So, if $X$ is odd and $X$ can't be $0$, as desired Now, $S_b = S_w$. Suppose, $a, b, c$ be three adjacent squares and $c$ is closest to the left corner. If $b \geq c$, then we will remove $c$ from each. \[\left(a, b, c\right) = \left(a, b - c, 0 \right)\]If $c \geq b$, \[\left(a, b, c \right) \to \underbrace{\left(a + c - b, c, c \right)}_{\text{Adding $c - b$ to $a$ and $b$}} \to \left(a + c - b, 0, 0 \right)\]So, we will get $0$ in every squares, expect the most right two columns. We will do the same in those columns and will be left with $2$ adjacent corners, $x$ and $y$. And, they will be of different color, obviously. As, $S_b = S_w$, it is simple that $x = y$ and we are done.
26.07.2021 12:00
Nice ! Clearly $S_b=S_w$ since we are adding an integer to neighbouring cells. We claim this is sufficient as well. We proceed via induction on $m+n$. The base case can be easily handled. Take any board with perimeter $m+n+1$, and $S_b=S_w$. We want to prove that we can make all it’s entries zero at some point. Look at its first column. If $S_b=S_w$ in that column, we are done by our induction hypothesis. If not, WLOG $S_b > S_w$. Simply add $S_b-S_w$ to any white cell and the cell adjacent to it in the same row. Now we have $S_b=S_w$ in the first column, and hence the remaining board too. Applying the induction hypothesis separately, we are done
20.07.2022 21:28
First ISL Combo! (Although it's pretty old) Call $S_{b}$ and $S_{w}$ the sum of the black and white squares, respectively. Clearly, $S_{b}-S_{w}$ is an invariant. We have $S_{b}-S_{w}=0$ at the end, so we also need $S_{b}=S_{w}$ at the beginning. Claim: The above condition is sufficient. Proof: Our algorithm is as follows: Let $a_{1}, a_{2}, a_{3}$ be numbers in consecutive cells, with $a_{1}$ adjacent to $a_{2}$ and $a_{2}$ adjacent to $a_{3}$. We take cases based on which of $a_{1}$ and $a_{2}$ is greater. Case 1: $a_{1} \geq a_{2}$. In this case, we can add $a_{1}-a_{2}$ to $a_{2}$ and $a_{3}$. Case 2: $a_{1} \leq a_{2}$. In this case, we can add $-a_{1}$ to $a_{1}$ and $a_{2}$. Applying this to each row, we have everything canceling except the last two entries. However, these last two numbers are clearly equal, since $S_{b}=S_{w}$. $\square$ Since we have shown that this is sufficient, we are done. $\blacksquare$
24.12.2024 14:35
Really nice. Colour the grid using a chessboard colouring. Our answer is when, the total sum of the numbers on the black squares is the total sum of the numbers on the white squares. Observe that it is necessary since, when we perform a move (increasing any two by $k$), we have to perform on one black and one white, and we increase the total sum of the black squares by $k$ and the total sum of the white squares by $k$, so the difference between the black sum and the white sum is invariant. Since we want all to be $0$ at the end, the difference is $0$, so the black sum is equal to the white sum. To prove that it is sufficient, we first clear out all the rows barring the last two squares of each. We prove that we can do this. [asy][asy] size(5cm); draw((0, 0)--(3, 0)); draw((0, 1)--(3, 1)); draw((0, 0)--(0, 1)); draw((1, 0)--(1, 1)); draw((2, 0)--(2, 1)); draw((3, 0)--(3, 1)); label("$x_1$", (0.5, 0.5), align=NoAlign); label("$x_2$", (1.5, 0.5), align=NoAlign); label("$x_3$", (2.5, 0.5), align=NoAlign); [/asy][/asy] If $x_1 \geq x_2$, add sufficiently large $k$ to $x_2, x_3$ so that $x_2 > x_1$. Then, we may subtract $x_1$ from the left two squares leaving $0$ at $x_1$'s position. If $x_1 < x_2$, subtract $x_1$ from $x_1$, $x_2$ leaving $0$ behind in $x_1$'s position. Repeatedly use this strategy as you move rightward in a row, leaving behind the last two squares of each row. Use the same strategy for columns, and we end up with a $2x2$ square, and after noticing the black sum in this square is equal to the white sum in this square, it's easy to finish.