Competition problem — Combinatorics

Library / /14 of 61

Combinatorics Difficulty 5.7 AIME, harder Prove it Greece

At each square of a $2007 \times 2007$ chessboard we put one of the numbers $1$ or $-1$ . We denote by $A_i$ the product of the numbers of the $i$ -row, $i=1,2,\ldots,2007$ and by $B_j$ the product of the numbers of the $j$ -column, $j=1,2,\ldots,2007$ . Prove that:

$A_1 + A_2 + \dots + A_{2007} + B_1 + B_2 + \dots + B_{2007} \neq 0.$

Solution

We have $A_1A_2\dots A_{2007} \cdot B_1B_2\dots B_{2007} = 1$ , because each element of the table appears two times, one in a row and one in a column, and so the number of $(-1)$ in the product $A_1A_2\dots B_{2007}$ is even, say, for example $2k$ .

Therefore the number of $+1$ will be $4014 - 2k$ .

If $(4014-2k)(1) + 2k(-1) = 0 \Rightarrow 4014 = 4k$ , which is absurd, because $4$ does not divide $4004$ . Hence $A_1 + A_2 + \dots + A_{2007} + B_1 + B_2 + \dots + B_{2007} \neq 0$ .

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.