AoPSWiki
Want to learn how to tackle those tough AMC/AIME/Olympiad counting and probability problems? Check out Art of Problem Solving's Intermediate Counting & Probability by David Patrick.

2006 IMO Shortlist Problems/N2

From AoPSWiki

Problem

(Canada) For x \in (0,1) let y \in (0,1) be the number whose \displaystyle nth 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 nth 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

Retrieved from "http://www.artofproblemsolving.com/Wiki/index.php/2006_IMO_Shortlist_Problems/N2"
Want to learn how to tackle those tough AMC/AIME/Olympiad counting and probability problems? Check out Art of Problem Solving's Intermediate Counting & Probability by David Patrick.
© Copyright 2008 AoPS Incorporated. All Rights Reserved. • Foundation • Privacy • Contact Us