Let $\mathcal{P}$ be a partition of $\{1,2,\dots ,2024\}$ into sets of two elements, such that for any $\{a,b\}\in\mathcal{P}$, either $|a-b|=1$ or $|a-b|=506$. Suppose that $\{1518,1519\}\in\mathcal{P}$. Determine the pair of $505$ in the partition.
Problem
Source: Stars of Mathematics 2024 P3 (junior level)
Tags: combinatorics
20.12.2024 00:34
This problem is very hard if you think it is an algebra problem and very easy if you want it to be a combinatorics problem. The answer is that $505$ is paired with $506$. Imagine creating a $4 \times 506$ array. In the first row, place the numbers $1, 2, \dots, 506$, in the second row the numbers $507, 508, \dots, 1012$, in the third row the numbers $1013, 1014, \dots, 1518$, and in the fourth row the numbers $1519, 1520, \dots, 2024$. Then consider each set in $\mathcal{P}$ as a "domino." If $|a-b| = 506$, then $\{a, b\}$ corresponds to a vertical "domino." If $|a-b| = 1$, then $\{a, b\}$ corresponds to a horizontal "domino," except for the possible pairs $\{506, 507\}$, $\{1012, 1013\}$, and $\{1518, 1519\}$. Color the numbers in the array in an alternating checkerboard manner with $1$ being white. Then $\{506, 507\}$ covers two black squares, $\{1012, 1013\}$ covers two white squares, $\{1518, 1519\}$ covers two black squares, and all other "dominoes" cover one white and one black square. Since the board has an equal number of white and black squares and since we know that $\{1518, 1519\}$ has already been selected, we must select $\{1012, 1013\}$ and not select $\{506, 507\}$. Thus the only remaining number that $506$ could pair with is $505$, as desired.