2003 Indonesia MO Problems/Problem 4

Problem

Given a $19 \times 19$ matrix, where each element is valued $+1$ or $-1$. Let $b_i$ be the product of all elements at the $i^\text{th}$ row, and $k_j$ be the product of all elements at the $j^\text{th}$ column. Prove that:

\[b_1 + k_1 + b_2 + k_2 + \cdots + b_{19} + k_{19} \ne 0\]

Solution

In order for the sum to equal 0, $19$ rows or columns must have a product of $+1$ and the other $19$ rows or columns must have a product of $-1.$


On a given entry of a matrix, the product of its row and column is either $1$ or $-1.$ If an entry with a $+1$ is switched to a $-1,$ then the product of its row and the product of its column change signs. That means the number of rows and columns where the product equals $-1$ will either be always an even number or always an odd number since the number of rows and columns where the product equals $-1$ will change by either 2, 0, or -2.


In a grid where all $38$ entries are $+1$, there is no $b_i, k_j$ that is equal to $-1.$ Thus, the number of rows and columns where the product equal $-1$ will always be an even number. Since the number of rows and columns where the product equals $-1$ can not equal $19,$ we find that $\sum_{n=1}^{19} (b_n + k_n) \ne 0.$

Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.

See Also

2003 Indonesia MO (Problems)
Preceded by
Problem 3
1 2 3 4 5 6 7 8 Followed by
Problem 5
All Indonesia MO Problems and Solutions