Maths Olympiad Prep

Library / /41 of 45

, 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+(2007t)=20072t a_1 + \dots + a_{2007} = -t + (2007 - t) = 2007 - 2t
and
b1++b2007=s+(2007s)=20072s. b_1 + \dots + b_{2007} = -s + (2007 - s) = 2007 - 2s.
This implies
0=a1+a2++a2007+b1+b2++b2007=20072t+20072s, 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,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.