Track / Stage 5 / 164 of 400 #1244 of 2444

Problem 1244

AIME late

Combinatorics Difficulty 5.3 Prove it Brazilian Mathematical Olympiad · Brazil

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

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

Official solution

Consider a $L$ -shaped piece formed by a square and two neighbouring squares.
The sum of its numbers is the opposite of the number that completes the $L$
to a $2 \times 2$ square, so the sum of numbers in any $L$ is less than $1$ .
We proceed by induction on $n$ . For $n=3$ , divide the array in four regions: a $2 \times 2$ square, an $L$ and two single cells.

The sum is less than $3$ , because of the single cells and the $L$ .
For bigger odd $n$ , divide the array in a square of side $n-2$ , several squares of side $2$ and a $L$ :

The sum of the square of side $n-2$ is less than $n-2$ by induction hypothesis and there are only an $L$ and a single square adding to less than $2$ . So the sum is less than $n-2+2=n$ and the proof is complete.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty, ordering) added by this project.