IMO 3J, Mock Exam 2

We start by rewriting the condition in the problem as:
$$a_{n+1} = 3a_n - 2a_{n-1}, \text{ or } a_{n+1} = 4a_n - 3a_{n-1}.$$
We have $a_{n+1} \equiv a_n \pmod{2}$ and $a_{n+1} = a_{n-1} \pmod{3}$ for all $n \ge 1$.
Now, since $a_0 = 0$ and $a_1 = 1$, we have that $a_n \equiv 0, 1 \pmod{3}$ for all $n \ge 0$. Since $m$ and $m+1$ are kawaii integers, then necessarily $m \equiv 0 \pmod{3}$.
We also observe that $a_2 = 3$ or $a_2 = 4$. Moreover,

1. If $a_2 = 3$, then $a_n \equiv 1 \pmod{2}$ for all $n \ge 1$ since $a_1 = a_2 = 1 \pmod{2}$.
2. If $a_2 = 4$, then $a_n \equiv 1 \pmod{3}$ for all $n \ge 1$ since $a_1 = a_2 = 1 \pmod{3}$.

Since $m \equiv 0 \pmod{3}$, any kawaii sequence containing $m$ does not satisfy (2), so it must satisfy (1). Hence, $m$ is odd and $m+1$ is even.
Take a kawaii sequence $(a_n)$ containing $m+1$. Let $t \ge 2$ be such that $a_t = m+1$.
As $(a_n)$ does not satisfy (1), it must satisfy (2). Then $a_n \equiv 1 \pmod{3}$ for all $n \ge 1$.
We define the sequence $a'_n = (a_{n+1} - 1)/3$. This is a kawaii sequence: $a'_0 = 0, a'_1 = 1$ and for all $n \ge 1$,
$$(a'_{n+1}-3a'_{n}+2a'_{n-1})(a'_{n+1}-4a'_{n}+3a'_{n-1}) = (a_{n+2}-3a_{n+1}+2a_{n})(a_{n+2}-4a_{n+1}+3a_{n})/9 = 0.$$
Finally, we notice that the term $a'_{t-1} = m/3$ which implies that $m/3$ is kawaii.

We start by proving the following:

Claim 1 We have $a_n \equiv 0, 1 \pmod 3$ for all $n \ge 0$.

Proof. We have $a_{n+1} = 3a_n - 2a_{n-1} - 1 = 3(a_n - a_{n-1}) + a_{n-1}$ or $a_{n+1} = 4a_n - 3a_{n-1} - 1 = 3(a_n - a_{n-1}) + a_n$, so $a_{n+1} \equiv a_n \pmod{3}$, and since $a_0 = 0$ and $a_1 = 1$ the result follows. $\square$

Hence if $m$ and $m+1$ are kawaii, then necessarily $m \equiv 0 \pmod 3$.

Claim 2 An integer $\ge 2$ is kawaii if and only if it can be written as $1+b_2+\dots+b_n$ for some $n \ge 2$ with $b_i = 2^{r_i}3^{s_i}$ satisfying $r_i+s_i=i-1$ for $i=2,\dots,n$ and $b_i|b_{i+1}$ for all $i=2,\dots,n-1$.

Proof. For a kawaii sequence $(a_n)$, we can write $a_{n+1} = 3a_n - 2a_{n-1} = a_n + 2(a_n - a_{n-1})$ or $a_{n+1} = 4a_n - 3a_{n-1} = a_n + 3(a_n - a_{n-1})$, so $a_{n+1} - a_n = 2(a_n - a_{n-1})$ or $3(a_n - a_{n-1})$. Hence, $a_n = 1 + b_2 + \dots + b_n$ where $b_2 = 2$ or $3$ and $b_{i+1} = 2b_i$ or $3b_i$.

Conversely, given a number that can be written in that way, we consider any sequence given by $a_0 = 0$, $a_1 = 1$ and $a_i = 1 + b_2 + \dots + b_i$ for $2 \le i < n$ and $a_i$ given by the kawaii condition for $i \ge n+1$. This defines a kawaii sequence containing the given number as $a_n$. $\square$

Let us suppose that $m$ and $m+1$ are kawaii, then they belong to some kawaii sequences and we can write them as in Claim 2 as $m = 1+2+\dots+2^\ell+2^\ell \cdot 3 \cdot A$ and $m+1 = 1+2+\dots+2^{\ell'}+2^{\ell'} \cdot 3 \cdot A'$ where $\ell$ is odd and $\ell'$ is even because of modulo $3$ reasons. Since $m+1 \equiv m \pmod{2^{\min(\ell,\ell')}}$, we have $\min(\ell, \ell') = 0$, so $\ell' = 0$.

Then $m+1 = 1+b_2+\dots+b_j$ for some $b_i$'s as in Claim 2 with $b_2=3$ and $b_i|b_{i+1}$: so with $3|b_i$ for all $i=2,\dots,j$. Then $\frac{m}{3} = 1+b'_1+\dots+b'_{j-1}$ with $b'_i = \frac{b_{i+1}}{3}$ as in Claim 2 and $\frac{m}{3}$ is a kawaii integer.