Library / Eighteenth STARS OF MATHEMATICS Competition /4 of 7

Eighteenth STARS OF MATHEMATICS Competition

Combinatorics Difficulty 5.6 AIME, harder Prove it Romania

A partition of a set $S$ is a set of pairwise disjoint subsets of $S$ whose union is $S$ . Let $P$ be a partition of the set $\{1, 2, ..., 2024\}$ into 2-element sets, satisfying the following condition: For every set $\{a, b\}$ in $P$ , either $|a - b| = 1$ or $|a - b| = 506$ . Assume that $\{1518, 1519\}$ belongs to $P$ . Determine the number that pairs off with $505$ to form a set in $P$ .
The Problem Selection Committee

Solution

Assume the square in the upper-left corner is white.
By the condition in statement, a set $\{a, b\}$ in $P$ is a horizontal domino if $|a-b| = 1$ and a vertical domino if $|a - b| = 506$ , with the possible exceptions $\{506, 507\}$ , $\{1012, 1013\}$ and $\{1518, 1519\}$ . As this latter is an all-black member of $P$ and dominoes are bicolour, $P$ must have some all-white member. The only such is $\{1012, 1013\}$ .
Hence, to form a set in $P$ , the number $506$ pairs off with exactly one of $505$ and $507$ .
As $\{506, 507\}$ is all-black and there are no more all-white sets left, $506$ must pair off with $505$ , as stated.

Want a route through all this instead of an archive? The track puts 2,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

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