Maths Olympiad Prep

Library / /6 of 6

Combinatorics Difficulty 5.3 AIME, harder Prove it Brazil

A real number with absolute value less than 11 is written in each cell of an n×nn \times n array, so that the sum of the numbers in each 2×22 \times 2 square is zero. Show that for nn odd the sum of all the numbers is less than nn.

Solution

Consider a LL-shaped piece formed by a square and two neighbouring squares.
The sum of its numbers is the opposite of the number that completes the LL
to a 2×22 \times 2 square, so the sum of numbers in any LL is less than 11.
We proceed by induction on nn. For n=3n=3, divide the array in four regions: a 2×22 \times 2 square, an LL and two single cells.
Figure 1
The sum is less than 33, because of the single cells and the LL.
For bigger odd nn, divide the array in a square of side n2n-2, several squares of side 22 and a LL:
Figure 2
The sum of the square of side n2n-2 is less than n2n-2 by induction hypothesis and there are only an LL and a single square adding to less than 22. So the sum is less than n2+2=nn-2+2=n and the proof is complete.

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 and solution reproduced as published; topic and difficulty added by this site.