Competition problem — Combinatorics

Library / /23 of 105

Combinatorics Difficulty 5.1 AIME, harder Prove it JBMO

Problem:
A board $n \times n$ ( $n \geq 3$ ) is divided into $n^{2}$ unit squares. Integers from $0$ to $n$ inclusive are written down: one integer in each unit square, in such a way that the sums of integers in each $2 \times 2$ square of the board are different. Find all $n$ for which such boards exist.

Solution

Solution:
The number of the $2 \times 2$ squares in a board $n \times n$ is equal to $(n-1)^{2}$ . All possible sums of the numbers in such squares are $0, 1, \ldots, 4n$ . A necessary condition for the existence of a board with the required property is $4n + 1 \geq (n-1)^{2}$ and consequently $n(n-6) \leq 0$ . Thus $n \leq 6$ . The examples show the existence of boards $n \times n$ for all $3 \leq n \leq 6$ .

6	6	6	6	5	5
6	6	5	5	5	5
1	2	3	4	4	5
3	5	0	5	0	5
1	0	2	1	0	0
1	0	1	0	0	0

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.