Let $a , b , c$ positive integers, coprime. For each whole number $n \ge 1$, we denote by $s ( n )$ the number of elements in the set $\{ a , b , c \}$ that divide $n$. We consider $k_1< k_2< k_3<...$ .the sequence of all positive integers that are divisible by some element of $\{ a , b , c \}$. Finally we define the characteristic sequence of $( a , b , c )$ like the succession $ s ( k_1) , s ( k_2) , s ( k_3) , .... $ . Prove that if the characteristic sequences of $( a , b , c )$ and $( a', b', c')$ are equal, then $a = a', b = b'$ and $c=c'$
Problem
Source: Rioplatense Olympiad 2015 level 3 P2
Tags: number theory, Integer sequence
Davi Medeiros
28.03.2020 22:39
To prove this, it is enough to prove that a given characteristic sequence is generated by exactly one triple of positive coprime integers $(a, b, c)$. Evidently, due to the periodicity of the multiples of $a, b, c$, this sequence is periodic, and it is repeated precisely when a $3$ appears, which is the representative of a multiple of $abc$. So, let $s (k_1), s (k_2), ..., s (k_t)$ such that $s (k_t) = 3$ and $t$ is as small as possible. Let's consider this sequence to be only this fundamental stretch.
First, notice that the number $t$ of terms in the sequence is equal to the number of multiples of $a$, $b$ or $c$ between $1$ and $abc$. So, using the inclusion-exclusion principle:
$$ t = \dfrac{abc}{a} + \dfrac{abc}{b} + \dfrac{abc}{c} - \dfrac{abc}{ab} - \dfrac{abc}{bc} - \dfrac{abc}{ca} + \dfrac{abc}{abc}$$$$t = ab + bc + ca- (a + b + c) +1$$
Also note that the quantity $t'$ of the numbers $2$ and $3$ that appears in this sequence is equal to the quantity of multiples of $ab$, $bc$ or $ca$ between $1$ and $abc$, which is equal to:
$$t '= \dfrac{abc}{ab} + \dfrac{abc}{bc} + \dfrac{abc}{ca}-2 = a + b + c-2$$
Note that we subtract $2$ because $abc$ had been counted 3 times.
From the last two equations, we conclude that, due to the symmetry of the expressions $(ab + bc + ca)$ and $(a + b + c)$ and due to the fact that $a <b <c$, we have to, if we prove that the value of $c$ is only determined by the characteristic sequence, so the values of $a$ and $b$ will also be, and with that the problem is solved.
To do this, note that there are exactly $c-1$ numbers $2$ that represent multiples of $ab$. Let $S_1$ be the sum of the numbers in the sequence up to the number $2$ that represents $ab$ (which is the first $2$ of the sequence, since $ab$ is the smallest positive integer that is a multiple of two among $a, b, c$), Let $S_2$ be the sum of the numbers in the sequence up to the number $2$ that represents $2ab$, $\dots$ , $S_ (c-1)$ the sum of the numbers in the sequence up to the number $2$ representing $(c-1)ab$ and $S_c$ the sum of the numbers in the sequence numbers up to $3$ , which represents $c.ab$.
Hence, we have that $S_m$ is the quantity of multiples of $a, b$ or $c$ from $1$ to $mab$, counted with multiplicity. This means that:
$$S_m = \dfrac{mab}{a} + \dfrac{mab}{b} + \dfrac{mab}{c} = m(a+b) + \lfloor \dfrac{mab}{c} \rfloor$$With that, we conclude that:
$$S_m-S_{m-1} -S_1 =\lfloor \dfrac{mab}{c} \rfloor - \lfloor \dfrac{(m-1)ab}{c} \rfloor-\lfloor \dfrac{ab}{c} \rfloor \in \{0,1 \} \Rightarrow S_m-S_{m-1} \in \{ S_1, S_1 +1 \}$$
Here, we used the well-known result $0 \le \lfloor x + y \rfloor - \lfloor x \rfloor - \lfloor y \rfloor < 2$.
With this in mind, we have that the following algorithm works:
1. Take the first 2 of the sequence and let $S_1$ be the sum of the numbers in the sequence up to it. Separate these numbers in a block, and take this block away from the sequence.
2. Now, take the number 2 in the sequence such that the sum of the numbers until it is $S_1$ or $S_1 + 1$ (we proved that such a number exists, and its uniqueness is obvious, since the next 2 will have partial sum $S_1 +2$). Separate these numbers in a new block, and remove this block from the sequence.
3. Repeat the previous step until the sum of the remaining sequence numbers is $S_1$ or $S_1 + 1$. The remaining numbers will form the last block, which is the $c$-th one.
For example, if we run the algorithm in the fundamental stretch 1,1,1,1,2,1,1,2,2,1,2,1,2,2,1,1,2,1,1,1,1,3 (sequence determined by $(2,3,5)$), we have the blocks $(1,1,1,1,2)$ ($S_1=6$), $(1,1,2,2)$ ($S_2-S_1=6$), $(1,2,1,2)$ ($S_3-S_2=6$), $(2,1,1,2)$ ($S_4-S_3=6$), $(1,1,1,1,3)$ ($S_5-S_4=7$). Observe that we have $5=c$ blocks.
Therefore, we obtained $c$, and since we have $a+b+c$,$ab+bc+ca$, we obtain $a,b$, finishing the problem.