Maths Olympiad Prep

Library / /69 of 104

Combinatorics Difficulty 6.2 National Olympiad Prove it Bulgaria

Problem:

In every cell of an n×nn \times n table one of the numbers 1,0-1, 0 and 11 is written. Is it possible the sums of the numbers in every row and every column to be 2n2n mutually different numbers, if:

a) n=4n=4;

b) n=5n=5?

Solution

Solution:

a) Yes. Here is an example:
(1011111111101111) \left(\begin{array}{rrrr} 1 & 0 & 1 & 1 \\ 1 & -1 & -1 & -1 \\ 1 & -1 & 1 & 0 \\ 1 & -1 & 1 & -1 \end{array}\right)

b) No. We have 11 possibilities for these sums: 0,±1,±2,±3,±40, \pm 1, \pm 2, \pm 3, \pm 4 and ±5\pm 5. Denote by aia_{i} the sum of the numbers in the ii-th row and by bjb_{j} the sum of the numbers in the jj-th column. Obviously
a1+a2+a3+a4+a5=b1+b2+b3+b4+b5 a_{1}+a_{2}+a_{3}+a_{4}+a_{5}=b_{1}+b_{2}+b_{3}+b_{4}+b_{5}
which shows that the number of odd sums aia_{i} and the number of odd sums bjb_{j} are of the same parity. Therefore all odd sums must be achieved.

Without loss of generality we may assume that b1=5b_{1}=5 and then none of aia_{i} equals 5-5. Thus, we may suppose that b2=5b_{2}=-5. At least one of the sums equals 44 or 4-4 and suppose it is 44. This is possible only if there is a column with four 11's and one 00. Let b3=4b_{3}=4 and the zero is in the last row. Therefore ai3a_{i} \neq -3 for every ii and we may assume that b4=3b_{4}=-3. Then in the fourth column we have at least three 1-1's. If they are in the first four rows we may assume that they are in the first three rows. So a1,a2,a3a_{1}, a_{2}, a_{3} is a permutation of 1,0,1-1, 0, 1. Therefore b53b_{5} \neq 3 and since a53a_{5} \neq 3, it follows that a4=3a_{4}=3, i.e., there are 11's in the last two cells of the fourth row. Since b4=3b_{4}=-3, the number in the last cell of the fourth column is 1-1. Now every possibility for the number in the 5th row and 5th column leads to a contradiction.

It remains to consider the case when there are at most two 1-1's in the first four cells of the fourth column. We may assume that the numbers in the fourth column are consequently 1,1,0,0-1, -1, 0, 0 and 1-1. Since the sum of the first four numbers of the rows equal 0,0,1,10, 0, 1, 1 and 1-1 we have that none of the rows equals 33 and therefore b5=3b_{5}=3. We must use different numbers for rows 1 and 2 and for rows 3 and 4, so we may have at most three 11's. Hence we may assume that the numbers in the fifth column are 1,0,1,0,11, 0, 1, 0, 1 and then a1=a4=1a_{1}=a_{4}=1, a contradiction.

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.