For any positive integer $ x$ define $ g(x)$ as greatest odd divisor of $ x,$ and \[ f(x) = \begin{cases} \frac {x}{2} + \frac {x}{g(x)} & \text{if \ \(x\) is even}, \\ 2^{\frac {x + 1}{2}} & \text{if \ \(x\) is odd}. \end{cases} \] Construct the sequence $ x_1 = 1, x_{n + 1} = f(x_n).$ Show that the number 1992 appears in this sequence, determine the least $ n$ such that $ x_n = 1992,$ and determine whether $ n$ is unique.
Problem
Source: IMO Shortlist 1992, Problem 14
Tags: induction, algebra, recurrence relation, Sequence, IMO Shortlist, IMO Longlist
13.08.2008 23:35
27.11.2009 11:30
Any comments on correctness or how I could word it better are welcome.
13.05.2021 15:45
Nice pattern finding problem. The following two claims are the key to the problem: Claim: For all nonnegative integers $n,$ we have that $x_{\frac{n^2+n+2}{2}} = 2^n$. Claim: Call a block the numbers from $x_i$ to $x_k$, including $x_i$ and excluding $x_k,$ such that $x_i$ and $x_k$ are the consecutive powers of two of the sequence which have the form given in the first claim. We claim that between two adjacent blocks, the only thing that happens is the numbers in the previous block get multiplied by $2$, and there is one extra odd number at the end, which is just the next odd number after the previous odd number in the first block. Both of these claims are easily provable by induction by just listing out the terms. From here it is easy to find the index at which 1992 appears, and because 1992 has a unique prime factorization, it is also unique.