IMO 2006 Shortlisted Problems

Let $\phi =(1+\sqrt{5})/2$ and $\psi =(1-\sqrt{5})/2$ be the roots of the quadratic equation $t^2-t-1=0$. So $\phi \psi =-1$, $\phi +\psi =1$ and $1+\psi ={\psi }^2$. An easy induction shows that the general term $c_n$ of the given sequence satisfies $$c_n=\frac{{\phi }^{n-1}-{\psi }^{n-1}}{\phi -\psi }\text{ for }n\ge 0$$ Suppose that the numbers $\alpha$ and $\beta$ have the stated property, for appropriately chosen $m$ and $M$. Since $\left(c_n,c_{n-1}\right)\in S$ for each $n$, the expression $\alpha c_n+\beta c_{n-1}=\frac{\alpha }{\sqrt{5}}\left({\phi }^{n-1}-{\psi }^{n-1}\right)+\frac{\beta }{\sqrt{5}}\left({\phi }^{n-2}-{\psi }^{n-2}\right)=\frac{1}{\sqrt{5}}\left[(\alpha \phi +\beta ){\phi }^{n-2}-(\alpha \psi +\beta ){\psi }^{n-2}\right]$ is bounded as $n$ grows to infinity. Because $\phi >1$ and $-1<\psi <0$, this implies $\alpha \phi +\beta =0$. To satisfy $\alpha \phi +\beta =0$, one can set for instance $\alpha =\psi$, $\beta =1$. We now find the required $m$ and $M$ for this choice of $\alpha$ and $\beta$. Note first that the above displayed equation gives $c_n\psi +c_{n-1}={\psi }^{n-1}$, $n\ge 1$. In the sequel, we denote the pairs in $S$ by $\left(a_J,b_J\right)$, where $J$ is a finite subset of the set $\mathbb{N}$ of positive integers and $a_J={\sum }_{j\in J}{c}_j$, $b_J={\sum }_{j\in J}{c}_{j-1}$. Since $\psi a_J+b_J={\sum }_{j\in J}\left(c_j\psi +c_{j-1}\right)$, we obtain $$\begin{array}{c}\psi a_J+b_J=\sum _{j\in J}{\psi }^{j-1}\text{ for each }\left(a_J,b_J\right)\in S\end{array}\text{\hspace{1em}(1)}$$ On the other hand, in view of $-1<\psi <0$, $$-1=\frac{\psi }{1-{\psi }^2}=\sum _{j=0}^{\infty }{\psi }^{2j+1}<\sum _{j\in J}{\psi }^{j-1}<\sum _{j=0}^{\infty }{\psi }^{2j}=\frac{1}{1-{\psi }^2}=1-\psi =\phi$$ Therefore, according to (1), $$-1<\psi a_J+b_J<\phi \text{ for each }\left(a_J,b_J\right)\in S.$$ Thus $m=-1$ and $M=\phi$ is an appropriate choice. Conversely, we prove that if an ordered pair of nonnegative integers $(x,y)$ satisfies the inequality $-1<\psi x+y<\phi$ then $(x,y)\in S$. Lemma. Let $x,y$ be nonnegative integers such that $-1<\psi x+y<\phi$. Then there exists a subset $J$ of $\mathbb{N}$ such that $$\begin{array}{c}\psi x+y=\sum _{j\in J}{\psi }^{j-1}\end{array}\text{\hspace{1em}(2)}$$ Proof. For $x=y=0$ it suffices to choose the empty subset of $\mathbb{N}$ as $J$, so let at least one of $x,y$ be nonzero. There exist representations of $\psi x+y$ of the form $$\psi x+y={\psi }^{i_1}+\cdots +{\psi }^{i_k}$$ where $i_1\le \cdots \le i_k$ is a sequence of nonnegative integers, not necessarily distinct. For instance, we can take $x$ summands ${\psi }^1=\psi$ and $y$ summands ${\psi }^0=1$. Consider all such representations of minimum length $k$ and focus on the ones for which $i_1$ has the minimum possible value $j_1$. Among them, consider the representations where $i_2$ has the minimum possible value $j_2$. Upon choosing $j_3,\dots ,j_k$ analogously, we obtain a sequence $j_1\le \cdots \le j_k$ which clearly satisfies $\psi x+y={\sum }_{r=1}^k{\psi }^{j_r}$. To prove the lemma, it suffices to show that $j_1,\dots ,j_k$ are pairwise distinct. Suppose on the contrary that $j_r=j_{r+1}$ for some $r=1,\dots ,k-1$. Let us consider the case $j_r\ge 2$ first. Observing that $2{\psi }^2=1+{\psi }^3$, we replace $j_r$ and $j_{r+1}$ by $j_r-2$ and $j_r+1$, respectively. Since $${\psi }^{j_r}+{\psi }^{j_{r+1}}=2{\psi }^{j_r}={\psi }^{j_r-2}\left(1+{\psi }^3\right)={\psi }^{j_r-2}+{\psi }^{j_r+1},$$ the new sequence also represents $\psi x+y$ as needed, and the value of $i_r$ in it contradicts the minimum choice of $j_r$. Let $j_r=j_{r+1}=0$. Then the sum $\psi x+y={\sum }_{r=1}^k{\psi }^{j_r}$ contains at least two summands equal to ${\psi }^0=1$. On the other hand $j_s\ne 1$ for all $s$, because the equality $1+\psi ={\psi }^2$ implies that a representation of minimum length cannot contain consecutive $i_r$ 's. It follows that $$\psi x+y=\sum _{r=1}^k{\psi }^{j_r}>2+{\psi }^3+{\psi }^5+{\psi }^7+\cdots =2-{\psi }^2=\phi ,$$ contradicting the condition of the lemma. Let $j_r=j_{r+1}=1$; then ${\sum }_{r=1}^k{\psi }^{j_r}$ contains at least two summands equal to ${\psi }^1=\psi$. Like in the case $j_r=j_{r+1}=0$, we also infer that $j_s\ne 0$ and $j_s\ne 2$ for all $s$. Therefore $$\psi x+y=\sum _{r=1}^k{\psi }^{j_r}<2\psi +{\psi }^4+{\psi }^6+{\psi }^8+\cdots =2\psi -{\psi }^3=-1,$$ which is a contradiction again. The conclusion follows. $\square$