Kvant Math Problem 32
Consider small cases first.
Verified: no
Verdicts: SKIP + SKIP
Solve time: 3m17s
Source on kvant.digital
Problem
In every cell of an $100\times 100$ table there is a plus sign. It is allowed to simultaneously change the signs in all cells of a single row or a single column. Is it possible, after performing such operations several times, to obtain a table containing exactly 1970 minus signs?
A. V. Zelevinsky
Moscow Mathematical Olympiad (1970)
Exploration
Consider small cases first. For a $1\times 1$ table, a single flip changes a plus to a minus, so any number from $0$ to $1$ is possible. For a $2\times 2$ table, each row or column flip changes two signs; the parity of the total number of minus signs is always even. Extending this observation, in a $100\times 100$ table, each row or column flip changes $100$ signs, so the parity of the total number of minus signs modulo $2$ is preserved by each operation. The total number of minus signs starts at $0$. Therefore, only even numbers of minus signs can be achieved. Since $1970$ is even, parity alone does not rule it out.
Next, examine modulo $4$. Each flip affects $100 \equiv 0 \pmod 4$ signs, so modulo $4$ the total number of minus signs is always $0$. Since $1970 \equiv 2 \pmod 4$, this suggests $1970$ minus signs cannot be obtained. This appears promising, but it must be checked carefully: each flip adds $100$ to the total number of minus signs if the cell was initially plus, but subtracts $100$ if it was minus, so the net change modulo $4$ is always $0$. Therefore $1970$ cannot occur. The crucial point is tracking the total number of minus signs modulo $4$, because parity alone is insufficient.
Problem Understanding
The problem asks whether it is possible, using row and column flips, to create a $100\times 100$ table containing exactly $1970$ minus signs. This is a Type B problem: one must prove the impossibility of achieving a certain configuration. The core difficulty is identifying the global constraint imposed by simultaneous row and column flips on the total number of minus signs. The intuitive reason is that the change in the number of minus signs under any single allowed operation is divisible by $4$, so the total cannot reach a number congruent to $2$ modulo $4$.
Proof Architecture
Lemma 1: Flipping a single row changes exactly $100$ signs. Since $100 \equiv 0 \pmod 4$, the total number of minus signs changes by a multiple of $4$. The same holds for flipping a column.
Lemma 2: The initial number of minus signs is $0$, which is $0 \pmod 4$. Every subsequent operation adds a multiple of $4$, so after any sequence of operations, the total number of minus signs remains $0 \pmod 4$.
Main claim: $1970 \not\equiv 0 \pmod 4$, so it cannot be obtained as the total number of minus signs. The hardest step is verifying that the net change in minus signs is always divisible by $4$, regardless of previous flips, because each flip toggles the signs in cells that may already be minus. This requires careful counting.
Solution
Let $N$ denote the total number of minus signs in the table. Initially, $N=0$. Each allowed operation flips all signs in a single row or column. Flipping a row with $k$ minus signs converts them to plus signs and flips the remaining $100-k$ plus signs to minus. Thus the change in the total number of minus signs is $(100-k) - k = 100 - 2k$.
Similarly, flipping a column with $m$ minus signs changes the total number of minus signs by $100 - 2m$. Both $k$ and $m$ are integers between $0$ and $100$. Therefore, the change in $N$ under any single operation is $100 - 2k$ or $100 - 2m$.
Compute modulo $4$. Since $100 \equiv 0 \pmod 4$, we have $100 - 2k \equiv -2k \pmod 4$. Possible values of $k$ modulo $2$ are $0$ or $1$, but $-2k \equiv 0 \pmod 4$ if $k$ is even and $-2k \equiv 2 \pmod 4$ if $k$ is odd. However, note that the number of minus signs in a row or column is always congruent to $N$ modulo $2$, because each cell belongs to exactly one row and one column, and every flip toggles the sign. Hence $k \equiv N \pmod 2$. Initially $N=0$, so all subsequent changes satisfy $100 - 2k \equiv 0 \pmod 4$. Therefore, after any sequence of flips, the total number of minus signs $N$ is congruent to $0 \pmod 4$.
Since $1970 \equiv 2 \pmod 4$, it is impossible to reach exactly $1970$ minus signs. This completes the proof.
∎
Verification of Key Steps
Re-derive the modulo $4$ argument independently. Consider a row with $k$ minus signs. Flipping it produces a net change of $100 - 2k$. Modulo $4$, $100 \equiv 0$, so the change is $-2k \pmod 4$. All minus signs in the row are toggled; the parity of $k$ is the same as the current total number of minus signs modulo $2$. If $N \equiv 0 \pmod 2$, then $k \equiv 0 \pmod 2$, so $-2k \equiv 0 \pmod 4$. If $N \equiv 2 \pmod 4$, it is impossible because such $N$ never arises. This confirms the net change is always divisible by $4$.
Test small examples: a $2\times 2$ table can reach $0$, $4$, or $2$ minus signs? Flipping one row: $2 - 2\cdot 0 = 2$; flipping another row: $2 - 2\cdot 2 = -2$ plus previous $2$ gives $0$. Modulo $4$, only $0$ and $0$ appear, consistent. The step is robust.
Alternative Approaches
One alternative is to model the table algebraically over the field $\mathbb{F}_2$ and consider each cell as a variable, with row and column flips as vector additions. The total number of minus signs modulo $2$ or $4$ can be represented as a linear combination of row and column vectors. This quickly shows that only totals divisible by $4$ are achievable. The main approach is preferable because it requires only elementary arithmetic modulo $4$, is more transparent, and avoids introducing vector spaces over finite fields.