Any solutions to this fine, fine problem?

Does anybody have the official solutions or an own solution???

Can anyone prove that an integer is good(i.e satisfies the given conditions) if and only if it is of the form $k(2k+1)$ where $k$ is a natural number?

**** Incorrect solution due to incorrect reading of problem statement (see my post after the next) *** Note that the recursive definition of $b_n$ depends only on $b_n$ itself, and the recursive definition of $c_n$ depends only on $b_n$ and $c_n$. One easily gets per induction that $b_{2n-1}=b_{2n}=2^{2+n}$ and $c_{2n}=c_{2n+1}=2^{3+n}-7$. With this it follows again per indicution (because all $b_n,c_n \ge 0$) that, if $a_{n_0} < 0$ then $a_n < 0$ for all $n\ge n_0$. However, to solve this problem, one needs only to calculate the $b_n,c_n$ values for $n\le 10$ recursively and use them for the $a_n$ recurrence (sorry, I have no idea how to make a table, any help would be appreciated): $n$ $b_n$ $c_n$ 0 4 1 1 8 1 2 8 9 3 16 9 4 16 25 5 32 25 6 32 57 7 64 57 8 64 121 9 128 121 10 128 249 $n$ $a_n$ 0 $k$ 1 $\frac{1}{2}k$ 2 $\frac{1}{2}k-5$ 3 $\frac{1}{4}k-\frac{5}{2}$ 4 $\frac{1}{4}k-\frac{39}{2}$ 5 $\frac{1}{8}k-\frac{39}{4}$ 6 $\frac{1}{8}k-\frac{203}{4}$ 7 $\frac{1}{16}k-\frac{203}{8}$ 8 $\frac{1}{16}k-\frac{915}{8}$ 9 $\frac{1}{32}k-\frac{915}{16}$ 10 $\frac{1}{32}k-\frac{3875}{16}$ We see: For $k < 1995$, $a_{10} < 0$ and hence by the above observation $a_n < 0$ for all $n\ge 10$. So $a_n=0$ is only possible for $n<10$ and solving $a_n=0$ for $0 \le n \le 9$ gives as possible solutions $k=10, 78, 406, 1830$ ($k=0$ not possible as $k$ is positive according to problem statement). So there are 4 such positive integers k as sought in the problem statement. @hajimbrak: All the solutions are of the stated form: $10=2*5$, $78=6*13$, $406=14*29$ and $1830=30*61$. Note that the smaller factor is each time one bigger than the larger factor if the previous solution. But of course, not all the intergers of the form $m*(2m+1)$ are solutions. I guess it is straightforward to find all the solutions. You have to guess and then prove by induction the general formula for $a_n$, starting at the above given formulas for $b_n$ and $c_n$.

Here is a proof of the fact that all integers of the form $k(2k+1)$ are good. Let $2^a$ be the largest power of $2$ less than $k$.Hence $k=2^a+b$ where $0\leq b<2^a$.Now we prove by induction that for some $n$, $a_{n}=2^{a+1}+4b+1,b_{n}=2^{a+2},c_{n}=4b+1$ which also implies that $a_{n+1}=0$. We can easily check the statement for the few base cases.Now we assume that the statement is true for all $k$ less than $2^l$. Let $k=2^l+m$,where $2^l$ is the largest power of two less than $k$.Hence $a_{0}=k(2k+1)=2^{2l+1}+(4m+1)2^{l}+m(2m+1)$ Now $m$ is less than $2^l$ hence the statement is true for it.Hence after sometime the term $m(2m+1)$ will vanish and for some $n$ we will get $a_{n}=2^{r+l+1}+(4m+1)2^{r},b_{n}=2^{l-r+2},c_{n}=4m+1$ which implies that $a_{n+r+1}=0$.

@Ingix:I do not think your solution is correct because I have given a proof of the fact that all numbers of the form $k(2k+1)$ are good,hence their are more than four solutions.You can check that $21,36,3,55$etc all are solutions.In fact the correct answer is $31$,you can get a solution in the IMO Compendium.

Sorry, I screwed up. I read "If $a_n$ is even/odd" as "if $n$ is even/odd", thus leading to my incorrect solution above.

For the other part, we refer to the proof given in the IMO compendium where it is proved that if $a_n=0$ then $b_{n-1},c_{n-1}$ uniquely fixes $a_0$.Now let $b_{n-1}=2^m$ and $c_{n-1}=4k+1$.We choose $l=2^{m-2}+k$ and $a_0=l(2l+1)$.This satisfies the conditions according to the proof of the other part and it is unique.Hence it is proved that an integer is good if and only if it is of the form $a(2a+1)$.

1. It's easy to verify that $a_n.b_n + \dfrac{c_n^2}{2}$ is an invariant. Also, $c_n \equiv 1 (mod 4)$ $\forall n \in N$. Therefore, if $a_n = 0$ for some $n$, then let $c_n = 4u + 1 \Rightarrow 4a_0 + \dfrac{1}{2} = \dfrac{(4u+1)^2}{2} \Rightarrow a_0 = u(2u+1)$. 2. Now we prove that all $a_0$ of the form $u(2u+1)$ will give $a_n = 0$ for some $n$. Let $u = 2^{x_1} + 2^{x_2} + ... + 2^{x_k} (x_1 < x_2 < ... < x_k)$ For $k = 1$, i.e. $u = 2^{x_1}$, it's easy to show that $a_{x_1+1}=0$. Consider $k \ge 2$. Denote $v_i = \sum_{j=i+1}^{k} 2^{x_j-x_i} +1$ $\forall 1 \le i \le k-1$ and $v_k = 1$ By induction, $a_{x_i+i} = 2^{x_{i+1}-x_i}.v_{i+1}.(2^{x_{i+1}+1}.v_{i+1}+ \sum_{j=1}^{i} 2^{x_{j+2}} +1)$, $b_{x_i+i} = 2^{x_i+2}$, $c_{x_i+i} = \sum_{j=1}^{i} 2^{x_{j+2}} +1$ $\forall 1 \le i \le k-1$ $\Rightarrow a_{x_{k-1}+k-1} = 2^{x_k-x_{k-1}}.v_k.(2^{x_k+1}.v_k+ \sum_{j=1}^{k-1} 2^{x_{j+2}} +1) = 2^{x_k-x_{k-1}}.(2^{x_k+1}+ \sum_{j=1}^{k-1} 2^{x_{j+2}} +1)$, $b_{x_{k-1}+k-1} = 2^{x_{k-1}+2}$, $c_{x_{k-1}+k-1} = \sum_{j=1}^{k-1} 2^{x_{j+2}} +1$ $\Rightarrow a_{x_k+k-1} = 2^{x_k+1}+ \sum_{j=1}^{k-1} 2^{x_{j+2}} +1$, $b_{x_k+k-1} = 2^{x_k+2}$, $c_{x_k+k-1} = \sum_{j=1}^{k-1} 2^{x_{j+2}} +1$ $\Rightarrow a_{x_k+k} = 0$. $\blacksquare$