Maths Olympiad Prep

Library / /27 of 32

Combinatorics Difficulty 6.5 National Olympiad Prove it Romania

We consider an n×nn \times n (nNn \in \mathbb{N}, n2n \ge 2) square divided into n2n^2 unit squares. Determine all the values of kNk \in \mathbb{N} for which we can write a real number in each of the unit squares such that the sum of the n2n^2 numbers is a positive number, while the sum of the numbers from the unit squares of any k×kk \times k square is a negative number.

Solution

We will prove that the desired numbers kk are those that are not factors of nn.

If knk \mid n, then we can tile the n×nn \times n square with k×kk \times k squares and the total sum should simultaneously be positive and negative, which is impossible.

If knk \nmid n, then n=kq+rn = kq + r, where 0<r<k0 < r < k. We fill the unit squares with aa (to be chosen conveniently later on) in the positions (ik,jk)(ik, jk) with i,j=1,,qi, j = 1, \dots, q and with 11 in the other positions. Every k×kk \times k square contains exactly one unit square of the form (ik,jk)(ik, jk), therefore the sum in every k×kk \times k square is a+k21a + k^2 - 1. The total sum is q2a+n2q2q^2 a + n^2 - q^2. We will choose aa arbitrarily from the non-empty interval (1n2q2,1k2)\left(1 - \frac{n^2}{q^2}, 1 - k^2\right).

Remark: For the case knk \nmid n there are many other ways of choosing the numbers from the unit squares. Another choice is to fill all the unit squares of the columns jkjk, j=1,,qj = 1, \dots, q, with a convenient aa and the other ones with 11.

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.