(i) is trivial since $x_n$ is bounded. Call $x_n>L$ big and small othersise, then we prove big turns to small, small turns to small iff $x_n=\lfloor\frac{\alpha}{\alpha -1}\rfloor ,$ and if small never turns to small the number keeps decreasing and get contradiction.

We ignore (i) because its trivial. Here's a pretty sus solution which might be wrong but probably encapsulates the main idea. WLOG we can take $L < x_1 < \left\lceil \alpha L \right\rceil$ else we can take the first term which satisfies so. Then we define \[ L_1 = \left\{\left\lfloor \frac{L}{\alpha} \right\rfloor\right\}, L_2 = \left[\left\lceil \frac{L}{\alpha} \right\rceil, L\right], L_3 = \left[L+1, \left\lfloor \alpha L \right\rfloor\right] \]Then $x_i$ just alternates \[ L_3 \mapsto L_2 \mapsto L_2 \dots \]under the operation. Note that the operation $L_3 \mapsto L_2 \mapsto L_3$ is strictly decreasing so eventually it jumps $L_3 \mapsto L_1$ or $L_2 \mapsto L_2$ as exactly one of $\left\lfloor\frac{L+1}{\alpha}\right\rfloor < \left\lceil \frac{L}{\alpha} \right\rceil$ or $\left\lfloor \alpha \left\lceil \frac{L}{\alpha} \right\rceil \right\rfloor < L + 1$ holds. In the first case the sequence contains $L_1$ and is thus always the same, and is odd since it has one $L_1$ and paired $L_2, L_3$. In the case of $L_2 \mapsto L_2$ this means that the sequence contains $\left\lceil \frac{L}{\alpha} \right\rceil$ and is thus always the same, and cyclic because $L_2$ repeats itself iff when that happens.

YaoAOPS wrote: We ignore (i) because its trivial. Here's a pretty sus solution which might be wrong but probably encapsulates the main idea. WLOG we can take $L < x_1 < \left\lceil \alpha L \right\rceil$ else we can take the first term which satisfies so. Then we define \[ L_1 = \left\{\left\lfloor \frac{L}{\alpha} \right\rfloor\right\}, L_2 = \left[\left\lceil \frac{L}{\alpha} \right\rceil, L\right], L_3 = \left[L+1, \left\lfloor \alpha L \right\rfloor\right] \]Then $x_i$ just alternates \[ L_3 \mapsto L_2 \mapsto L_2 \dots \]under the operation. Note that the operation $L_3 \mapsto L_2 \mapsto L_3$ is strictly decreasing so eventually it jumps $L_3 \mapsto L_1$ or $L_2 \mapsto L_2$ as exactly one of $\left\lfloor\frac{L+1}{\alpha}\right\rfloor < \left\lceil \frac{L}{\alpha} \right\rceil$ or $\left\lfloor \alpha \left\lceil \frac{L}{\alpha} \right\rceil \right\rfloor < L + 1$ holds. In the first case the sequence contains $L_1$ and is thus always the same, and is odd since it has one $L_1$ and paired $L_2, L_3$. In the case of $L_2 \mapsto L_2$ this means that the sequence contains $\left\lceil \frac{L}{\alpha} \right\rceil$ and is thus always the same, and cyclic because $L_2$ repeats itself iff when that happens. It is actually possible to uniformly use \(\lfloor (L+1)/\alpha \rfloor\) as the same element.

