Competition problem — Combinatorics

Library / /7 of 19

Combinatorics Difficulty 5.0 AIME Prove it United States

Problem:
Victoria paints every positive integer either pink or blue. Is it possible that both conditions below are satisfied?
- For every positive integer $n$ , the numbers $n$ and $n+5$ are different colors.
- For every positive integer $n$ , the numbers $n$ and $2 n$ are different colors.

Solution

Solution:
The answer is no.
Assume for contradiction that such a coloring exists. Let's say $10$ was colored pink. Then $10+5=15$ must be blue, and $15+5=20$ must be pink. But now $20=10 \cdot 2$ , violating the second condition.

Now if $10$ was colored blue, the same argument works with "pink" and "blue" switched.

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: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.