Track / Stage 6 / 379 of 400 #1379 of 2000

Problem 1379

National olympiad, first round

Combinatorics Difficulty 6.9 Find the answer

Consider a $m*n$ board. On each box there's a non-negative integrer number assigned. An operation consists on choosing any two boxes with $1$ side in common, and add to this $2$ numbers the same integrer number (it can be negative), so that both results are non-negatives.
What conditions must be satisfied initially on the assignment of the boxes, in order to have, after some operations, the number $0$ on every box?.

This one wants a proof. Work it on paper, read the official solution, then mark yourself honestly — the ladder only means something if the record is true.

Official solution

1. Coloring the Board:
- Consider a $m \times n$ board. Color the cells of the board like a chessboard, such that no two adjacent cells have the same color. Let's denote the sum of the numbers in the white cells as $S_w$ and the sum of the numbers in the black cells as $S_b$ .

2. Necessity of the Condition:
- In each operation, we choose two adjacent cells and add the same integer (which can be negative) to both cells. This operation does not change the difference between $S_w$ and $S_b$ because each operation affects one white cell and one black cell equally.
- If we want to reach a state where all cells have the number $0$ , then both $S_w$ and $S_b$ must be $0$ at the end. Therefore, initially, $S_w$ must be equal to $S_b$ .

3. Sufficiency of the Condition:
- Suppose $S_w = S_b$ initially. We need to show that it is possible to make all cells $0$ through a series of operations.
- We can clear the board one column at a time. Consider the first column. We can perform operations on adjacent cells within this column to make all cells in this column $0$ .
- After clearing the first column, we move to the next column and repeat the process. Continue this until only one column remains.
- When only one column remains, we clear the cells one by one until we are left with a $2 \times 1$ board. By the hypothesis, the sums of the numbers in the white and black cells are equal, so the two numbers we are left with are equal. We can then perform one final operation to make both numbers $0$ .

4. Conclusion:
- The initial condition that must be satisfied is that the sum of the numbers in the white cells must be equal to the sum of the numbers in the black cells.

The final answer is the sum of the numbers in the white cells must be equal to the sum of the numbers in the black cells.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.