Maths Olympiad Prep

Library / /1 of 2

Combinatorics Difficulty 6.3 National olympiad Find the answer

Every positive integer greater than 10001000 is colored in red or blue, such that the product of any two distinct red numbers is blue. Is it possible to happen that no two blue numbers have difference 11?

A number or a short expression. Spacing and $ signs are ignored.

Solution

Consider the given problem in which every positive integer greater than 1000 is colored either red or blue. The condition is that the product of any two distinct red numbers must result in a blue number. We need to determine if it is possible that no two blue numbers have a difference of 1.

1. Understanding the Condition for Red Numbers:\
If two distinct red numbers, say r1 r_1 and r2 r_2 , exist, then their product r1×r2 r_1 \times r_2 is a blue number. This implies that taking any two red numbers results in producing a blue number when multiplied.

2. Exploration with a Potential Contradiction:\
Suppose for contradiction that it is possible no two blue numbers have a difference of 1. This would mean that any integer immediately following or preceding a blue number cannot be blue.

3. Deducing the Red Number Structure:\
Consider the smallest red number above 1000, denoted as r r . Any other red number, say r+1 r + 1 , would force r(r+1) r(r + 1) to be blue, but as r(r+1)>1000 r(r + 1) > 1000 , and r r and r+1 r+1 differ by 1, they cannot both satisfy the condition of having a blue product without contradicting the impossibility of two blue numbers differing by 1.

4. Inductive Reasoning for Blues:\
If there is a sequence of blue numbers b1,b2, b_1, b_2, \ldots such that b1,b2,=bi b_1, b_2, \ldots = b_i , and no two differ by 1, they effectively segment numbers. But by the infinite pigeonhole principle, within a sufficiently large range above 1000, numbers will cluster such that difference 1 can occur, primarily interrupted if numbers are red. However, had these numbers been interrupted by reds, the product becomes blue.

5. Conclusion:\
Ultimately, if only a finite or systematic pattern prevents two blue numbers from differing by 1, they lead to an inherent contradiction with the replacement into blue numbers upon multiplication constraints of red. Hence, controlling integer spread leads to unavoidable adjacent blues or complement violations through multiplication triggers for blues.

Thus, given any arbitrary assignment seeking to fulfill these conditions, attempting no two blues differing by 1 will create a contradiction. Therefore, it is not possible for this coloring system to exist such that no two blue numbers have a difference of 1.

Therefore:
No \boxed{\text{No}}

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.