A Problem That Has a Chance of Becoming a Theorem // Problema, kuri gali tapti teorema

          I heard the expression in the title from a somewhat megalomaniac fellow mathematician.

          It does, and we will try to prove the following formula :

                    Let be the nonzero numbers  $a_1,\;\dots a_m$. The following equation holds :

$a_1\cdot \left ( \frac{1}{a_1}+\frac{1}{a_2}+\frac{1}{a_3}+\dots +\frac{1}{a_m}\right )+(a_2-a_1)\cdot \left ( \frac{1}{a_2}+\frac{1}{a_3}+\dots +\frac{1}{a_m}\right )+$

$+(a_3-a_2)\cdot \left (\frac{1}{a_3}+\dots +\frac{1}{a_m}\right )+\dots+(a_{m-1}-a_{m-2})\cdot \left ( \frac{1}{a_{m-1}}+\frac{1}{a_m}\right )+$

$+(a_m-a_{m-1})\cdot \frac{1}{a_m}=m \tag{1}$

I seem to see that a "proof without words" is imminent.

A Mathematical Olympiad in the middle of nowhere // O Olimpiadă de Matematică la dracu-n praznic

 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$

Problem #1 from JBMO TEAM SELECTION TEST 2025 - GREECE

 Obtained from here.

         "Problem 1.

           (a) Let the positive integers  $p,\;q$  be prime numbers and let  $a$  be a positive

           integer. If  $a$  divides the product  $p\cdot q$ , and it holds that  $a>p$  and  $a>q$ , 

           prove that  $a=pq$.

          (b) Determine all pair  $(p,q)$  of prime numbers such that  $p^2+3pq+q^2$ 

           eqals a perfect square."

ANSWER CiP

(b)  $(3,\;7)$  and  $(7,\;3)$

Solution CiP

(a)  $a\mid p\cdot q\;\Rightarrow\;\;p\cdot q=a\cdot b$  for a certain  $b\in \mathbb{N}$. Noting that  $p$  divides the product $a\cdot b$ then, since it is prime, it follows

$$p\mid a\;\;\;or\;\;\;p\mid b.$$

      If  $p\mid a$, then  $a=p\cdot c$  for a certain  $c\in \mathbb{N}$. Then, from

$p\cdot q= (p\cdot c)\cdot b$  we obtain  $q=c\cdot b$. But  $q$  is also prime so we can have  $c=1$ (when  $q=b,\;p=a$  which contradicts  $a>p$)  or $b=1$ , in which case  $q=c$  and $a=pq$.

      If  $p\mid b$,  then $b=p\cdot d$  for a certain  $d\in\mathbb{N}$. Then, from  $p\cdot q=a(p\cdot d)$  we obtain  $q=a\cdot d$, but $q$ being prime and  $a>1$  it follow  $d=1,\;q=a$  wich contradicts  $a>q$.

With these,  (a)  is proven.

(b) If  $k\in \mathbb{N}$ is such that  $p^2+3pq+q^2=k^2$  then we get

$$pq=k^2-p^2-2pq-q^2=k^2-(p+q)^2=(k-p-q)\cdot (k+p+q)$$

From the above it can be seen that the number  $a:=k+p+q>p,\;q$  divides the product  $pq$. According to (a) we must have $a=pq$  that is, equivalent to

$k+p+q=pq\;\Rightarrow\;k=pq-p-q\;\;\Rightarrow\;\;p^2+3pq+q^2=(pq-p-q)^2\;\:\Leftrightarrow$

$\Leftrightarrow\;pq=p^2q^2-2p^2q-2pq^2\;\;\Leftrightarrow\;\;1=pq-2p-2q\;\Leftrightarrow\;5=pq-2p-2q+4\;\Leftrightarrow$

$$\Leftrightarrow\;\;\;5=(p-2)(q-2).$$ 

Then it follows that  $p-2=1$  or  $p-2=5$. We get the answer.

          Verification:  $3^2+3\cdot 3\cdot 7+7^2=9+63+49=121=11^2$.

$\blacksquare$

An UNSOLVED completely problem from Sierpiński

 It is Problem #4, page 16 mentioned in the cited work. Edited from the manuscript.

In translation : 

                           "Prove that there are infinitely many natural numbers  $n$  for which

                          the number  $4n^2+1$ is divisible by both  $5$  and  $13$."

               The author's[WS] solution is on page 38. (The text is written in green.) In translation:

                         "ANSWER : All numbers in the arithmetic progression

 $65k+56,\;\;k=0,\;1,\;2\dots$

