The Problem:

A number (in decimal) can be transformed in the following three ways:
 * Append a '4' on the end of the number; for example, 135 --> 1354
 * Append a '0' to the end 
 * If the number is even, divide by two.

Start with the number '4'. Prove that for any natural number n, there is a
sequence of the above operations to get to n.

---------------------------------------------------------------------
Solution:

The easiest way to build up a sequence from 4 to n is to work
backwards and try to get from n to 4 using the inverse operations (dropping the
last digit if the last digit is 0 or 4, and multiplication by 2).

Here's an algorithm to get from n to 4:

1. If the current number is 4, stop. Otherwise, go to step 2.

2. If the last digit is 0 or 4, then drop the last digit; otherwise, 
   double the number.
   Go to step 1.

For example, starting with the number 13, we get 13 26 52 104 10 1 2 4.
This algorithm always works, but it's not clear that it actually stops after a
finite number of steps.   The rest of this solution is devoted to showing this.

It's quick to verify this procedure works for n <= 4. For n > 4, it suffices to
show that if we start at n, then at some step the algorithm produces a number
less than n.  (Continuing the algorithm from here produces a yet smaller
number, and so on, until eventually we must reach 4 or smaller.)

Keeping track of just the last digit as we follow the algorithm, we get:

n ends in 0:  divide by 10.                                  n -->  0.1 n
n ends in 1:  1 --> 2 --> 4 --> drop last digit.             n -->  < 0.4 n
n ends in 2:  2 --> 4 --> drop last digit.                   n -->  < 0.2 n
n ends in 3:  3 --> 6 --> 2 --> 4 --> drop last digit.       n -->  < 0.8 n
n ends in 4:  drop last digit.                               n -->  < 0.1 n
n ends in 5:  5 --> 0 --> divide by 10.                      n -->  0.2 n
n ends in 6:  6 --> 2 --> 4 --> drop last digit.             n -->  < 0.4 n
n ends in 7:  7 --> 4 --> drop last digit.                   n -->  < 0.2 n
n ends in 8:  8 --> 6 --> 2 --> 4 --> drop last digit.       n -->  < 0.8 n
n ends in 9:  9 --> 8 --> 6 --> 2 --> 4 --> drop last digit. n -->  < 1.6 n

If n does not end in 9, then n goes to a number less than 0.8 n, which is
smaller than n, and we're done. Now suppose that n ends in 9.

Repeating the above analysis for each of the possiblilities for n ending in 09,
19, 29, ..., 99 shows that after 4 doublings, we have 16n ends in 04, 24, 44,
64, or 84.  Lopping off the last digit means we get an even number.

This new number is less than 1.6n (by our original argument).  If 
it ends in 0, 2, 4, or 6, then we double at most twice before we can lop off
the 0 or 4, and we get a number at most (0.4)(1.6n) = .64n < n.

Finally, if the number ends in 8, then we require 3 doublings before we can
drop the last digit; following this process, we get an even number 0.8 times as
large as before. Since we started with something less than 1.6n, multiplying
by 0.8 still gives a number less than 1.28n, which is still is too large.
However, the resulting number is even, and we can repeat this process; each 
time we get a number at worst 0.8 times as big as before.
This needs be done at most 3 times before we finally get a number smaller than
the original n (since 0.8 * 0.8 * 0.8 * 1.6 n = 0.8192 n).

So in every case, the above procedure eventually leads to a smaller number,
and so the procedure must eventually stop.

---------------------------------------------------------------------------

Correct solutions: 

Aaron Dilley (undergraduate); Dustin Moody, Adam Estrup,
(graduate); Gary Raymond (faculty); Rich Bauer (alum)

Dustin Moody wins the prize!