Maths Olympiad Prep

Library / /6 of 7

Combinatorics Difficulty 6.7 National olympiad Prove it Austria

Let n2n \ge 2 be an integer.
We draw an n×nn \times n grid on a board and label each box with either the number 1-1 or the number 11. Then we calculate the sum of each of the nn rows and the sum of each of the nn columns and determine the sum SS of these 2n2n sums.

a. Show that there does not exist a labelling of the grid with S=0S = 0 if nn is odd.

b. Show that there exist at least six different labellings with S=0S = 0 if nn is even.

Solution

As each number of the grid appears exactly once in the sum of all columns of the grid and the same holds for the sum of all rows, we get that SS is twice the sum of all labels of the boxes of the n×nn \times n grid. Therefore, S=0S = 0 holds if and only if the sum of all labels of the boxes vanishes, or equivalently, if the number of labels +1+1 equals the number of labels 1-1. We call such a labelling admissible.

a. If nn is odd, the sum of all labels is also odd, because it is a sum of an odd number of odd labels. Thus there cannot be an admissible labelling in this case.

b. If nn is even, we write n=2kn = 2k for some integer kk. The admissible labellings can be constructed as follows: Choose exactly half of the n2=4k2n^2 = 4k^2 boxes arbitrarily and label each of them with +1+1. The remaining boxes are labelled with 1-1.
Thus there are exactly ak:=(4k22k2)a_k := \binom{4k^2}{2k^2} admissible labellings of a 2k×2k2k \times 2k grid.
We have a1=(42)=6a_1 = \binom{4}{2} = 6 and it is easily seen that aka_k is increasing in kk: if 1k<k1 \le k' < k, each admissible labelling of any 2k×2k2k' \times 2k' subgrid can be extended to an admissible labelling of the 2k×2k2k \times 2k grid by choosing half of the extra 4k24k24k^2 - 4k'^2 boxes and labelling each of them with +1+1 and the remaining boxes with 1-1. Therefore, ak6a_k \ge 6 for all kk.

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.