**Source:**Problems on Algorithms (Ian Parberry and William Gasarch)

**Problem:**

Let

*f*be a function which takes a number

*x*(number with say

*n*digits, digit

*i*represented by

*d_i*) as input and outputs sum of the

*2001*powers of the digits. So,

*f(327)=3^2001 + 2^2001 + 7^2001*. Show that for any

*x*, the set {

*f(x), f(f(x)), f(f(f(x))),..*} is finite.

Update (31 January 2011)

**Solution:**Posted by Sudeep Kamath (UC Berkeley PhD Student & EE IITB Alumnus) in comments!

If x has n digits, then

ReplyDeletef(x)\leq n*9^2001 \leq 10^{n-1} \leq x

where second inequality holds for all sufficiently large n.

Thus, there exists an integer N such that f(x)\leq x for all x>N.

This tells us that for any iterate i, f^{(i)}(x) is upper bounded by max{sup_{y\leq N} f(y), x} which is a finite number that depends on x.

:) Nice solution. I so wish blogger had tex support :(

ReplyDeleteThanks.