2006 IMO Shortlist Problems/N2

Problem

(Canada) For $x \in (0,1)$ let $y \in (0,1)$ be the number whose $\displaystyle n$th digit after the decimal point is the $\displaystyle (2^n)$th digit after the decimal point of $\displaystyle x$. Show that if $\displaystyle x$ is rational then so is $\displaystyle y$.

Solution

For any real ${ a \in (0,1) }$ and any natural number $\displaystyle n$, let $\displaystyle f_a(n)$ the $\displaystyle n$th digit after the decimal point of $\displaystyle a$. We note that $\displaystyle a$ is rational if and only if $\displaystyle f_a(n)$ is periodic for sufficiently large $\displaystyle n$, i.e., if $\displaystyle f_a(n)$ is determined by the residue of $\displaystyle n$ mod $\displaystyle m$, for some integer $\displaystyle m$.

Suppose $\displaystyle x$ is rational, and let $\displaystyle m$ be an integer such that for sufficiently large $\displaystyle n$, $\displaystyle f_x(n)$ is determined by the residue of $\displaystyle n$ mod $\displaystyle m$. Let $\displaystyle m = 2^r \cdot k$, for some odd integer $\displaystyle k$ and some nonnegative integer $\displaystyle r$. We note that the residue of $\displaystyle n$ mod $\displaystyle m$ is uniquely determined by the residues of $\displaystyle n$ mod $\displaystyle 2^r$ and mod $\displaystyle k$. Then for sufficiently large $\displaystyle n$,

$2^n \equiv 2^{n + \phi(k)} \equiv 0 \pmod{2^r}$,

and

$2^n \equiv 2^n \cdot 2^{\phi(k)} \equiv 2^{n+\phi(m)} \pmod{k}$,

so

$2^n \equiv 2^{n+\phi(k)} \pmod{m}$,

and

$\displaystyle f_y(n) = f_x(2^n) = f_x [2^{n+\phi(m)}] = f_y[n+\phi(m)]$.

Hence $\displaystyle y$ is rational.


Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.

Resources