[I noticed at the bottom of the page in the first photo that there is no indication of how to find the answer. Then comes its Solution :]

          Indeed, if  $n=65k+56$ , $k\geqslant 0$ is an integer, then  $n\equiv 1\;(mod\;5)$ and $n\equiv 4\;(mod\;13)$ from where  $4n^2+1\equiv 0\;(mod\;5)$ and  $4n^2+1\equiv 0\;(mod\;13)$, so that 

$5\mid 4n^2+1$  and  $13\mid 4n^2+1.$

$\color {Green}{\blacksquare}$"

                I solved the problem without knowing this answer. [Text written in blue; in translation:]

ANSWER CiP

The numbers that have the property in the statement are exactly those of the form

$65k+4,\;\;65k+9,\;\;65k+56,\;\;65k+61$  where  $k=0,\;1,\;2,\dots\;.$

                   Solution CiP

               Since  $5$  and  $13$  are coprime, we have

$5\mid A\;\;and\;\;13 \mid A\;\;\;\Leftrightarrow\;\;\;5\cdot 13 \mid A$

Let  $n=65k+r$ ;  then  $4n^2+1=4(65k+r)^2+1=4(65^2k^2+2\cdot 65\cdot r+r^2)+1=$

$=65\cdot(4\cdot 65k^2+8r)+4r^2+1=65k_1+4r^2+1.$

Trying to choose a number  $r$  so that  $4r^2+1=65$  we get  $r^2=16$. For example  $r=4$, so we have an infinity of numbers, of the form  $n=65k+4$, with the property in the statement. The problem would be solved [, but not completely.]

$\color {Blue}{\blacksquare}$

       I noted in red, further on, that we can also have  $r=-4$, obtaining another infinity of convenient numbers. 

         - And all the convenient values ​​found in my answer were obtained by checking all the possibilities

$65k,\;65k\pm1,\;65k\pm2,\;\dots,\;65k\pm32$

     Finally, I also noted, [written in black], that : The numbers in ANSWER CiP form the sequence

 A203464 in OEIS ("The On-Line Encyclopedia of Integer Sequences).

АXA! Немам ПОИМ!! // AHA! I have NO IDEA!!

 It's a parody of the title of Martin ERICKSON's  book "Aha! Solutions" 

          The Problems Given at the Dam for JBMO in North Macedonia fell into my hands. I said I'd try my hand at Problem 1. 

            "1.  Let  $n>1$ be a natural number and  $m>2$  a divisor of  $2n$. Prove that

               the number  $n^2$ can be written as the sum of  $m$ nonzero perfect squares."

          I have no idea how to solve this, so for now I'm just showing a few

          EXAMPLES CiP

           a) $n=2$ :  $2<m \mid 4\;\;\Rightarrow\;\;m=4$.  We have the equation

$2^2=1+1+1+1$

          b) $n=3$ :  $2<m \mid 6\;\;\Rightarrow\;\;m=3$ or $m=6$. We have the equations

$3^2=1+4+4$

$3^2=1+1+1+1+1+4$

          c) $n=4$ :  $2<m \mid 8\;\;\Rightarrow\;\;m=4$ or $m=8$. We have the equations

$4^2=4+4+4+4$

$4^2=1+1+1+1+1+1+1+9$

Let's hope that inspiration will help me solve the problem.

Edited Friday 06 June  The following Lemma, which I will now formulate only as a Conjecture, would be helpful:

               Lemma CiP (Conjecture) Whatever the prime number  $p>2$, the

                                                  number  $p^2$ can be written as the sum of  $p$ squares.

          So we have an equation like this

$$p^2=a_1^2+a_2^2+\dots +a_p^2=\sum_{i=1}^pa_i^2 \tag{P}$$

          Examples:

$3^2=\underset{3-terms}{\underbrace{1+4+4}}$

$5^2=\underset{5-terms}{\underbrace{4+4+4+9}}$

$7^2=\underset{7-terms}{\underbrace{1+1+4+9+9+9+16}}$

For the following example we proceed by trial and error:

$11^2=\underset{4-terms}{\underbrace{5+16+36+64}}\;\overset{we\;replace\; 16\; with\; a}{\underset{sum\;of\;several\;terms}{=}}\;\underset{7-terms}{\underbrace{5+4+4+4+4+36+64}}=$

