Maths Olympiad Prep

Library / Slovenian Mathematical Olympiad /62 of 68

Slovenian Mathematical Olympiad, 2008

Combinatorics Difficulty 6.7 National Olympiad Prove it Slovenia

On every square of an n×nn \times n chessboard we write one of the numbers 11 or −1-1. Let aka_k be the product of all numbers in the kthk^{\text{th}} row and blb_l be the product of all numbers in the lthl^{\text{th}} column. Assuming n=2007n = 2007, can we choose the numbers in such a way that the sum
a1+a2+⋯+an+b1+b2+⋯+bn a_1 + a_2 + \dots + a_n + b_1 + b_2 + \dots + b_n
will be zero? What about n=2008n = 2008?

Solution

If n=2008n = 2008 fill the first row of the board with −1-1 and all other squares with 11. Then ak=1a_k = 1 for all kk and bl=−1b_l = -1 for all ll, so
a1+a2+⋯+a2008+b1+b2+⋯+b2008=1+⋯+1+(−1)+⋯+(−1)=0. a_1 + a_2 + \dots + a_{2008} + b_1 + b_2 + \dots + b_{2008} = 1 + \dots + 1 + (-1) + \dots + (-1) = 0.

Now, let n=2007n = 2007. We will show that we cannot choose the numbers so that
a1+a2+⋯+a2007+b1+b2+⋯+b2007=0. a_1 + a_2 + \dots + a_{2007} + b_1 + b_2 + \dots + b_{2007} = 0.
Assume, on the contrary, that this can be done. Obviously, each of aka_k and blb_l is either 11 or −1-1. Let tt denote the number of negative elements of the set {a1,…,a2007}\{a_1, \dots, a_{2007}\} and let ss be the number of negative elements in {b1,…,b2007}\{b_1, \dots, b_{2007}\}. Then
a1+⋯+a2007=−t+(2007−t)=2007−2t a_1 + \dots + a_{2007} = -t + (2007 - t) = 2007 - 2t
and
b1+⋯+b2007=−s+(2007−s)=2007−2s. b_1 + \dots + b_{2007} = -s + (2007 - s) = 2007 - 2s.
This implies
0=a1+a2+⋯+a2007+b1+b2+⋯+b2007=2007−2t+2007−2s, 0 = a_1 + a_2 + \dots + a_{2007} + b_1 + b_2 + \dots + b_{2007} = 2007 - 2t + 2007 - 2s,
so s+t=2007. \text{so } s + t = 2007.
How many −1-1s are there on the board? If ai=−1a_i = -1, then the ithi^{\text{th}} row contains an odd number of −1-1s. If ai=1a_i = 1, then this number is even. So, the parity of the number of −1-1s is the same as the parity of tt. A similar argument for the columns shows that the parity of the total number of −1-1s is the same as the parity of ss. So, ss and tt have the same parity, which contradicts the equation s+t=2007s + t = 2007 from above.

When n=2007n = 2007 we cannot fill the board with 11s and −1-1s so that
a1+a2+⋯+a2007+b1+b2+⋯+b2007=0. a_1 + a_2 + \dots + a_{2007} + b_1 + b_2 + \dots + b_{2007} = 0.

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.