Maths Olympiad Prep

Library / /20 of 22

Combinatorics Difficulty 6.5 National Olympiad Prove it Romania

Let n3n \ge 3 be a positive integer. Consider an n×nn \times n square. In each cell of the square, one of the numbers from the set M={1,2,,2n1}M = \{1, 2, \dots, 2n-1\} is to be written. One such filling is called "good" if, for every index ii, 1in1 \le i \le n, row no. ii and column no. ii, together, contain all the elements of MM.
a) Prove that there exists n3n \ge 3 for which a good filling exists.
b) Prove that for n=2017n = 2017 there is no good filling of the n×nn \times n square.

Solution

a) For n=4n = 4 the filling below is good.

1245
3164
7512
6731

b) We prove that there is no good filling of an n×nn \times n square if nn is odd. Assume the contrary to be true. Then, for some odd number nn, we have that, for every index ii, 1in1 \le i \le n, the row no. ii and the column no. ii contain, together, exactly once, each element of MM. If we denote by aija_{ij} the number situated on row no. ii and column no. jj, i,j{1,2,,n}i, j \in \{1, 2, \dots, n\}, and Si=ai1+ai2++ain+a1i+a2i++aniS_i = a_{i1} + a_{i2} + \dots + a_{in} + a_{1i} + a_{2i} + \dots + a_{ni} in which the term aiia_{ii} only appears once, then each element of MM must appear in nn such sums. But if aij=k,ija_{ij} = k, i \neq j, then the element kk will contribute to both SiS_i and SjS_j. Thus, any number that is not situated on the main diagonal contributes to two sums. But in total, there is an odd number of sums, so each element of MM must appear an odd number of times on the main diagonal. Thus, each element of MM needs to appear at least once on the main diagonal, which is not possible because there are 2n12n-1 elements in MM and only nn places on the diagonal.

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 reproduced verbatim; metadata (topic, difficulty) added by this project.