The International Mathematical Olympiad "Tuymaada" ...
Even students from Romania participated there. We read on Andrei Alex ECKSTEIN's blog : "The Tuymaada International Multidisciplinary Olympiad is a competition held annually in Yakutsk, Sakha Republic (Russian Federation). The competition has sections: mathematics, computer science, physics and chemistry. There are two days of competition. Participation is numerically small, for example in 2013 150 students from 6 countries participated, including Romania. Although very far away, participation in the competition is justified by the exceptional quality of the problems. Since 2000, the competition has had a section dedicated to juniors."
Follow the path :
HOME$\rightarrow$PROBLEME DIVERSE$\rightarrow$CONCURSURI$\rightarrow$"TUYMAADA"
I was interested in "INTERNATIONAL OLYMPIAD "TUYMAADA-2025" (mathematics) Second day" Problems 6 from both the Seniors and Juniors :
Senior League 6. In a sequence $(x_n)$, the number $x_1$ is positive and
rational, and
$x_{n+1} = \frac{\{nx_n\}}{n}$ for $n\geqslant 1$
($\{a\}$ denotes the fractional part of $a$). Prove that this
sequence contains only finitely many non-zero terms
and their sum is an integer.
(V. Kolezhuk, O, Tarakanov )
Junior League 6. In a sequence $(x_n)$, the first number $x_1$ is positive,
and
$x_{n+1} =\frac{\{ nx_n\}}{ n}$ for $n\geqslant 1$
($\{a\}$ denotes the fractional part of $a$). Prove that the
sequence does not contain zeroes if and only if $x_1$ is
irrational.
(V. Kolezhuk, O, Tarakanov )
$\blacklozenge$CiP Comments
We will refer to these problems by the notations S6, J6 respectively.
$\blacklozenge$Problem J6 has a logical aspect
$$\forall n\;(x_n\neq 0)\;\Leftrightarrow\; x_1\notin\mathbb{Q}$$
The statement
$x_1\notin \mathbb{Q}\;\Rightarrow\;\forall n\;(x_n\neq 0)$
is almost trivial: from $\{nx_n\}=nx_n-[nx_n]$ we have $x_{n+1}=\color{Red}{x_n}-\frac{[nx_n]}{n}$, so
$x_n\notin \mathbb{Q}\;\Rightarrow\;x_{n+1}\notin \mathbb{Q}$, hence $x_{n+1}\neq 0$. Thus we have $\forall n\;(x_n \neq 0).$
For statement
$\forall n\;(x_n \neq 0)\;\Rightarrow\;x_1\notin \mathbb{Q}$
we prove its converse instead
$x_1 \in \mathbb{Q}\;\Rightarrow\;\exists n\;(x_n=0) \tag{SJ_1}$
that is a common requirement for both problems J6, S6.
$\blacklozenge$Let's look at some examples.
Example 1 $x_1=\frac{2}{3}$
$x_2=\frac{\{x_1\}}{1}=\left\{\frac{2}{3}\right \}=\frac{2}{3}\;;\;x_3=\frac{\{2x_2\}}{2}=\frac{\left \{\frac{4}{3}\right \}}{2}=\frac{\frac{1}{3}}{2}=\frac{1}{6}\;;\;x_4=\frac{\{3x_3\}}{3}=\frac{\left \{\frac{3}{6}\right \}}{3}=\frac{\frac{3}{6}}{3}=\frac{1}{6}$
$x_5=\frac{\{4x_4\}}{4}=\frac{\left \{\frac{4}{6}\right \}}{4}=\frac{\frac{4}{6}}{4}=\frac{1}{6}\;;\;x_6=\frac{\{5x_5\}}{5}=\frac{\left \{\frac{5}{6}\right \}}{5}=\frac{\frac{5}{6}}{5}=\frac{1}{6}$
$x_7=\frac{\{6x_6\}}{6}=\frac{\{1\}}{6}=0$ and from here on out, all $x_n=0,\;n\geqslant 8$.
The sum of the nonzero terms is
$$x_1+x_2+x_3+x_4+x_5+x_6=\frac{2}{3}+\frac{2}{3}+\frac{1}{6}+\frac{1}{6}+\frac{1}{6}+\frac{1}{6}=2 \tag{S_Ex_1}$$
We will see later the connection with Egyptian writing
$$\frac{2}{3}=\frac{1}{2}+\frac{1}{6} \tag{E_Ex_1}$$
Example 2. $x_1=\frac{3}{4}$
$x_2=\frac{\{x_1\}}{1}=\left\{\frac{3}{4}\right\}=\frac{3}{4}\;;\;x_3=\frac{\{2x_2\}}{2}=\frac{\left\{\frac{6}{4}\right \}}{2}=\frac{\frac{2}{4}}{2}=\frac{1}{4}\;;\;x_4=\frac{\{3x_3\}}{3}=\frac{\left\{\frac{3}{4}\right \}}{3}=\frac{\frac{3}{4}}{3}=\frac{1}{4}$
$x_5=\frac{\{4x_4\}}{4}=\frac{\{1\}}{4}=0$ and from here on out, all $x_n=0,\;n\geqslant 6$.
The sum of the nonzero terms is
$$x_1+x_2+x_3+x_4=\frac{3}{4}+\frac{3}{4}+\frac{1}{4}+\frac{1}{4}=2 \tag{S_Ex_2}$$
and the representation as a sum of Egyptian fractions of $x_1$ is
$$\frac{3}{4}=\frac{1}{2}+\frac{1}{4} \tag{E_Ex_2}$$
Example 3. $x_1=\frac{17}{5}$
$x_2=\frac{\{x_1\}}{1}=\left\{ \frac{17}{5}\right \}=\frac{2}{5}\;;\;x_3=\frac{\{2x_2\}}{2}=\frac{\left\{\frac{4}{5}\right\}}{2}=\frac{\frac{4}{5}}{2}=\frac{2}{5}\;;\;x_4=\frac{\{3x_3\}}{3}=\frac{\left\{\frac{6}{5}\right\}}{3}=\frac{\frac{1}{5}}{3}=\frac{1}{15}$
$x_5=\frac{\{4x_4\}}{4}=\frac{\left\{\frac{4}{15}\right\}}{4}=\frac{1}{15}\;;\;x_6=\frac{\{5x_5\}}{5}=\frac{\left\{\frac{5}{15}\right\}}{5}=\frac{\frac{5}{15}}{5}=\frac{1}{15}\;;\;x_7=\frac{\{6x_6\}}{6}=\frac{\left\{\frac{6}{15}\right\}}{6}=\frac{\frac{6}{15}}{6}=\frac{1}{15}$
$x_8=\frac{\{7x_7\}}{7}=\frac{\left\{\frac{7}{15}\right\}}{7}=\frac{\frac{7}{15}}{7}=\frac{1}{15}\;;\;x_9=\frac{\{8x_8\}}{8}=\frac{\left\{\frac{8}{15}\right\}}{8}=\frac{\frac{8}{15}}{8}=\frac{1}{15}\;;\;x_{10}=\frac{\{9x_9\}}{9}=\frac{\left\{\frac{9}{15}\right\}}{9}=\frac{\frac{9}{15}}{9}=\frac{1}{15}$
and so on... $x_{11}=\frac{1}{15}=x_{12}=x_{13}=x_{14}=x_{15}\left (=\frac{\{14x_{14}\}}{14}=\frac{\left\{\frac{14}{15}\right\}}{14}=\frac{\frac{14}{15}}{14}=\frac{1}{15}\right )$
but(!) $x_{16}=\frac{\{15x_{15}\}}{15}=\frac{\{1\}}{15}=0$ and from here on out, $x_n=0,\;n\geqslant 17$.
The sum of the nonzero terms is
$$x_1+x_2+x_3+x_4+\dots+x_{15}=\frac{17}{5}+2\cdot\frac{2}{5}+12\cdot \frac{1}{15}=5\tag{S_Ex_3}$$
and the representation as a sum of Egyptian fractions of $x_1$ is
$$\frac{17}{5}=3+\frac{1}{3}+\frac{1}{15} \tag{E_Ex_3}$$
Example 4. $x_1=\frac{7}{6}$
$x_2=\frac{\{x_1\}}{1}=\left \{\frac{7}{6}\right\}=\frac{1}{6};$ without further calculation, so in the previous examples, we have
$x_3=x_4=x_5=x_6=\frac{1}{6},\;x_7=\frac{\{6x_6\}}{6}=\frac{\{1\}}{6}=0$, and furher $x_n=0,\;n\geqslant 8$.
The sum of the nonzero term is
$$x_1+x_2+\dots+x_6=\frac{7}{6}+5\cdot \frac{1}{6}=2 \tag{S_Ex_4}$$
and $x_1$ has the representation as the sum of Egyptian fractions
$$\frac{7}{6}=1+\frac{1}{6} \tag {E_Ex_4}$$
Example 5. $x_1=\frac{3}{7}$
We quickly see that $x_3=x_2=\{x_1\}=\frac{3}{7}$; then that $x_{11}=x_{10}=\dots=x_4=\frac{\{3x_3\}}{3}=\frac{\left\{\frac{9}{7}\right\}}{3}=\frac{\frac{2}{7}}{3}=\frac{2}{21}$;
and the eye, increasingly experienced, sees that $x_{231}=x_{230}=\dots =x_{12}=\frac{\{11 x_{11}\}}{11}=\frac{\left\{\frac{22}{21}\right\}}{11}=\frac{\frac{1}{21}}{11}=\frac{1}{231}$.
We're almost done, because $x_{232}=\frac{\{231x_{231}\}}{231}=\frac{\{1\}}{231}=0$ and $x_n=0,\;n\geqslant 232$.
The sum of the nonzero terms is
$$x_1+x_2+x_3+(x_4+x_5+\dots+x_{11})+(x_{12}+x_{13}+\dots+x_{231})=3\cdot \frac{3}{7}+8\cdot \frac{2}{21}+220\cdot \frac{1}{231}=3 \tag{S_Ex_5}$$
and $x_1$ has the representation as the sum of Egyptian fractions
$$\frac{3}{7}=\frac{1}{3}+\frac{1}{11}+\frac{1}{231} \tag{E_Ex_5}$$
$\blacklozenge$The hard truth about the sequence $(x_n)$ is, this sequence being the protocol of a slow and sad decomposition of a rational number $x_1=\frac{a}{b}$ to the form - pay attention to colors -
$\frac{a}{b}=\color{Blue}s+\frac{1}{k_1}+\dots+\frac{1}{k_{\color{Red}m}} \tag{E_1}$
where
$s=[x_1],\;\;k_1<k_2<\dots<k_m \tag{E_2}$
$k_i,\;i=1,\dots m,$ are positive integers, and
$x_n=\frac{1}{k_i}+\dots +\frac{1}{k_m}\;\;for\;\;k_{i-1}<n\leqslant k_i \tag{E_3}$
Moreover, the sum of the nonzero terms of the sequence is equal to (!!colors!!)
$x_1+x_2+\dots+x_{k_m}=\color{Blue}s+\color{Red}m \tag{S}$
Returning to the previous examples
In Example 1, $x_7=0,\;\;x_6=x_5=x_4=x_3=\frac{1}{6},\;\;x_2=x_1=\frac{2}{3}=\frac{1}{2}+\frac{1}{6}.$ So $\color{Blue}{s=0},\;\color{Red}{m=2},\;k_1=2,\;k_2=6.$
In Example 2, $x_5=0,\;\;x_4=x_3=\frac{1}{4},\;\;x_2=x_1=\frac{3}{4}=\frac{1}{2}+\frac{1}{4}.$ So $\color{Blue}{s=0},\;\;\color{Red}{m=2},\;k_1=2,\;k_2=4.$
In Example 3, $x_{16}=0,\;\;x_{15}=x_{14}=\dots=x_4=\frac{1}{15},\;\;x_3=x_2=\frac{2}{5}=\frac{1}{3}+\frac{1}{15}.$ So $\color{Blue}{s=3},\;\;\color{Red}{m=2},\;k_1=3,\;k_2=15.$
In Example 4, $x_7=0,\;\;x_6=x_5=\dots=x_2=\frac{1}{6}$. So $\color{Blue}{s=1},\;\;\color{Red}{m=1},\;k_1=6.$
In Example 5, $x_{232}=0,\;\;x_{231}=x_{230}=\dots=x_{12}=\frac{1}{231},\;\;x_{11}=x_{10}=\dots=x_4=\frac{2}{21}=\frac{1}{11}+\frac{1}{231},\;\;$
$x_3=x_2=\frac{3}{7}=\frac{1}{3}+\frac{1}{11}+\frac{1}{231}.$ So $\color{Blue}{s=0},\;\;\color{Red}{m=3},\;k_1=3,\;k_2=11,\;k_3=231.$
All relations (E_1), (E_3), (S) are verified.
$\blacklozenge$A final example, treated more expeditiously:
Let $x_1=\frac{7}{8}$. The calculations show that
$\color{Blue}{s=0},\;\;k_1=2,\;\;k_2=3,\;\;k_3=24,\;\;\color{Red}{m=3}$
$x_{25}=0,\;\;x_{24}=\dots=x_4=\frac{1}{24},\;\;x_3=\frac{3}{8}=\frac{1}{3}+\frac{1}{24},\;\;x_2=x_1=\frac{7}{8}=\frac{1}{2}+\frac{1}{3}+\frac{1}{24}$
and
$x_1+\dots +x_{24}=2\cdot \frac{7}{8}+\frac{1}{3}+21\cdot \frac{1}{24}=3$
<end CiP comments>$\blacklozenge$
Proving that the sequence contains
only a finite number of nonzero terms
Let's prove (SJ_1) that is, if $x_1$ is a rational number then the sequence contains a term (and from here on all terms) equal to zero.
If $x_1\in\mathbb{Z}$, then $\{x_1\}=0$ and statement (SJ_1) is true.
Otherwise, $x_2\;\overset{def}{=}\;\frac{\{1\cdot x_1\}}{1}=\{x_1\} \in (0;1)$ and we will clarify this case in the following.
So, let
$x_2=\frac{a}{b},\;\;a<b \tag{1}$
and $a\; and\; b$ are positive coprime integers.
We choose $k$-the smallest natural number such that
$x_2 \geqslant \frac{1}{k} \tag{2}$
Obviously $k\geqslant 2$.
If $k=2$, that is $\frac{a}{b}=x_2\geqslant 2$ (so $2a-b\geqslant 0$ we'll use that later)
we have $2x_2-1\geqslant 0$ and, as $x_2<1$, we also have $2x_2-1<1$. Using the periodicity of the function $\{\cdot\}\;(i.e.\;\{\alpha\}=\{\alpha-1\})$ we find
$x_3=\frac{\{2x_2\}}{2}=\frac{\{2x_2-1\}}{2}\underset{0\leqslant 2x_2-1<1}{===}\frac{2x_2-1}{2}=x_2-\frac{1}{2} \tag{3}$
With (1) this is written
$x_3=\frac{2a-b}{2b},\;\;\;0\leqslant 2a-b \;\overset{\color{Red}!a<b}{<}\;a \tag{4}$
So, if $x_3$ is not eqal zero, then the numerator of $x_3$ in irreducible form, is $\leqslant 2a-b$ hence (cf. (4)) less than the numerator of $x_2$.
<end case $k=2$>
If $k>2$ we will prove the following facts :
(i) $2\leqslant i \leqslant k\;\;\Rightarrow\;\;x_i=x_2$
(ii) $x_{k+1}=x_2-\frac{1}{k} \tag{5}$
We show (i) one by one, up close and close.
Obviously (i) holds for $i=2$.
We assume the statement is true for some $i$, with $i\geqslant 2\;\;and\;i+1\leqslant k$. We have $i\leqslant k-1$ and, considering how we defined the number $k$, it results (cf. (2)) $x_2<\frac{1}{i}.$ But then
$x_{i+1}=\frac{\{i \cdot x_i\}}{i}\underset{\overbrace{x_i=x_2}}{==}\frac{\{i \cdot x_2\}}{i}\overset{\underbrace{ix_2<1}}{==}\frac{i\cdot x_2}{i}=x_2$
so (i) is also true for $i+1$.(It's like a kind of Induction.)
For (ii) , since from the way we chose the number $k,\;\;k-1$ does not verify (2) - that is $x_2<\frac{1}{k-1}$-, we have the inequalities
$$\frac{1}{k}\overset{(2)}{\leqslant} x_2\underset{(1)}{=}\frac{a}{b}<\frac{1}{k-1}\overset{k>2}{<}\frac{2}{k} \tag{6}$$
Then $b\leqslant k\cdot a<2b$, so $0\leqslant ka-b<b\;\left ( \Leftrightarrow 0\leqslant \frac{ka-b}{b}<1\right )$, and
$x_{k+1}=\frac{\{k\cdot x_k\}}{k}=\frac{\{k\cdot x_2\}}{k}=\frac{\left\{\frac{ka}{b}\right\}}{k}=\frac{\left \{\frac{ka}{b}-1\right \}}{k}=\frac{\left \{\frac{ka-b}{b}\right \}}{k}=\frac{\frac{ka-b}{b}}{k}=\frac{ka-b}{kb}=x_2-\frac{1}{k} \tag {7}$
From $(k-1)a<b$ (cf.(6)) we have $ka-b<a$ and from $x_{k+1}=\frac{ka-b}{kb}$ we see that the numerator of $x_{k+1}$ in irreducible form, is $\leqslant ka-b$ hence less than the numerator $a$ of $x_2$.
<end case $k>2$>
(Notice that (3) is embedded in (7) for $k=2$.)
"As the numerators cannot decrease infinitely, at some moment the next term will be 0." (We have reproduced the words of the authors of the Official Solution.)
<<end of Proof (SJ_1)>> $\blacksquare$
Before moving on, let's try to find out the
Structure of the Sequence $(x_n)_{n\geqslant 1}$
and its Connection with the Egyptian Fractions
Let $k_m$ be the index of the last nonzero term. From $x_{k_m+1}=0$, applying the analogous of (5)
$x_{k_m+1}=x_{k_m}-\frac{1}{k_m} \tag{8}$
it result
$x_{k_m}=\frac{1}{k_m} \tag{9'}$
(The same thing can be obtained from $x_{k_m+1}=\frac{\{k_m\cdot x_{k_m}\}}{k_m}=0\;\;\overset{\underbrace{x_n<\frac{1}{n-1}}}{\Rightarrow}\;\;k_m\cdot x_{k_m}=1\;\;etc$ )
Let $k_{m-1}$ be the largest index $<k_m$ for wich $x_{k_{m-1}}\neq x_{k_m}.$ We have
$\frac{1}{k_m}=x_{k_m}=x_{k_m-1}=\dots =x_{k_{m-1}+1} \tag{10'}$
abd from (8) written for $k_{m-1}\;:$
$x_{k_{m-1}+1}=x_{k_{m-1}}-\frac{1}{k_{m-1}}\overset{(10')}{\Leftrightarrow}\frac{1}{k_m}=x_{k_{m-1}}-\frac{1}{k_{m-1}}$
it result
$x_{k_{m-1}}=\frac{1}{k_{m-1}}+\frac{1}{k_m} \tag{9''}$
If $k_{m-2}$ is the largest index $<k_{m-1}$ for wich $x_{k_{m-2}}\neq x_{k_{m-1}}$, that is
$\frac{1}{k_{m-1}}+\frac{1}{k_m}=x_{k_{m-1}}=x_{k_{m-1}+1}=\dots=x_{k_{m-2}+1} \tag{10''}$
then we get
$\frac{1}{k_{m-1}}+\frac{1}{k_m}\;\overset{(10'')}{=}$$x_{k_{m-2}+1}\overset{(8)}{\underset{for\;k_{m-2}}{=}}\;x_{k_{m-2}}-\frac{1}{k_{m-2}}$
and it result
$x_{k_{m-2}}=\frac{1}{k_{m-2}}+\frac{1}{k_{m-1}}+\frac{1}{k_m} \tag{9'''}$
(9'), (9''), (9''') as well as (10'), (10'') confirm the equations (E_3) from CiP_Comments above.
Further, in the words of the Authors of the Official Solutions :
"Restoring the sequence backwards in this way, we arrive at the desired formula."
It's about the formula (E_1), but the statement doesn't seem very convincing.
Let's say it's still good. But I hope it doesn't create confusion that I used the fraction $\frac{a}{b}$ in (1), in a different context.
I will now present one last example, to show that we can start the algorithm with any real number. The reader is advised to treat Examples 1-5 and the final one in my comments at the beginning in the same way. Let's choose a favorite number of Archimedes:
$x_1=-\frac{22}{7}$
$\color{Blue}s=[x_1]=\left [-4+\frac{6}{7}\right ]=\color{Blue}{-4}$
$x_2=\{x_1\}=\frac{6}{7}\;;$
we have $\frac{6}{7}\geqslant \frac{1}{2}$ so we choose in (2) $k_1=2$. The next term will therefore be different from $x_2$. Let's find it :
$x_3=\frac{\{2x_2\}}{2}=\frac{\left \{\frac{12}{7}\right \}}{2}=\frac{\left \{\frac{5}{7}\right \}}{2}=\frac{\frac{5}{7}}{2}=\frac{5}{14}\;;$
the calculation is also in agreement with (3). We have $\frac{5}{14}\geqslant 3$ so we choose in (2) $k_2=3$. Because $k_2-k_1=3-2=1$, this value appears only once in the string. Let's move on.
$x_4=\frac{\{3x_3\}}{3}=\frac{\left\{\frac{15}{14}\right \}}{3}=\frac{\frac{1}{14}}{3}=\frac{1}{42}$
and obvously $x_4\geqslant \frac{1}{42}$ so $k_3=42$. All of the following $k_3-k_2=42-3=39$ terms have the same value :
$x_4=x_5=\dots=x_{42}=\frac{1}{42}$
and finally $x_{43}=0.$ So $\color{Red}{m=3}$.
The calculation of the sum of nonzero terms has, in the official solution, the aspect
$x_1+x_2+\dots +x_{k_m}=s+k_1 \cdot \frac{1}{k_1}+k_2\cdot \frac{1}{k_2}+\dots +k_m\cdot \frac{1}{k_m}=s+m$
This did not appear obviously in the calculations of the previous examples, although the result was correct. That this is indeed the case follows if we write the terms in the form :
$x_4=\color{Violet}{\frac{1}{42}}\;\;\;\;\}\;k_3-k_2=39\;values$
$x_3=\color{Teal}{\frac{1}{3}}+\color{Violet}{\frac{1}{42}}\;\;\;\}\;k_2-k_1=1\;value$
$x_2=\color{Red}{\frac{1}{2}}+\color{Teal}{\frac{1}{3}}+\color{Violet}{\frac{1}{42}}\;\;\}\;k_1-1=1\;value$
$x_1=\color{Blue}{-4}+\color{Red}{\frac{1}{2}}+\color{Teal}{\frac{1}{3}}+\color{Violet}{\frac{1}{42}}\;\;\}\;1\;value$
We see that each value $\frac{1}{k_i}$ appears $k_i$ times. So this sum is $\color{Blue}s+\color{Red}m=-4+3=-1$.
$\blacksquare\;\blacksquare$
Niciun comentariu:
Trimiteți un comentariu