Prove that the natural numbers can be divided into two groups in a way that both conditions are fulfilled: 1) For every prime number $p$ and every natural number $n$, the numbers $p^n,p^{n+1}$ and $p^{n+2}$ do not have the same colour. 2) There does not exist an infinite geometric sequence of natural numbers of the same colour.
Problem
Source: Bulgarian National Olympiad 2012 Problem 2
Tags: geometric sequence, number theory, prime factorization, combinatorics proposed, combinatorics
22.05.2012 03:00
Consider the sets $A_n=\{j\in\mathbb{N}: n!\le j<(n+1)!\}$. Then $\mathbb{N}=\bigcup_nA_n$. Consider the following coloration: if $n\in A_{2h}$ for some $h$, \[p^{n}=\begin{cases} \textrm{white}, \qquad \textrm{if } n=\textrm{even}\\ \textrm{black}, \qquad \textrm{if } n=\textrm{odd} \end{cases}.\] If $n\in A_{2h+1}$ for some $h$ then switch the above coloration. Let now $m$ be a generic integer and color it as its prime factor with highest exponent: if there is ambiguity, pick the largest of these primes. Consider now the sequence $a, ar, ar^2, \ldots$, for some $a,r\in\mathbb{N}$. From a certain point, the primes of $r$ will dominate over those of $a$, and the color of the generic element $ar^N$, of the sequence will be the color of $p^{r_0N+a_0}$, for some fixed $r_0,a_0$. It's not difficult to see that there are infinitely many white and black elements of this form, for any fixed $r_0,a_0$ and prime $p$.
06.08.2012 04:00
We're going to colour the set of positive integers with two colours. Let $A$ and $B$ be the two colors. Consider the four patterns $AAB$, $ABA$, $BBA$ y $BAB$. Consider the infinite sequence $S$ of colours formed by putting the first pattern once, the second twice, the third three times, the fourth four times, now the first five times and so on (I call each group of the same pattern many times a block): \[ S = \underbrace{AAB}_{\times 1} \underbrace{ABAABA}_{\times 2} \underbrace{BBABBABBA}_{\times 3} \underbrace{BABBABBABBAB}_{\times 4} \ldots\] Denote $S_k$ to the $k$-th colour in $S$ from left to right. For example, $S_1 = A$, $S_2 = A$ and $S_8 = B$. Let $\mathcal{C}(x)$ be the colour I assign to the number $x$. This may be either $A$ or $B$. If $N = p_1^{\alpha_1} \cdots p_k^{\alpha_k}$ is the prime factorization of $N$. I claim that the colouring $\mathcal{C}(N) = S_{\alpha_1 + \ldots + \alpha_k}$ does the trick. The first condition translates to $\mathcal{C} (p^n)$, $\mathcal{C} (p^{n+1})$ and $\mathcal{C} (p^{n+2})$ not being the same. Due to our definition of colours, that is $S_n, S_{n+1}$ and $S_{n+2}$ not being the same. That is, there aren't three consecutive colours in $S$ that are the same. It is trivially true. To prove that the second condition holds, let's assume the opposite. Suppose there exists some infinite geometric sequence of first term $N$ and rate $r$ that is monochromatic. Then, we want that $\mathcal C (N) = \mathcal C (N\cdot r^{\alpha} )$ for all $\alpha \in\mathbb N$. If we let $N =p_1^{\alpha_1} \cdots p_k^{\alpha_k}$ and $m = \alpha_1 + \cdots + \alpha_k$; $r = q_1^{\beta_1}\cdots q_t^{\beta_t}$ and $n=\beta_1 + \ldots + \beta_t$, then the condition is equivalent to $S_m = S_{m+n\alpha}$ for all $\alpha\in\mathbb N$. But looking at cases of $m$ and $n$ modulo $3$ it is easy to see that if we take sufficently large $\alpha$ we can get $S_{m + n\alpha}$ and $S_{m + n(\alpha+1)}$ in a same block or in two consecutive blocks and we can make sure that if one is coloured $A$ the other one is $B$, and the other way around, contradicting the existence of an infinite geometric sequence. And we're done. $\blacksquare$
02.05.2013 02:35
for naturals $n$ $d(n)$ the sum of the exponents of primes in $n$. For all $n$ with at least $2$ prime divisors we color $n$ blue if $d(n)$ has an even number of digits and red otherwise. clearly an infinite geometric progression contains a number of at least $2$ primes we get an easy contradiction. Now for numbers $p^n$ if $n$ has an even number of digits and is divisible by $3$ then color it blue. if it has an odd number of digits and gives remainder $2$ mod $3$ also color it blue and numbers $10^k$ color blue. This coloring clearly satisfies both conditions.
22.02.2016 12:26
Defenitions: $n=p_1^{a_1}\times ... \times p_k^{a_k}$. $S(n)=a_1+...+a_k$. $C(n)$ is a number $S(n)$ written in binary. $q=a_2/a_1$. $q=p_1^{b_1}\times ... \times p_l^{b_l}$ $k=b_1+...+b_l$. Coloring: We will color $n$ black if $C(n)$ has odd number of ones in it and white otherwise. Proof: Firstly, it is clear that at least one of $C(p^k), C(p^{k+1})$ has last digit equal to zero, so either $(C(p^{k+1})$ and $C(p^k))$ or $(C(p^{k+2})$ and $C(p^{k+1}))$ have different parity of the number of ones. Each infinite geometric sequence $\{a_n\}_{n=1}^{\infty}$ of natural numbers have only one color in it iff all $C(a_n)$ have the same number of ones in it. It is easy to see that $C(a_{n+1})=C(a_n)+k$. One can prove that such arithmetic sequence has differently colored numbers considering $C(a_1)+(2^t+1)\times k$ or $C(a_1)+(2^t-1)\times k$ for sufficiently large $t$. Also, if we consider sequence $f(n)= \#$ of ones in $C(n)$ modulo $2$, we will receive arithmetic consequence of Thue–Morse sequence, which is a typical example of a minimal map $f$ on a connected space. But it is known, that "A minimal map $f$ on a connected space $X$ is totally transitive." (Theorem 2.5 from "Regular periodic decompositions for topologically transitive maps" by John Banks) And this is exactly what we want: there doesn't exist such $t$ that $f^t$ is non-transitive, so for each $t$ there exist such $l(0)$ that $(f^t)^l(0)$ is 0 and there exist such $l(1)$ that $(f^t)^l(1)$ is 1. Also this happens for any starting point, so there exist infinete sequences $\{b_i\}_{i=1}^\infty$ and $\{c_j\}_{j=1}^\infty$ such that $(f^t)^{b_i}=0$ and $(f^t)^{c_j}=1$.
26.02.2016 15:26
kroki wrote: Prove that the natural numbers can be divided into two groups in a way that both conditions are fulfilled: 1) For every prime number $p$ and every natural number $n$, the numbers $p^n,p^{n+1}$ and $p^{n+2}$ do not have the same colour. 2) There does not exist an infinite geometric sequence of natural numbers of the same colour. All geometric progressions are countably many, so we can enumerate them as: $g_1, g_2,\dots$ The idea is to color consecutively the natural numbers, complying with the condition 1), and one by one rule out the possibilities $g_1,g_2,\dots$ to be monochromatic. Suppose it comes the moment to color $p^n$. If $p^{n-2}, p^{n-1}$ are in the same color, it's mandatory to color $p^n$ with the opposite one. But after that, when it comes to color $p^{n+1}$, we would have a choice. The algorithm: Color number $1$ white. Set $n=1$ Coloring step : The aim is to rule out $g_n$ to be monochromatic. There are two possibilities: a) $g_n$ is not of the form $p^{n_k}$, where $n_k,k=1,2\dots$ is an arithmetic progression. b) $g_n$ consists of $p^{n_1},p^{n_2},\dots$, where $n_1,n_2,\dots$ is an arithmetic progression. Case a): Let $g_n=\{a_1,a_2,\dots\}$ and $a_k$ be the first its member that is not yet colored. Then we color all not colored numbers somehow, complying with condition 1), till $a_k$. Then color $a_k$ white, then color in the same manner numbers till $a_{k+1}$, and finally color $a_{k+1}$ black. Case b): Let $g_n=\{p^{n_1}, p^{n_2},\dots\}$. Suppose $p^{n_k}$ be the first member of $g_n$ with the property: $p^{n_k}$ and $p^{n_{k} -1}$ are not yet colored. Then we color all numbers till $p^{n_{k} -1}$ complying with condition 1). If there is an option to color $p^{n_{k} -1}$ in both colors, we color it in the color opposite to that $p^{n_{k}-2}$ is colored. Otherwise we color $p^{n_{k} -1}$ in the only possible color. In this way when it comes to color $p^{n_k}$, we have the option to color it in both colors, and we color it in the color, opposite to the color of $p^{n_{k-1}}$. That's, we have ruled out the possibility $g_n$ to be monochromatic. Now, we increment $n$ and go again to the coloring step. Comment. All of the solutions above, including the official one, explicitly construct a clever coloring that complies with conditions 1) and 2). Rather on the opposite, the above approach is also constructive, but there is no need to be so smart and construct explicitly a rule of coloring.
27.03.2016 02:27
First color $N$ as follows: $CPC|PCP|PCP|CPC|CPC|CPC|PCP|PCP|PCP|PCP\dots$ in a pattern where $CPC$ comes once, then $PCP$ comes twice, then $CPC$ three times and just continue like that. Let $k-th$ letter be the color of $k$. Easy to see that there are no $3$ consecutive elements of the same color. Now suppose this coloring contains an infinite arithemtic progression: $a,a+d,a+2d,\dots$. That means it contains $a,a+3d,a+6d,\dots$ or in other words infinitely many numbers from the same position in their triplets like $a$ is in his triplet. Note that $a,a+3d,a+6d,\dots$ are colored as follows: $PCCPPPCCCC\dots$ (if we take it starts with $C$ the proof is the same). Now notice that $a+3d$ is just $d$ moves away from $a$ in last sequence. Because there are both $C$ consecutive sequences and $P$ consecutive sequences longer than $d$ there will be both $P$ and $C$ colors in the progression which is a contradiction. Now for some number $n=p_1^{\alpha_1}\cdots p_k^{\alpha_k}$ let $n$ be colored like number $\alpha_1+\dots+\alpha_k$ in the above coloring. Now we easily see that: $p^{n},p^{n+1},p^{n+2}$ are colored differently. Now if there is an geometric progression for some same colored numbers then the sum of their exponents form arithmetic progression which is in contradiction with the above coloring so we have colored $N$ to satisfy both conditions so we are finished.
08.06.2018 19:13
look at the prime factorization of a number and choose the biggest exponent (if tied, biggest prime among those who are equal) and the if the exponent was 0,1 mod 4 then put it in A and if it was 2,3 put it B . and so one can easily see this coloring works .
22.12.2023 02:20
kroki wrote: Prove that the natural numbers can be divided into two groups in a way that both conditions are fulfilled: 1) For every prime number $p$ and every natural number $n$, the numbers $p^n,p^{n+1}$ and $p^{n+2}$ do not have the same colour. 2) There does not exist an infinite geometric sequence of natural numbers of the same colour. Please correct the problem statement formally (the words "groups" and "colours" are mixed).