Skip to main content
OlympiadHQ

Browse · MathNet

Print

1 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) .
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 ):
33333-4-4-4-4
-433333-4-4-4
-4-433333-4-4
-4-4-433333-4
-4-4-4-433333
3-4-4-4-43333
33-4-4-4-4333
333-4-4-4-433
33333-4-4-4-4
Final answer
a) 63; b) 0

Techniques

Pigeonhole principleColoring schemes, extremal arguments