How do I find the last two digits of the following expression?
$$\Bigl\lfloor \frac{10^{2001}}{10^{29}-2} \Bigr\rfloor$$
A full formula or general solution would also be useful!
This is from a Training Set known from the MTG in the Philippines. We are currently having lessons on Floor and Ceiling functions, and this was given as "an exercise for the reader." The first thing I tried was to express $10^{2001}$ into $(10^{29})^{69}$ and set that to x, but from there I'm stuck.
Using the Binomial Theorem, $$ ( 1 0 ^ { 2 9 } - 2 ) ^ { - 1 } = \sum _ { k = 0 } ^ \infty { - 1 \choose k } ( - 2 ) ^ k ( 1 0 ^ { 2 9 } ) ^ { - 1 - k } = \sum _ { k = 0 } ^ \infty 2 ^ k 1 0 ^ { - 2 9 ( k + 1 ) } \text . $$ So the decimal expansion of this consists of blocks of length $ 2 9 $ that begin with $ 0 $s and end with powers of $ 2 $ (until the powers of $ 2 $ come to have $ 2 9 $ digits or more themselves).
We want to go out to $ 2 0 0 1 $ digits. Since $ 2 0 0 1 / 2 9 = 6 9 $ exactly, that means $ 6 9 $ blocks, which run from $ 2 ^ 0 $ to $ 2 ^ { 6 8 } $ inclusive. Since $ 2 ^ { 6 8 } $ is … well, using a calculator to work that out exactly may be cheating, but it's less than $ 2 ^ { 7 0 } = ( 2 ^ { 1 0 } ) ^ 7 \approx ( 1 0 ^ 3 ) ^ 7 = 1 0 ^ { 2 1 } $, so we're still long before the blocks start interfering with each other. So the answer will be the last two digits of $ 2 ^ { 6 8 } $.
Multiplying out some powers of $ 2 $, a convenient place to stop is $ 2 ^ 8 = 2 5 6 $. When we get here, we only need the last two digits, $ 5 6 $. So $ 2 ^ { 1 6 } = 2 ^ 8 \cdot 2 ^ 8 $ will end in the same last two digits as $ 5 6 \cdot 5 6 = 3 1 3 6 $, which are $ 3 6 $. Then $ 2 ^ { 3 2 } $ will end in the same last two digits as $ 3 6 \cdot 3 6 = 1 2 9 6 $. Then $ 2 ^ { 6 4 } $ will end in the same last two digits as $ 9 6 \cdot 9 6 = 9 2 1 6 $. Finally, $ 2 ^ { 6 8 } = 2 ^ { 6 4 } \cdot 2 ^ 4 $ ends in the same last two digits as $ 1 6 \cdot 1 6 $ (it's just a coincidence now that these are the same), which is $ 2 5 6 $. (The strategy for this is based on the binary digits of the exponent $ 6 8 $; you'd use the same strategy even if you were looking at powers of something other than $ 2 $.)
So the answer is $ 5 6 $.
By the way, you can see the entire number on WolframAlpha if you keep asking it to show more digits, so you can check for yourself (not only the last two digits, but also how it consists of blocks of $ 0 $s ending with powers of $ 2 $).