Competition problem — Combinatorics

Library / /103 of 224

Combinatorics Difficulty 6.0 AIME, harder Prove it Belarus

Given a $3n \times 3n$ table with one of two signs "+" or "-" in any of its cells. Per move one can replace the signs in all cells of some row (or of some column) by the opposite signs. At the beginning there is exactly one minus in the table (all other signs are pluses). After some moves the table with exactly 36 minuses is obtained.
Find all possible values of $n$ .

Solution

Answer $n = 3$ .

Note that if changing of signs is performed even number of times to some row (column), then it is equivalent that the operation is not applied at all. So we can assume that the operation is applied exactly once to some rows (columns), and is not applied to the remaining rows (columns). Let the operation be applied to $x$ rows and $y$ columns. Then the total number of the cells in which the signs are changed is equal to $c = 3n x + 3n y - 2 x y$ . We rewrite the equality as
$|3n - 2x| \cdot |3n - 2y| = |9n^2 - 2c| \quad (1)$

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.