AoPSWiki

Want to learn how to tackle those tough AMC/AIME/Olympiad algebra problems? Check out Art of Problem Solving's Intermediate Algebra by Richard Rusczyk and Mathew Crawford. Over 1600 problems!

Personal tools

Log in

Search

Toolbox

2006 IMO Shortlist Problems/N2

From AoPSWiki

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

Retrieved from "http://www.artofproblemsolving.com/Wiki/index.php/2006_IMO_Shortlist_Problems/N2"

Category: Olympiad Number Theory Problems

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

© Copyright 2008 AoPS Incorporated. All Rights Reserved. • Foundation • Privacy • Contact Us