Maths Olympiad Prep

Library / /186 of 520

Combinatorics Difficulty 6.7 National olympiad Find the answer

Let n2n\ge 2 be a natural number.
An n×nn \times n grid is drawn on a blackboard and each field with one of the numbers 1-1 or +1+1 labeled. Then the nn row and also the nn column sums calculated and the sum SnS_n of all these 2n2n sums determined.
(a) Show that for no odd number nn there is a label with Sn=0S_n = 0.
(b) Show that if nn is an even number, there are at least six different labels with Sn=0S_n = 0.

Solution

### Part (a)
1. Let a a be the number of fields labeled with +1 +1 and b b be the number of fields labeled with 1 -1 . Then we have:
a+b=n2 a + b = n^2
2. The sum Sn S_n of all the row and column sums is calculated. Each field in the grid is counted twice in Sn S_n (once in its row sum and once in its column sum). Therefore, we can express Sn S_n as:
Sn=2a2b=2(ab) S_n = 2a - 2b = 2(a - b)
3. For Sn S_n to be zero, we need:
2(ab)=0    ab=0    a=b 2(a - b) = 0 \implies a - b = 0 \implies a = b
4. Since n n is odd, n2 n^2 is also odd. Therefore, a+b=n2 a + b = n^2 is odd. If a=b a = b , then a+b=2a a + b = 2a would be even, which contradicts the fact that n2 n^2 is odd.
5. Hence, for no odd number n n , there is a labeling such that Sn=0 S_n = 0 .

\blacksquare

### Part (b)
1. If n n is even, then n2 n^2 is also even. We need to show that there are at least six different labelings such that Sn=0 S_n = 0 .
2. For Sn=0 S_n = 0 , we need a=b a = b . Since n2 n^2 is even, we can have a=b=n22 a = b = \frac{n^2}{2} .
3. The number of ways to choose n22\frac{n^2}{2} fields out of n2 n^2 fields to label with 1 -1 is given by the binomial coefficient:
(n2n22) \binom{n^2}{\frac{n^2}{2}}
4. We need to show that this number is at least 6 for n2 n \geq 2 . For n=2 n = 2 , we have:
(42)=6 \binom{4}{2} = 6
5. For n>2 n > 2 , (n2n22) \binom{n^2}{\frac{n^2}{2}} is even larger. Therefore, there are at least six different labelings such that Sn=0 S_n = 0 .

\blacksquare

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: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.