Competition problem — Combinatorics

Library / /17 of 48

Combinatorics Difficulty 5.1 AIME, harder Prove it Baltic Way

The entries of an $8 \times 8$ chessboard are numbered by the numbers $1, 2, \ldots, 64$ in such a way that the sum of the four numbers in each of its parts of one of the forms

is divisible by the same integer $N$ . For which of the integers $3$ , $4$ , $5$ is this possible?

Solution

Numbers in cells "A" and "B" must have the same remainder modulo $N$ , because shaded cells are common for two forms (shaded cells + "A" and shaded cells + "B"). Investigating all possible form placements, we will get that numbers in cells marked by the same lowercase letter must have the same remainder modulo $N$ .

For $8 \times 8$ chessboard there will be $8$ groups with $8$ cells in each group having the same remainder modulo $N$ . In case of $N=3$ or $N=5$ it is not possible to split all numbers in such groups. If $N=4$ one valid distribution of numbers modulo $4$ is:

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.