Maths Olympiad Prep

Library / /1 of 2

Algebra Difficulty 8.7 Shortlist Prove it Taiwan

A sequence of integers a0,a1,a2,a_0, a_1, a_2, \dots is called kawaii, if a0=0a_0 = 0, a1=1a_1 = 1, and, for any positive integer nn, we have
(an+13an+2an1)(an+14an+3an1)=0. (a_{n+1} - 3a_n + 2a_{n-1})(a_{n+1} - 4a_n + 3a_{n-1}) = 0.
An integer is called kawaii if it belongs to a kawaii sequence.
Suppose that two consecutive positive integers mm and m+1m+1 are both kawaii (not necessarily belonging to the same kawaii sequence). Prove that 3 divides mm, and that m/3m/3 is kawaii.

Solutions — 2

Solution 1

We start by rewriting the condition in the problem as:
an+1=3an2an1, or an+1=4an3an1. a_{n+1} = 3a_n - 2a_{n-1}, \text{ or } a_{n+1} = 4a_n - 3a_{n-1}.
We have an+1an(mod2)a_{n+1} \equiv a_n \pmod{2} and an+1=an1(mod3)a_{n+1} = a_{n-1} \pmod{3} for all n1n \ge 1.
Now, since a0=0a_0 = 0 and a1=1a_1 = 1, we have that an0,1(mod3)a_n \equiv 0, 1 \pmod{3} for all n0n \ge 0. Since mm and m+1m+1 are kawaii integers, then necessarily m0(mod3)m \equiv 0 \pmod{3}.
We also observe that a2=3a_2 = 3 or a2=4a_2 = 4. Moreover,

1. If a2=3a_2 = 3, then an1(mod2)a_n \equiv 1 \pmod{2} for all n1n \ge 1 since a1=a2=1(mod2)a_1 = a_2 = 1 \pmod{2}.
2. If a2=4a_2 = 4, then an1(mod3)a_n \equiv 1 \pmod{3} for all n1n \ge 1 since a1=a2=1(mod3)a_1 = a_2 = 1 \pmod{3}.

Since m0(mod3)m \equiv 0 \pmod{3}, any kawaii sequence containing mm does not satisfy (2), so it must satisfy (1). Hence, mm is odd and m+1m+1 is even.
Take a kawaii sequence (an)(a_n) containing m+1m+1. Let t2t \ge 2 be such that at=m+1a_t = m+1.
As (an)(a_n) does not satisfy (1), it must satisfy (2). Then an1(mod3)a_n \equiv 1 \pmod{3} for all n1n \ge 1.
We define the sequence an=(an+11)/3a'_n = (a_{n+1} - 1)/3. This is a kawaii sequence: a0=0,a1=1a'_0 = 0, a'_1 = 1 and for all n1n \ge 1,
(an+13an+2an1)(an+14an+3an1)=(an+23an+1+2an)(an+24an+1+3an)/9=0. (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 at1=m/3a'_{t-1} = m/3 which implies that m/3m/3 is kawaii.

Solution 2

We start by proving the following:

Claim 1 We have an0,1(mod3)a_n \equiv 0, 1 \pmod 3 for all n0n \ge 0.

Proof. We have an+1=3an2an11=3(anan1)+an1a_{n+1} = 3a_n - 2a_{n-1} - 1 = 3(a_n - a_{n-1}) + a_{n-1} or an+1=4an3an11=3(anan1)+ana_{n+1} = 4a_n - 3a_{n-1} - 1 = 3(a_n - a_{n-1}) + a_n, so an+1an(mod3)a_{n+1} \equiv a_n \pmod{3}, and since a0=0a_0 = 0 and a1=1a_1 = 1 the result follows. \square

Hence if mm and m+1m+1 are kawaii, then necessarily m0(mod3)m \equiv 0 \pmod 3.

Claim 2 An integer 2\ge 2 is kawaii if and only if it can be written as 1+b2++bn1+b_2+\dots+b_n for some n2n \ge 2 with bi=2ri3sib_i = 2^{r_i}3^{s_i} satisfying ri+si=i1r_i+s_i=i-1 for i=2,,ni=2,\dots,n and bibi+1b_i|b_{i+1} for all i=2,,n1i=2,\dots,n-1.

Proof. For a kawaii sequence (an)(a_n), we can write an+1=3an2an1=an+2(anan1)a_{n+1} = 3a_n - 2a_{n-1} = a_n + 2(a_n - a_{n-1}) or an+1=4an3an1=an+3(anan1)a_{n+1} = 4a_n - 3a_{n-1} = a_n + 3(a_n - a_{n-1}), so an+1an=2(anan1)a_{n+1} - a_n = 2(a_n - a_{n-1}) or 3(anan1)3(a_n - a_{n-1}). Hence, an=1+b2++bna_n = 1 + b_2 + \dots + b_n where b2=2b_2 = 2 or 33 and bi+1=2bib_{i+1} = 2b_i or 3bi3b_i.

Conversely, given a number that can be written in that way, we consider any sequence given by a0=0a_0 = 0, a1=1a_1 = 1 and ai=1+b2++bia_i = 1 + b_2 + \dots + b_i for 2i<n2 \le i < n and aia_i given by the kawaii condition for in+1i \ge n+1. This defines a kawaii sequence containing the given number as ana_n. \square

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

Then m+1=1+b2++bjm+1 = 1+b_2+\dots+b_j for some bib_i's as in Claim 2 with b2=3b_2=3 and bibi+1b_i|b_{i+1}: so with 3bi3|b_i for all i=2,,ji=2,\dots,j. Then m3=1+b1++bj1\frac{m}{3} = 1+b'_1+\dots+b'_{j-1} with bi=bi+13b'_i = \frac{b_{i+1}}{3} as in Claim 2 and m3\frac{m}{3} is a kawaii integer.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement translated into English from zh; metadata (topic, difficulty) added by this project.