Library / All-Soviet-Union Mathematical Olympiad /61 of 185

All-Soviet-Union Mathematical Olympiad

Combinatorics Difficulty 4.8 AIME Prove it Soviet Union

Problem:
Given an $n \times n$ array of numbers. $n$ is odd and each number in the array is $1$ or $-1$ . Prove that the number of rows and columns containing an odd number of $-1$ s cannot total $n$ .

Solution

Solution:
If we change a $-1$ to $1$ , we affect the total number of rows and columns (containing an odd number of $-1$ s) by $0$ , $2$ or $-2$ . After changing all the $-1$ s we have total of $0$ . Hence the starting total must be even. So it cannot be $n$ .

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

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