and now if we replace the term  $5$ with the sum  $1+1+1+1+1$  we are lucky to obtain the desired result, so

$11^2=\underset{11-terms}{\underbrace{1+1+1+1+1+4+4+4+4+36+64}}$

Until we find a proof for the Lemma, let us observe that if for two prime numbers $p>2$ and $q>2$ we have decompositions  (P) and

$$q^2=\sum_{j=1}^qb_j^2$$

then because

$$\left ( \sum_{i=1}^pa_i^2\right )\cdot \left (\sum_{j=1}^qb_j^2 \right )=\sum_{i,j=1}^{i=p,j=q}a_i^2b_j^2$$

we obtain a sum of  $p\cdot q$  squares 

$$p^2\cdot q^2=\sum_{i,j=1}^{i=p,j=q}(a_i\cdot b_j)^2 \tag{PQ}$$

<end Edit 06 June>

Weekend Edition (There are no days off in Mathematics. When you are struggling with a problem, you are constantly thinking about it.) 

          But what if the property in yesterday's Lemma holds for any number  $n>2$ ? 

          Also by trying, as for number  $121$ , I obtained the following equations:

$4^2=\underset{4-terms}{\underbrace{4+4+4+4}}$

$6^2=\underset{6-terms}{\underbrace{1+1+1+4+4+25}}$

$8^2=\underset{8-terms}{\underbrace{1+1+1+1+1+1+9+49}}$

$9^2=\underset{9-terms}{\underbrace{1+1+1+1+1+4+4+4+64}}$

Ugh!, no pattern is visible. Worse, if we start from equation for  $3^2=1+4+4$ and square it (or rather multiply it by itself),

$3^2 \cdot 3^2=(1+4+4)\cdot (1+4+4)=\dots $ (the $3\times 3=9$ terms obtained by multiplication are all squares)

 we find an equation for  $9^2$ that differs from what I obtained:

$9^2=\underset{9-terms}{\underbrace{1+4+4+4+4+16+16+16+16}}$

So, we don't have unique writings for the representations we're looking for. Complicated stuff...

<end Weekend Edition>

          I couldn't be patient anymore and I consulted the solution to the problem. As expected, the problem should be quite simple. I'm saved !

          You can also consult the solution from where I got the problem statement.

          As a consolation for how much I've been struggling these days, the statement that I considered above as a Lemma is true. In fact, the following are true:

    (a)   For any number  $n\geqslant 3$, the number  $n^2$ can be written as a sum

            of  $n$ nonzero perfect squares.

    (b)   For any number  $n\geqslant 2$, the number  $n^2$ can be written as a sum

             of  $2\cdot n$ nonzero perfect squares.

 To my shame, these statements are almost trivial. If you only showed them, you would get 2 points on the solution scale. For just one, you would get nothing.

        Proof of (a) : We have that

  $n^2=(n^2-4\cdot n +4)+4\cdot n-4=(n-2)^2+4\cdot (n-1)$  so

$$n^2=\underset{1-term}{\underbrace{(n-2)^2}}+\underset{n-1\;-terms}{\underbrace{4+4+\dots+4}}$$

     Examples (that differ from those I found) : 

$6^2=4^2+4+4+4+4+4$

$7^2=5^2+4+4+4+4+4+4$

$8^2=6^2+4+4+4+4+4+4+4$

$9^2=7^2+4+4+4+4+4+4+4+4$

$10^2=8^2+4+4+4+4+4+4+4+4+4$

$11^2=9^2+4+4+4+4+4+4+4+4+4+4$

       Proof of (b) :  We have that

$n^2=(n^2-2\cdot n+1)+2n-1=(n-1)^2+(2n-1)\cdot 1$   so

$$n^2=\underset{1-term}{\underbrace{(n-1)^2}}+\underset{2\cdot n-1\;-terms}{\underbrace{1+1+\dots +1}}$$

Note that (a) is the particular case with  $m=n$ of the Problem, and (b) is the particular case  $m=2n$ of it.

                    Official Solution (adapted by CiP)

Let  $k=\frac{2n}{m}$; it is, from the divisibility condition, a natural number, $k\geqslant 1$. From

$n^2=(n^2-2 n k+k^2)+2nk-k^2\;\;\overset{2n=k\cdot m}{=}\;(n-k)^2+km\cdot k-k^2=(n-k)^2+k^2 \cdot (m-1)$

