Every positive integer greater than $1000$ 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 $1$?
Problem
Source: All-Russian MO 2023 Final stage 9.3
Tags: algebra
23.04.2023 17:14
Assume this is the case and no two consecutive numbers are blue at the same time. We note that if $s$ is red, then $s^2$ is blue and has the same parity, hence we have infinitely many pairs of consecutive red numbers. Let $(t, t+1)$ be such a pair. Then $t^2+t$ is blue, $t^2+t+1$ is red and $t^3+t^2+t$ is blue. Also, $t^2$ is blue, $t^2+1$ is red and $(t^2+1)(t+1) = t^3+t^2+t+1$ is blue. This contradicts our initial assumption, hence the answer is no.
26.04.2023 20:09
The problem statement mentions that the two red numbers also have to be different (source). Let me directly translate my solution from there. The answer is no. Let's assume there are no consecutive blue numbers. Firstly, note that if $n$ is blue, then $n-1$ and $n+1$ are both red, and so $(n-1)(n+1)=n^2-1$ is blue, hence $n^2$ is red. Let $n>1000$ be a blue number (if none exists, then all numbers are red, a contradiction since the product of each two of them is blue). Then, from our previous remark $n^2$ is red. We distinguish two cases. Case 1: $n^3$ is red. Then, $n^2 \cdot n^3=n^5$ is blue, and so $(n^5)^2=n^{10}$ is red. Since $n^2 \cdot n^8=n^3 \cdot n^7=n^{10},$ it must be the case that $n^7,n^8$ are both blue. Therefore, $n^{14}$ and $n^{16}$ are both red. However, since $n^{16}=n^{10} \cdot n^6,$ we must also have that $n^6$ is blue. Thus, $(n^6)^2=n^{12}$ is red, and we arrive at the sought contradiction since $n^2 \cdot n^{12}=n^{14}$ and $n^2,n^{12},n^{14}$ are all red. Case 2: $n^3$ is blue. Then $(n^3)^2=n^6$ is red and since $n^2 \cdot n^4=n^6,$ we conclude that $n^4$ is blue. Hence, $(n^4)^2=n^8$ is red. However, in this case we obtain that $n^2 \cdot n^6=n^8$ and $n^2,n^6,n^8$ are all red, a contradiction. Thus, in all cases we reach a contradiction and so the proof is complete.
10.08.2023 01:49
FTSOC assume the opposite. Note that both $RBRB...$ and $BRBR...$ are invalid colourings so at least two consecutive numbers $n$ and $n+1$ are coloured red. Note that $n(n+1)$ must be blue so $n^2 + n - 1$ is red, which implies that $(n+1)(n^2+n-1) = n^3 + 2n^2 - 1$ is blue so $n^3+2n^2-2$ is red and we conclude $n^4 + 2n^3 - 2n$ is blue. On the other hand, $n(n^2+n-1) = n^3 + n^2 - n$ is blue so $n^3 + n^2 - n - 1$ is red and thus $(n+1)(n^3 + n^2 - n - 1) = n^4+2n^3 -2n-1$ is blue. Two numbers coloured blue are consecutive, a contradiction.