Olympiad Maths Prep

Library / /2 of 4

Combinatorics Difficulty 6.0 National olympiad Prove it Bulgaria

An integer is written in each of the fields of a 9×99 \times 9 square table. For every kk numbers in the same row (column), their sum is in the same row (column). Find the smallest possible number of zeros in the table if:

a) k=5k = 5;

b) k=8k = 8.

Solution

a) Example: we number the rows and columns from 11 to 99. We write 11 in the fields (i,i)(i, i) (i=1,,9i = 1, \dots, 9); 1-1 in field (1,9)(1, 9) and in fields (i,i1)(i, i-1) (i=2,,9i = 2, \dots, 9); 00 in other fields. Possible sums are 11, 00, and 1-1.

Evaluation: Suppose there are at least 1919 non-zero numbers. From Dirichlet's principle, there will be at least three non-zero numbers on any row, and therefore at least two non-zero numbers with the same sign, let's say positive ones (the situation with negative ones is analogous). Let's arrange the numbers in this order by size: a1a2a9a_1 \le a_2 \le \dots \le a_9, where a9a8>0a_9 \ge a_8 > 0. If a50a_5 \ge 0, then a5+a6+a7+a8+a9a8+a9>a9a_5 + a_6 + a_7 + a_8 + a_9 \ge a_8 + a_9 > a_9 must be of the same order, a contradiction. If a5<0a_5 < 0, then a1+a2+a3+a4+a5<a1a_1 + a_2 + a_3 + a_4 + a_5 < a_1 must be of the same order, a contradiction.

b) A possible example without zeros is as follows (works because 53+3(4)=35 \cdot 3 + 3 \cdot (-4) = 3 and 43+4(4)=44 \cdot 3 + 4 \cdot (-4) = -4):

| 3 | 3 | 3 | 3 | 3 | -4 | -4 | -4 | -4 |
|----|----|----|----|----|----|----|----|----|
| -4 | 3 | 3 | 3 | 3 | 3 | -4 | -4 | -4 |
| -4 | -4 | 3 | 3 | 3 | 3 | 3 | -4 | -4 |
| -4 | -4 | -4 | 3 | 3 | 3 | 3 | 3 | -4 |
| -4 | -4 | -4 | -4 | 3 | 3 | 3 | 3 | 3 |
| 3 | -4 | -4 | -4 | -4 | 3 | 3 | 3 | 3 |
| 3 | 3 | -4 | -4 | -4 | -4 | 3 | 3 | 3 |
| 3 | 3 | 3 | -4 | -4 | -4 | -4 | 3 | 3 |
| 3 | 3 | 3 | 3 | 3 | -4 | -4 | -4 | -4 |

Looking for a route rather than 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.