Seeing this graphically and also trying examples does help a lot, in fact it's the main motivation/idea to make progress on this. (i) is trivial because of bounded eventually, so for (ii) we consider a number line where $L$ is in "the middle" and numbers on the left are greater than $L$ and number from $L$ to the right are smaller than $L$ notice that from the left for any $x_i$ where jumping to the right started, the main observations to be made is that if in a process we go from left to right and right to left, next time we go left to right, the resulting number is decreased by exactly $1$ unit. This is because like if you had $\left \lfloor \frac{x_n}{\alpha} \right \rfloor=k \le L$ then $x_n$ lies on $((k+1)\alpha, k\alpha)$, but then $\lfloor \alpha k \rfloor$ is the first integer below the range of the $x_n$ (so it obviously lies on $(k \alpha, (k-1) \alpha)$ (which contains an integer at least as $\alpha>1$)) which would mean that when this number jumps to the right again (which has to because its smaller than the first one that jumped to the right) then it lands exactly on $k-1$, now if we never had a case where right jumps to right then $k$ would constsntly decreasing until becoming zero in which case period if $1$, so assume this doesn't happen, then whenever it first reaches an $l$ for which $\lfloor \alpha l \rfloor$ is still on the right, then you do process one again and then whatever is on the left still goes to the right as it is the result of launching something to the right by $\alpha$ minus some (mostly likely) small constant. They key part is that this $l$ is unique because as we have seen previously, from some value $k$ taken after two steps it decreases by exactly one unit, however we have to verify that we don't need over $3$ steps to launch the value $l$ back to the left so first start by noticing that from the problem condition no value below $\left \lfloor \frac{\alpha}{\alpha-1} \right \rfloor \ge 1$ is taken for size reasons so notice $l$ is the first ever positive integer for which you have to jump twice which means that $\lfloor \alpha (l+1) \rfloor \ge L+1$, so if we suddently have that $L \ge \lfloor \alpha \lfloor \alpha l \rfloor \rfloor$, then notice that $l \ge \left \lceil \frac{L+1}{\alpha} \right \rceil-1$ so in fact from the definition of $l$ equality is true which then gives that $\left \lfloor \frac{L}{\alpha} \right \rfloor \ge \lfloor \alpha l \rfloor -1$, now let $\ell$ be a positive integer such that $\lfloor (\ell+1)\alpha \rfloor>L \ge \lfloor \ell \alpha \rfloor$ then $\ell \ge \left \lfloor \alpha \cdot \left \lfloor \frac{L+1}{\alpha} \right \rfloor \right \rfloor \ge \lfloor \alpha \cdot \ell \rfloor$ as $L+1 \ge \lceil \alpha \ell \rceil$ which means that $\frac{1}{\alpha-1}>\ell$, but this can't be possible as we get that $\frac{\alpha^2}{\alpha-1}>(\ell+1)\alpha>L$ contradiction the problem condition, thus we are done .

I don't understand how (i) is trivial if the sequence is bounded. If we consider the sequence of digits of pi, each term is bounded, but the sequence is non-periodic since pi is irrational.

KuroNeko2007 wrote: I don't understand how (i) is trivial if the sequence is bounded. If we consider the sequence of digits of pi, each term is bounded, but the sequence is non-periodic since pi is irrational. Because $x_{n+1}$ is integer and only need $x_n$

The sequence is eventually periodic because it is bounded by $\lfloor \max(x_1,\alpha L)\rfloor$, so it can only take on finitely many values. Call $x_i$ big if $x_i>L$ and small otherwise. Let $D$ be the smallest index such that $x_D$ is small. $D$ must exist otherwise $x_n$ is strictly decreasing, contradiction. Hereby assume $i>D$. Claim: For all big numbers $x_i$, $x_{i+1}$ is small. Let $i$ be the smallest index such that $x_i$ and $x_{i+1}$ are both big. Then, $x_{i-1}$ is small. We have \[x_i=\lfloor \alpha x_i \rfloor<\alpha x_i\le \alpha L\implies x_{i+1}<\left\lfloor\frac{\alpha L}{\alpha} \right\rfloor\]so $x_{i+1}$ is small, contradiction. Claim: If $x_i$ and $x_{i+2}$ are big, then $x_{i+2}<x_i$. Note that $x_{i+1}$ is small. We have \[x_{i+1}=\left\lfloor\frac{x_i}{\alpha} \right\rfloor<\frac{x_i}{\alpha}\implies x_{i+2}=\lfloor \alpha x_{i+1}\rfloor<\alpha x_{i+1}<x_i\]as desired. Claim: There exists at most one value of $x_i$ that is small such that $x_{i-1}$ is big but $x_{i+1}$ is small. We have $x_{i+1}\le L$. Since $x_{i}$ is small, \[\lfloor \alpha x_{i} \rfloor\le L\implies \alpha x_{i} < L+1\implies x_{i} <\frac{L+1}{\alpha}\]Since $x_{i-1}$ is big, \[x_{i-1}\ge L+1\implies x_i=\left\lfloor \frac{x_{i-1}}{\alpha}\right \rfloor > \frac{L+1}{\alpha}-1\]The difference between the strict upper and lower bounds of $x_i$ is one. Therefore, $x_i$ attains at most one value. Claim: There does not exist any values $x_i$ that are small such that $x_{i-1}$ and $x_{i+1}$ are both small. Assume that $i$ does exist and is minimal, then $x_{i-2}$ is big. Then $x_{i-1} =\frac{L+y}{\alpha}-1$ for some $y>1$ so \[x_{i}>\left\lfloor \alpha x_{i-1}\right\rfloor=\left\lfloor \alpha \frac{L+y}{\alpha}-\alpha\right\rfloor=\left\lfloor L+y-\alpha\right\rfloor = L - \lceil \alpha-y \rceil > L-\lceil \alpha\rceil +1>L-\alpha+1\]This implies that \[L\ge x_{i+2}>\alpha(L-\alpha+1)-1\]which ends up being a contradiction to the bound given in the problem. Construct a colored directed graph over all the positive integers such that $x_i\to x_{i+1}$ is red if $x_i$ is big and blue if $x_i$ is small. We have already suggested that starting from any vertex and following the edges, the path eventually cycles. Note that if a cycle goes $\text{red}\to\text{blue}$ alternating only, then the source of all red edges decreases strictly, which cannot happen. Therefore, there must be at least one $\text{blue} \to \text{blue}$. By our previous two claims, there must be at most one $\text{blue}\to \text{blue}$. Therefore, each cycle alternates except at one point, so each cycle is the same odd cycle. We are done.

