Problem A. 903. (March 2025)

A. 903. Let the irrational number $\displaystyle \alpha={1-\frac1{2a_1-\frac1{2a_2-\frac1{2a_3-\frac1{\dots}}}}}$, where coefficients $\displaystyle a_1$, $\displaystyle a_2$, $\displaystyle \ldots$ are positive integers, infinitely many of which are greater than $\displaystyle 1$. Prove that for every positive integer $\displaystyle N$ at least half of the numbers $\displaystyle \lfloor \alpha \rfloor, \lfloor 2\alpha \rfloor,\ldots , \lfloor N\alpha \rfloor$ are even. $\displaystyle \lfloor x \rfloor$ denotes the floor function of $\displaystyle x $, which is the greatest integer less than or equal to $\displaystyle x$.

Proposed by: Géza Kós, Budapest

(7 pont)

Deadline expired on April 10, 2025.

For an arbitrary irrational number $\displaystyle p$ and $\displaystyle C>0$ let

$\displaystyle S(c,p)=\sum_{0<k\le C} (-1)^{\lfloor kp \rfloor}. $

We have to prove that $\displaystyle S(N,\alpha)\ge 0$.

Lemma 1. For irrational numbers $\displaystyle p,q>1$ satisfying $\displaystyle \frac1p+\frac1q=1$ Beatty-sequences $\displaystyle \lfloor kp\rfloor$ ($\displaystyle k=1,2,...$) and $\displaystyle \lfloor lq\rfloor$ ($\displaystyle l=1,2,...$) contain every integer exactly once.

Proof. This statement is well known and easy to prove: positive integer $\displaystyle K$ appears in the first sequence $\displaystyle \lfloor \frac{K+1}{p}\rfloor-\lfloor \frac{K+1}{p}\rfloor$ times and in the second sequence $\displaystyle \lfloor \frac{K+1}{q}\rfloor-\lfloor \frac{K+1}{q}\rfloor$, and $\displaystyle \lfloor \frac{K+1}{p}\rfloor+\lfloor \frac{K+1}{q}\rfloor=K$, since $\displaystyle \frac{K+1}{p}+\frac{K+1}{q}=K+1$ and the addends are not integers. From this, the sum of the two number of occurences is $\displaystyle K-(K-1)=1$.

Lemma 2. For irrational numbers $\displaystyle p,q>0$ satisfying satisfying $\displaystyle \frac1p+\frac1q=1$ and $\displaystyle C>0$

$\displaystyle S\left(\frac{C}{p},p\right)+S\left(\frac{c}{q},q\right)\in \{0,-1\}. $

Proof. Let's count the number of occurences of positive integer $\displaystyle n$ in sequences $\displaystyle \lfloor kp\rfloor$ and $\displaystyle \lfloor lq\rfloor$, if $\displaystyle k\le \frac{C}{p}$ and $\displaystyle l\le \frac{C}{q}$. Clearly $\displaystyle n\le C$ (otherwise it won't appear in an any of the two sequences).

If $\displaystyle n+1\le C$, we have already seen that it will appear $\displaystyle \lfloor \frac{n+1}{p}\rfloor-\lfloor \frac{n}{p}\rfloor$ and $\displaystyle \lfloor \frac{n+1}{q}\rfloor-\lfloor \frac{n}{q}\rfloor$. The sum of these is 1.

If $\displaystyle n\le C <n+1$ (i.e. $\displaystyle n=\lfloor C\rfloor$), then it will appear $\displaystyle \lfloor \frac{C}{p}\rfloor -\lfloor \frac{n}{p}\rfloor$ and $\displaystyle \lfloor \frac{C}{q}\rfloor -\lfloor \frac{n}{q}\rfloor$. $\displaystyle \lfloor \frac{C}{p}\rfloor+ \lfloor \frac{C}{q}\rfloor = \lfloor C\rfloor $ or $\displaystyle \lfloor C\rfloor -1$, and $\displaystyle \lfloor \frac{n}{p}\rfloor+ \lfloor \frac{n}{q}\rfloor=n-1=\lfloor C\rfloor -1$, therefore the sum of occurences is 1 or 0. Thus

$\displaystyle S\left(\frac{C}{p},p\right)+S\left(\frac{c}{q},q\right)=\sum_{i=1}^n (-1)^i \text{ or } \sum_{i=1}^{n-1} (-1)^i=0 \text{ or } -1. $

Lemma 3. For any integer $\displaystyle a$

$\displaystyle S(C,a+2p)=S(c,p) \text{ and } S(C,2a-p)=-S(C,p). $

Proof. The first one is trivial, since the parities of the floors of $\displaystyle kp$ and $\displaystyle k(2a+p)$ are equal. The second follows from $\displaystyle \lfloor kp\rfloor + \lfloor k(2a-p)\rfloor=2ak-1$.

The solution of the problem. Let's define $\displaystyle p=2-\alpha={1+\dfrac1{2a_1-\dfrac1{2a_2-\dfrac1{2a_3-\dfrac1{~\cdots~}}}}}$, $\displaystyle q=\frac{1}{1-\frac1p}=\frac{p}{p-1}=1+\frac{1}{p-1}=1+2a_1-\dfrac1{2a_2-\dfrac1{2a_3-\dfrac1{~\cdots~}}}=2a_1+\alpha'$, where $\displaystyle \alpha'$ is defined as $\displaystyle \alpha'=1-\dfrac1{2a_2-\dfrac1{2a_3-\dfrac1{~\cdots~}}}$. Clearly $\displaystyle \frac{1}{p}+\frac{1}{q}=1$, and so

$$\begin{align*} \text{Lemma 3:} &\qquad S\Big(A,\alpha\Big) + S\Big(A,p\Big) =0, \\ \text{Lemma 2:} &\qquad S\Big(A,p\Big) +S\Big(\dfrac{p}{q}A,q\Big) =\varepsilon\in\big\{0,-1\big\} \\ \text{Lemma 3:} &\qquad S\Big(\dfrac{p}{q}A,q\Big) = S\Big(\dfrac{p}{q}A,\alpha'\Big), \end{align*}$$

therefore

$\displaystyle S(A,\alpha)=S\left(\frac{p}{q}A,\alpha'\right)-\varepsilon\ge S\left(\frac{p}{q}A,\alpha'\right). $

This means that we can replace $\displaystyle A$ and $\displaystyle \alpha$ by $\displaystyle \frac{p}{q}A$ and $\displaystyle \alpha'$ without increasing the value of $\displaystyle S(A,\alpha)$. Now let's iterate this step. Note that $\displaystyle \frac{p}{q}=p-1\le \frac{1}{2a_1-1}\le 1$, so the value of $\displaystyle A$ cannot increase, and since infinitely many times $\displaystyle \frac{p}{q}$ will be at most $\displaystyle \frac{1}{3}$ (in each step when $\displaystyle a_i>1$, since in this case $\displaystyle \frac{1}{2a_i-1}$), the value of $\displaystyle A$ will eventually become smaller than 1, in which case we clearly get 0 as a result (the defining sum being empty), therefore our proof is finished.

Statistics:

5 students sent a solution.

7 points: Bodor Mátyás, Szakács Ábel, Varga Boldizsár, Xiaoyi Mo.

1 point: 1 student.

Problems in Mathematics of KöMaL, March 2025

5 students sent a solution.
7 points:	Bodor Mátyás, Szakács Ábel, Varga Boldizsár, Xiaoyi Mo.
1 point:	1 student.

Already signed up?
New to KöMaL?