One positive integer is written in each $1 \times 1$ square of the $m \times n$ board. The following operations are allowed : (1) In an arbitrarily selected row of the board, all numbers should be reduced by $1$. (2) In an arbitrarily selected column of the board, double all the numbers. Is it always possible, after a final number of steps, for all the numbers written on the board to be equal to $-1$? (Explain the answer.)
Problem
Source: 2020 1st Memorial Mathematical Contest "Aleksandar Blazhevski-Cane" p2
Tags: combinatorics
01.05.2021 09:33
When you say, "Is it always possible, after a final number of steps, for all the numbers written on the board to be equal to $-1$?", is it enough to display a counter example, and explain why it is one, or do I have to find necessary and sufficient conditions for being able to create an all $-1$ board? I will anyways give a type of counterexample. First since we want counter examples let $\gcd(m, n) = d> 1$ and let $\varepsilon$ be a primitive root of unity with order $d$. Assign to each square $(i, j)$ the number $k\cdot \varepsilon^{i+j}$, where $k$ is the number written in that square. After this it is trivial to note that after any operation the sum of all assigned quantities is an invariant and so if it is not zero initially(such a case can be easily constructed), it remains nonzero throughout. So we could never have all numbers equal to $-1$ as in such a case the sum of all the assigned numbers would be zero. EDIT: This is wrong, the doubling operation is not an Invariant step.
01.05.2021 16:30
The answer is Yes! To get all the numbers to -1, we first get all the numbers to 0. Then minus every row by one and we're done. Notice that once we have a whole row with the number 0, no matter how we double the numbers, they're still 0. Hence, we just need to proof that for every row with all numbers positive, we can get all the numbers in that row to 0 without getting the rest of the numbers $\le 0$ Regard row 1 (1) First, we get the smallest 2 numbers in row 1 equal. Suppose the smallest numbers are x and y ($x<y$) we double the row that contains x again and again until $2y\ge x\ge y$. Suppose x = y+t Then reduce row 1 by $y-t$ As y is now the smallest number, every number is positive, and we change x and y into 2t and t we times the column that contains t by 2. Hence, we equalized two numbers without getting any other number $\le 0$ (2) Now we regard the two columns that contain the two number we've just equalized as a whole. Which means whenever we double the first column, we must double the other column at the same time. Then, we get another 2 numbers to be the same and then regard them as a whole…… Finally, we can get all the numbers in row 1 to be the same. And then we minus the numbers in the first row to 0. (3) Simillarly, we can get every row to 0 (4) Minus every row by 1, and we're done!