>opens thread cuz found the sum too hard >someone calls it trivial >FML

Let $S = [\lfloor (L+1)/\alpha\rfloor, \lfloor (L+1)\alpha\rfloor]\cap\mathbb{N}, \ A = [\lfloor (L+1)/\alpha\rfloor, L]\cap\mathbb{N}, \ B = [L+1, \lfloor (L+1)\alpha\rfloor]\cap\mathbb{N}$ Claim 1: if $x_1$ is greater than $\lfloor (L+1)\alpha\rfloor$, then there exists $k>1$ such that $\lfloor x_k/\alpha\rfloor\in B$. Proof: Note that if $x_i>L$, then $x_{i+1}=\lfloor x_i/\alpha\rfloor<x_i$ (as $\alpha>1$). But, there are only finitely many integers between $L$ and $x_1$. Hence there must exist $n>1$ such that $x_n\le L$ and $x_{n-1}>L$. So, we get $x_{n-1}\le\lfloor (L+1)\alpha\rfloor$. So, $x_{n-1}\in B$. Claim 2: if $x_1$ is lesser than $\lfloor (L+1)/\alpha\rfloor$, then there exists $k>1$ such that $\lfloor x_k/\alpha\rfloor\in A$. Proof: Note that if $x_i<L$, then $x_{i+1}=\lfloor x_i\alpha\rfloor>x_i$ (as $\alpha>1$). But, there are only finitely many integers between $L$ and $x_1$. Hence there must exist $n>1$ such that $x_n\ge L+1$ and $x_{n-1}\le L$. So, we get $x_{n-1}>\lfloor (L+1)/\alpha\rfloor$. So, $x_{n-1}\in A$. Observe that if $x_k\in A$, then $x_{k+1}\in B$; and if $x_k\in B$, then $x_{k+1}\in A$. Also, there are finitely many integers in $S=A\cup B$. So, $\{x_i\}$ must be eventually periodic. Now consider the following bipartite graph with vertex sets as $A$ and $B$. We draw an edge directed from $a$ and $b$ if and only if $\exists \ i\ge 1$ such that $x_i=a$ and $x_{i+1}=b$. Clearly, there cannot be an edge between two elements of $A$ or two elements of $B$. Also, note that there is exactly one cycle in this directed bipartite graph as the sequence becomes eventually periodic. Since the graph is bipartite, the length of the cycle must be even. So, the fundamental period of the sequence, which is just 1 less than the cycle length, will be odd.

