Maths Olympiad Prep

Library / /66 of 101

Combinatorics Difficulty 6.5 National olympiad Prove it Estonia

Is there a positive integer nn for which it is possible to write a number 1-1, 00 or 11 into each cell of an n×nn \times n table in such a way that every integer from n-n to nn occurs at least once among the row sums, column sums and the two sums of the numbers on one long diagonal? If yes then find the least such nn.

Solution

Suppose that an n×nn \times n table is filled with numbers 1-1, 00, and 11 in such a way that the conditions are met. The sums nn and n-n can be obtained only from a row, column or diagonal with all 11s and all 1-1s, respectively, whence nn and n-n cannot arise as sums of different kind (one as a row sum and the other as a column sum or similar) as such sums have a common summand. If both nn and n-n arise as diagonal sums, nn must be even (otherwise the middle summand would be common) and each row and each diagonal must contain one 11 and one 1-1. But then sums n1n-1

and (n1)-(n-1) would be impossible to achieve. Hence nn and n-n must be either both row sums or both column sums. W.l.o.g., assume that they are both row sums.

The number n1n-1 can arise only as the sum of n1n-1 numbers 11 and one number 00. As 1-1 occurs in each column and each long diagonal, n1n-1 can be obtained as a row sum only. Similarly, (n1)-(n-1) can be obtained as a row sum only. The number n2n-2 can arise as the sum of either n2n-2 numbers 11 and two numbers 00 or n1n-1 numbers 11 and one number 1-1. As either two 1-1s or numbers 00 and 1-1 occur in each column and each long diagonal, n2n-2 can be obtained as a row sum only. Similarly, (n2)-(n-2) can be obtained as a row sum only.

Therefore, the table must contain at least 66 rows.

An example of a 6×66 \times 6 table that fulfils the conditions is shown in Fig. 42: the row sums from the top to the bottom are 66, 55, 5-5, 4-4, 44, and 6-6, the column sums from the left to the right are 00, 2-2, 11, 22, 1-1, 00, and the diagonal sums are 33 and 3-3.

Figure 1
Fig. 42

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.