Maths Olympiad Prep

Library / /291 of 860

Combinatorics Difficulty 5.0 AIME, harder Find the answer

Can the set of lattice points {(x,y)x,yZ,1x,y252,xy}\{(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 ab,bca \neq b, b \neq c, the colors of (a,b)(a, b) and (b,c)(b, c) are distinct?

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,,10}S=\{1,2, \ldots, 10\}. Then assign to (a,b)(a, b) an element of SS that is in the subset associated to aa but not in that associated to bb. It's not difficult to see that this numerical assignment is a valid coloring: the color assigned to (a,b)(a, b) is not in bb, while the color assigned to (b,c)(b, c) is in bb, so they must be distinct.

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: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.