HMMT February

Combinatorics Difficulty 5.0 AIME, harder Find the answer

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?

Your answer

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

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: Omni-MATH, licensed Apache-2.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.