and because  $n-k=\frac{2n}{2}-k=\frac{k\cdot m}{2}-k=k\cdot \left (\frac{m}{2}-1\right )>0$

we have

$$n^2=(n-k)^2+\underset{m-1\;-terms}{\underbrace{k^2+\dots +k^2}}$$

QED $\blacksquare$

मलाही या समस्येची लाज वाटेल.

   शीर्षकाचे भाषांतर असे आहे: I would be ashamed of this problem too"

Someone, signed "ANONYMOUS", commented on yesterday's post. I wanted to delete the comment, usually insulting, but I researched it and the guy is right. He, in the comment, refers to this problem:

In translation:

                      "10.     Show that if   $a,\;b,\;c \in \mathbb{R}$  and  $ab+bc+ca=0$ , then

$2\sqrt{a^2+b^2+c^2}\geqslant 3\sqrt[3]{|abc|}.$

C. Ionescu-Țiu "

Indeed, the problem is a bit strange. Unless it is a typographical error, it insults the intelligence of a solver with minimal knowledge. I won't bother with it any further, I'll just say this:

 it is true under any conditions for any numbers  $a,\;b,\;c$  not just those that satisfy the relation $ab+bc+ca=0$. In addition, the  $=$  sign only occurs in the case of  $a=b=c=0$.

          Proof  CiP  For non-negative numbers $x,\;y,\;z$ , holds the inequality

  AM-GM :   $\frac{x+y+z}{3}\geqslant \sqrt[3]{xyz}$ 

 so

$x+y+z\geqslant 3\cdot \sqrt[3]{xyz}$

Replacing above $x=a^2,\;y=b^2,\;z=c^2$, where the numbers  $a,\;b,\;c$  are arbitrary, not bound by any condition, we obtain

$a^2+b^2+c^2\geqslant 3\cdot \sqrt[3]{a^2b^2c^2}$

and taking the square root of both sides we have

$$2\cdot \sqrt{a^2+b^2+c^2}\geqslant 2\sqrt{3}\cdot \sqrt[3]{|abc|}$$

But, since  $2\sqrt{3}=\sqrt{12}>\sqrt{9}=3$, the above results in

$$2\sqrt{a^2+b^2+c^2}>3\cdot \sqrt[3]{|abc|}\;.$$

$\blacksquare$

More in Joke, more in Serious : A Problem Close to Logic

 I don't expect C. Ionescu-Țiu to show much logic in His Problems. Here is Problem E:6061 from the magazine in the picture.

I have published more about this issue of the Magazine elsewhere.

In translation:

                        "E:6061*. Consider the real and positive numbers  $a,\;b,\;c,\;d$  such

                        that $a+b=c+d$.  Show that:

                          1). If  $ab>cd$  then  $a^2+b^2<c^2+d^2$  and the converse.

                          2). If  $ab>cd$  then  $|a-b|<|c-d|$.

                          3). If  $a^2+b^2<c^2+d^2$  then  $|a-b|<|c-d|$  and the converse."

          Solution CiP (an improvised solution, at the school level)

               Let us remember that everywhere in what follows holds the equation:

$a+b=c+d \tag{1}$

               1). Direct implication:         $ab>cd\;\Rightarrow\;a^2+b^2<c^2+d^2$

(1)$\;\Rightarrow\;\;(a+b)^2=(c+d)^2$

$\Rightarrow\;\;a^2+b^2+2\cdot ab=c^2+d^2+2\cdot cd$

$\Rightarrow\;\;a^2+b^2-c^2-d^2=2\cdot (cd-ab)$

and from hypothesis  $ab>cd$  it follows  $cd-ab<0$,  so  $a^2+b^2-c^2-d^2<0$, or equivalently : $a^2+b^2<c^2+d^2$.

qed

                    Converse implication :          $a^2+b^2<c^2+d^2\;\Rightarrow\;ab>cd$ 

              $a^2+b^2<c^2+d^2\;\;\Rightarrow\;\;-a^2-b^2>-c^2-d^2\;\;\underset{(1)}{\Rightarrow}$

$\Rightarrow\;\;(a+b)^2-a^2-b^2>(c+d)^2-c^2-d^2\;\;\Leftrightarrow\;\;2\cdot ab>2\cdot cd\;\;\Leftrightarrow\;\;ab>cd$

