Competition problem — Combinatorics

Library / /34 of 34

Combinatorics Difficulty 7.5 National olympiad, round 2 Prove it Romania

Determine all ways to color in green and red the numbers $1, 2, \ldots, 10$ such that the following conditions are fulfilled:

a) the number $5$ is colored red;

b) if the numbers $x$ and $y$ have different colors and $x + y \le 10$ , then the number $x + y$ must be colored green;

c) if the numbers $x$ and $y$ have different colors and $xy \le 10$ , then the number $xy$ must be colored red.

Solution

If $1$ is colored red, then for any green $a > 1$ , we have $1 \cdot a = a$ must be colored red, a contradiction. Hence all numbers must be red in this case.

Consider now that $1$ is colored green.

If $2$ is red, then $1 + 2 = 3$ must be green, so $2 + 3 = 5$ must also be green, contradiction. So $2$ must be green.

If $3$ is red, then $2 + 3 = 5$ must be green, contradiction. So $3$ must be green.
If $4$ is red, then $1 + 4 = 5$ must be green, contradiction. So $4$ must be green.

Since $5$ has a different color than $1, 2, 3, 4$ , all the numbers $1+5=6$ , $2+5=7$ , $3+5=8$ , $4+5=9$ must be green, and $2 \cdot 5 = 10$ must be red. The numbers $6, 7, 8, 9$ , respectively $10$ cannot be obtained as the product, respectively the sum, of $5$ and another number, so that this coloring satisfies the conditions in the statement of the problem.

Consequently, there are two possible colorings: all numbers colored red, or $5$ and $10$ colored red and the other numbers green.

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 and solution reproduced as published; topic and difficulty added by this site.