Library / HMMT February Team Round /2 of 9

HMMT February Team Round, 2019

Combinatorics Difficulty 5.1 AIME, harder Prove it United States

Problem:
Can the set of lattice points $\{(x, y) \mid x, y \in \mathbb{Z}, 1 \leq x, y \leq 252, x \neq y\}$ be colored using 10 distinct colors such that for all $a \neq b, b \neq c$ , the colors of $(a, b)$ and $(b, c)$ are distinct?

Solution

Solution:
Yes.
Associate to each number from $1$ to $252$ a distinct $5$ -element subset of $S=\{1,2, \ldots, 10\}$ . Then assign to $(a, b)$ an element of $S$ that is in the subset associated to $a$ but not in that associated to $b$ . It's not difficult to see that this numerical assignment is a valid coloring: the color assigned to $(a, b)$ is not in $b$ , while the color assigned to $(b, c)$ is in $b$ , so they must be distinct.

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.