It is currently Thu Mar 21, 2019 9:08 am


All times are UTC [ DST ]




Post new topic Reply to topic  [ 5 posts ] 
Author Message
PostPosted: Tue Nov 10, 2015 3:59 pm 
Administrator
Administrator
User avatar

Joined: Sat Nov 07, 2015 6:12 pm
Posts: 841
Location: Larisa
Find the five last digits of the number:

$$\mathscr{N}=\underbrace{9^{9^{9^{\cdot^{\cdot^{\cdot^{\cdot^{9}}}}} }}}_{1001 \;\; \rm {nines}}$$

_________________
Imagination is much more important than knowledge.
Image


Top
Offline Profile  
Reply with quote  

PostPosted: Tue Nov 10, 2015 5:53 pm 

Joined: Mon Nov 09, 2015 11:52 am
Posts: 77
Location: Limassol/Pyla Cyprus
I wonder which evil mind has concocted this exercise. Having solved it though, I will probably behave like Mike in this comic.

Tolis, please confirm if the answer is $45289$.

Edit: Added font colour on the hyperlink.


Last edited by Demetres on Tue Nov 10, 2015 6:35 pm, edited 1 time in total.

Top
Offline Profile  
Reply with quote  

PostPosted: Tue Nov 10, 2015 5:58 pm 
Administrator
Administrator
User avatar

Joined: Sat Nov 07, 2015 6:12 pm
Posts: 841
Location: Larisa
Demetres wrote:
Tolis, please confirm if the answer is $45289$.


Affirmative.

As for the evil mind , no idea.

_________________
Imagination is much more important than knowledge.
Image


Top
Offline Profile  
Reply with quote  

PostPosted: Wed Nov 11, 2015 2:21 pm 

Joined: Mon Nov 09, 2015 11:52 am
Posts: 77
Location: Limassol/Pyla Cyprus
Ok then. Here we go.

Let me write $a_n$ for the tower of $n$ nines. In fact I will show that $a_n \equiv 45289 \bmod 100000$ for every $n \geqslant 5$.

Firstly, it is immediate that $a_n \equiv 9 \bmod 10$ for every $n \geqslant 1$. (Because $a_{n-1}$ is always odd.)

Modulo $100$ we have

\[ a_n \equiv (10-1)^{a_{n-1}} \equiv 10a_{n-1} - 1 \equiv 90-1 \equiv 89 \bmod 100\]

for every $n \geqslant 2$.

In the second congruence I have used the binomial expansion and omitted all terms which are multiples of $100$. We follow the same procedure with higher powers of $10$, but greater care is needed.

Modulo $1000$ we have

\[ a_n \equiv -100\frac{a_{n-1}(a_{n-1}-1)}{2} + 10a_{n-1} - 1.\]

Now, $a_{n-1} \equiv 9 \bmod 10$. Also, $(a_{n-1}-1) \equiv 88 \bmod 100$ so $(a_{n-1}-1)/2 \equiv 4 \bmod 10$. In more detail: $a_{n-1} = 100k+89$ for some integer $k$. Then $(a_{n-1}-1)/2 = 50k+44 \equiv 4 \bmod 10$.

This gives that $a_{n-1}(a_{n-1}-1)/2 \equiv 6 \bmod 10$. So overall we get

\[ a_n \equiv -600 + 890 - 1 \equiv 289 \bmod 1000\]

for every $n \geqslant 3$.

Modulo $10000$ we have

\[ a_n \equiv 1000\binom{a_{n-1}}{3} - 100\binom{a_{n-1}}{2} + 10a_{n-1} - 1\]

To compute $\dbinom{a_{n-1}}{3} \bmod 10$ we see that

\begin{align*}
\binom{a_{n-1}}{3} &= \frac{(1000k+289)(1000k+288)(1000k+287)}{6}\\
& = \frac{(1000k+289)(500k+144)(1000k+287)}{3} \\
&\equiv 7 \cdot 9 \cdot 4 \cdot 7\\
& \equiv 4 \bmod 4
\end{align*}
Here, the first $7$ appears because $7$ is the inverse of $3$ module $10$.

We also have to compute $\dbinom{a_{n-1}}{2} \bmod 100$ which with the same process gives $89 \cdot 44 \equiv 16 \bmod 100$. Overall we get

\[ a_n \equiv 4000 - 1600 + 2890 - 1 \equiv 5289 \bmod 1000\]

for every $n \geqslant 4$.

We have yet one more round to go:

\[ a_n \equiv -10000\binom{a_{n-1}}{4} + 1000\binom{a_{n-1}}{3} - 100\binom{a_{n-1}}{2} + 10a_{n-1} - 1\]

It is left as an exercise for the reader :evil: to check that $\dbinom{a_{n-1}}{4} \equiv 6 \bmod 10, \dbinom{a_{n-1}}{3} \equiv 64 \bmod 100$ and $\dbinom{a_{n-1}}{2} \equiv 116 \bmod 1000$. Putting all these together gives that the last 5 digits of $a_n$ are $45289$ for every $n \geqslant 5$.


Top
Offline Profile  
Reply with quote  

PostPosted: Wed Nov 11, 2015 2:40 pm 

Joined: Mon Nov 09, 2015 11:52 am
Posts: 77
Location: Limassol/Pyla Cyprus
I believe I now understand why the "evil" creator of this exercise went all the way up to 5 digits and he/she was not content with the last four digits.

In the solution, when we compute $\binom{m}{2} \bmod 10$ it is absolutely important to use the last two digits of $m$ and not just the last one. For example, if $m = 2$, then $\binom{m}{2} = 1 \equiv 1 \bmod 10$, while if $m = 12$, then $\binom{m}{2} = 66 \equiv 6 \bmod 10$.

So somebody might possibly get lucky and using the wrong method derive the right answer. When does this happen? Some fiddling around shows that if the digit he have omitted is even then we get the correct answer with the wrong procedure, while if the digit is odd then we do not.

The first instance in which we get an additional odd digit is when we have to use $5289$ rather than just $289$. To use $5289$, we need to ask for $5$ digits.


Top
Offline Profile  
Reply with quote  

Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 5 posts ] 

All times are UTC [ DST ]


Mathimatikoi Online

Users browsing this forum: No registered users and 0 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
Powered by phpBB® Forum Software © phpBB Group Color scheme created with Colorize It.
Theme created StylerBB.net