Posted on: March 30th, 2013 by
4

You know that $9^{100000000000}$ is a 95424250944 digit number. Consider the set $\{9^1,9^2,9^3,\dots 9^{100000000000}\}$. How many of these numbers start with a 9? (Example: 91 starts with a 9, but 729 does not start with a 9). (Obviously you are not allowed to use a computer. That's why the number is bloated up by so much that even a computer can't feasibly solve it).

Source: One of the practice problems from the Indian National Mathematics Olympiad training programme.

I have a vague solution which you could refine for me:
I reduced the problem to solving for positive integers n such that the fractional part of nlog9 is at least log9.
Now in the additive group [0,1) with addition modulo 1 (i.e.floor of addition), consider the subgroup generated by log9. We would like to show that the elements of this subgroup which are at least log9 is a 1-log9 fraction.
Here is where I go into the discrete case: Let 0<c<1 be such that c=a/b in lowest form. Then in the group modulo b, c can be identified with a, and as gcd(a,b)=1, the subgroup generated by a is the whole group modulo b. In which case the elements "at least a" in the group are a 1-a/b or a 1-c fraction. We can take limits in the case of c being irrational (can we?)
Thus the number of powers of 9 with 9 as the first digit is 100000000000(1-log9) which is
4575749057.
Is that okay? I'd love to hear a simple way of saying this without resorting to groups(though I guess modulo arithmetic, which is the same thing, can be used without the group-theoretic terminology)

Whoa! A big solution! You are pretty close! The exact answer is 100000000000-95424250944+1=4575749057. The simple solution I have:
...
...
...
...
...
Suppose $9^n$ starts with a 9. Then $9^{n-1}={9^n\over 9}$ has the same number of digits as $9^n$. Otherwise, $9^{n-1}$ has 1 digit lesser. Since the number of digits has to reduce from 95424250944 to 1, you have the answer.

I like your solution though because it helps us estimate the number of elements that start with an 8 for example. Well, I am not sure if the answer will be exact. So the exact answer for this question is $100000000000-\lfloor 100000000000\log 9\rfloor$