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.

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

Page

Toolbox

Search

2003 Indonesia MO Problems/Problem 4

Problem

Solution

See Also