Browse · MathNet
Print1 Autumn tournament
Bulgaria counting and probability
Problem
An integer is written in each of the fields of a square table. For every 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) ;
b) .
a) ;
b) .
Solution
a) Example: we number the rows and columns from to . We write in the fields (); in field and in fields (); in other fields. Possible sums are , , and .
Evaluation: Suppose there are at least 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: , where . If , then must be of the same order, a contradiction. If , then must be of the same order, a contradiction.
b) A possible example without zeros is as follows (works because and ):
Evaluation: Suppose there are at least 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: , where . If , then must be of the same order, a contradiction. If , then must be of the same order, a contradiction.
b) A possible example without zeros is as follows (works because and ):
| 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 |
Final answer
a) 63; b) 0
Techniques
Pigeonhole principleColoring schemes, extremal arguments