qed

          Remark CiP  Based on the equation

$a^2+b^2-c^2-d^2=2\cdot (cd-ab)$

we have the logical equivalence

$a^2+b^2-c^2-d^2<0\;\;\;\Leftrightarrow\;\;\;cd-ab<0$

and the statement  "1)" is obtained immediately.

<end Rem>

               2). Implication:   $ab>cd\;\;\Rightarrow\;\;|a-b|<|c-d|$

$ab>cd\;\;\Rightarrow\;\;-4\cdot ab<-4\cdot cd\;\;\Rightarrow\;\;(a-b)^2-(a+b)^2<(c-d)^2-(c+d)^2\;\;\Rightarrow$

$\;\underset{(1)}{\Rightarrow}\;\;(a-b)^2<(c-d)^2\;\;\Rightarrow\;\;\sqrt{(a-b)^2}<\sqrt{(c-d)^2}\;\;\Leftrightarrow\;\;|a-b|<|c-d|$.

qed

          Remark CiP

                 a)  The converse is also valid:  $|a-b|<|c-d|\;\;\Rightarrow\;\;ab>cd$

Because  $|a-b|<c-d|\;\;\Rightarrow\;\;(a-b)^2<(c-d)^2\;\;\Rightarrow\;\;-(a-b)^2>-(c-d)^2\;\;\Rightarrow$

$\underset{(1)}{\Rightarrow}\;\;(a+b)^2-(a-b)^2>(c+d)^2-(c-d)^2\;\;\Leftrightarrow\;\;4\cdot ab>4\cdot cd$, &c...

                 b) As in the Remark from point 1), we can prove point 2) together with its converse, based on the equation

$(a-b)^2-(c-d)^2=4\cdot(cd-ab)$

<end Rem>

               3).  Direct implication:     $a^2+b^2<c^2+d^2\;\;\Rightarrow\;\;|a-b|<|c-d|$

From  $2a^2+2b^2<2c^2+2d^2\;\;\Rightarrow\;\;(a+b)^2+(a-b)^2<(c+d)^2+(c+d)^2\;\;\Rightarrow$

$\underset{(1)}{\Rightarrow}\;\;(a-b)^2<(c-d)^2\;\;\Rightarrow\;\;\sqrt{(a-b)^2}<\sqrt{(c-d)^2}\;\;\Leftrightarrow\;\;|a-b|<|c-d|$

qed

                     Converse implication:     $|a-b|<|c-d|\;\;\Rightarrow\;\;a^2+b^2<c^2+d^2$

From the hypothesis  $|a-b|<|c-d|$  follows immediately the inequality  

$(a-b)^2<(c-d)^2 \tag{2}$

$\Rightarrow\;\;2a^2+2b^2-4ab<2c^2+2d^2-4cd\;\;\Rightarrow\;\;2(a^2+b^2-c^2-^2)<4ab-4cd=$

$=(a+b)^2-(a-b)^2-[(c+d)^2-(c-d)^2]\underset{(1)}{=}(c-d)^2-(a-b)^2\underset{(2)}{<}0.$

qed

               Remark CiP   Both implications, direct and converse, result at once from the equation

$2(a^2+b^2-c^2-d^2)=(c-d)^2-(a-b)^2$

<end Rem>

With this we solved the exercise, and something extra.

                    Final Remarks CiP

               1.  For the logical propositions:

$p :  ab>cd$

$q :  a^2+b^2<c^2+d^2$

$r :   |a-b|<|c-d|$

we have the logical equivalents

$p\;\;\Leftrightarrow\;\;q\;\;\Leftrightarrow\;\;r$

               2.  Due to the symmetry in $a$ and $b$ on the one hand and in $c$ and $d$ on the other hand, we could assume from the beginning that  $a\leqslant b$ and $c\leqslant d$. With this, the proposition $p$ is true  $\Leftrightarrow\;\;ab\underset{(1)}{>}c(a+b-c)\;\;\Leftrightarrow\;\;c^2-c(a+b)+ab>0\;\;\Leftrightarrow\;\;(c-a)(c-b)>0\;\;\Leftrightarrow\;\;c\in (0,\;a)\cup (b,\;+\infty)$.

and similar for $d$, so ultimately we have on the real axis the ordering $0<c<a\leqslant b<d$, to which is added the condition that the segments with ends $a$ and $b$, respectively $c$ and $d$ have the same midpoint.

$\blacksquare$