Fibonacci_math wrote: Let $S = [\lfloor (L+1)/\alpha\rfloor, \lfloor (L+1)\alpha\rfloor]\cap\mathbb{N}, \ A = [\lfloor (L+1)/\alpha\rfloor, L]\cap\mathbb{N}, \ B = [L+1, \lfloor (L+1)\alpha\rfloor]\cap\mathbb{N}$ Claim 1: if $x_1$ is greater than $\lfloor (L+1)\alpha\rfloor$, then there exists $k>1$ such that $\lfloor x_k/\alpha\rfloor\in B$. Proof: Note that if $x_i>L$, then $x_{i+1}=\lfloor x_i/\alpha\rfloor<x_i$ (as $\alpha>1$). But, there are only finitely many integers between $L$ and $x_1$. Hence there must exist $n>1$ such that $x_n\le L$ and $x_{n-1}>L$. So, we get $x_{n-1}\le\lfloor (L+1)\alpha\rfloor$. So, $x_{n-1}\in B$. Claim 2: if $x_1$ is lesser than $\lfloor (L+1)/\alpha\rfloor$, then there exists $k>1$ such that $\lfloor x_k/\alpha\rfloor\in A$. Proof: Note that if $x_i<L$, then $x_{i+1}=\lfloor x_i\alpha\rfloor>x_i$ (as $\alpha>1$). But, there are only finitely many integers between $L$ and $x_1$. Hence there must exist $n>1$ such that $x_n\ge L+1$ and $x_{n-1}\le L$. So, we get $x_{n-1}>\lfloor (L+1)/\alpha\rfloor$. So, $x_{n-1}\in A$. Observe that if $x_k\in A$, then $x_{k+1}\in B$; and if $x_k\in B$, then $x_{k+1}\in A$. Also, there are finitely many integers in $S=A\cup B$. So, $\{x_i\}$ must be eventually periodic. Now consider the following bipartite graph with vertex sets as $A$ and $B$. We draw an edge directed from $a$ and $b$ if and only if $\exists \ i\ge 1$ such that $x_i=a$ and $x_{i+1}=b$. Clearly, there cannot be an edge between two elements of $A$ or two elements of $B$. Also, note that there is exactly one cycle in this directed bipartite graph as the sequence becomes eventually periodic. Since the graph is bipartite, the length of the cycle must be even. So, the fundamental period of the sequence, which is just 1 less than the cycle length, will be odd. waow

$(i)$ is trivial by noting that $x_n$ is bounded. Let $d$ denote the maximal value that is at most $L$ that appears in the sequence. WLOG $x_1=d$. Note the bound on $L$ ensures that all elements of the sequence are positive. Note that if we have $x_j\leq L,x_{j+1}>L$, then $x_j > \frac{\lfloor \alpha x_j\rfloor }{\alpha}> \frac{\alpha x_j - 1}{\alpha}>x_j - 1$ hence $x_{j+2}=\lfloor\frac{\lfloor \alpha x_j\rfloor }{\alpha}\rfloor = x_j-1$. Then, there must exist a minimal index $m$ with $x_3=d-1, x_5=d-2, \dots x_{2m+1}=d-m$ and $x_{2m+2}\leq L$. In this case, $d=x_1 \geq x_{2m+2} \geq x_{2m+1}$ implying that there is an index $1 \leq i \leq m$ s.t. $x_{2i+1}=x_{2m+2}$. Check that $x_{2i+1}>x_{2i+3}> \dots >x_{2m+1}$ and $x_{2m+2}<x_{2m}< \dots <x_{2i+2}$ implying the value $x_{2i+1}$ does not appear again between these 2 occurrences, thus the sequence has fundamental period $(2m+2)-(2i+1)$. Observe $x_{2m}=\lfloor (d-m+1) \alpha \rfloor > L, x_{2m+2} = \lfloor (d-m) \alpha \rfloor \leq L$ implies $d-m+1=\lceil \frac{L}{\alpha} \rceil$ and $x_{2i+1}=d-i=x_{2m+2}=\lfloor (\lceil \frac{L}{\alpha} \rceil - 1 ) \alpha \rfloor$ implying $m-i=(d-i)-(d-m)$ is only dependent on $\alpha$ and $L$, thus so is the fundamental period (which is clearly odd).