Welcome to our community

Be a part of something great, join today!

Problem of the week #76 - September 9th, 2013

Status
Not open for further replies.
  • Thread starter
  • Admin
  • #1

Jameson

Administrator
Staff member
Jan 26, 2012
4,041
What is the last digit of \(\displaystyle \frac{2^{222}+2^{333}+2^{444}}{2}\)?

(This problem is aimed at 9th and 10th graders. If you find it easy, I suggest giving a shot at POTW #70 using modular arithmetic)
--------------------
Remember to read the POTW submission guidelines to find out how to submit your answers!
 
  • Thread starter
  • Admin
  • #2

Jameson

Administrator
Staff member
Jan 26, 2012
4,041
Congratulations to the following members for their correct solutions:

1) MarkFL
2) eddybob123

Solution (from MarkFL):
If we look at the first few powers of 2:

\(\displaystyle 2^1=2\)

\(\displaystyle 2^2=4\)

\(\displaystyle 2^3=8\)

\(\displaystyle 2^4=16\)

We see this cycle of last digits, with a period of 4, will repeat. If we observe that:

\(\displaystyle 111=4\cdot28-1\)

Then we might hypothesize that:

\(\displaystyle 2^{4n-1}=10m_n+8\) where \(\displaystyle m_n\in\mathbb{N}\)

Multiplying this induction hypothesis by:

\(\displaystyle 2^4=16\)

we obtain:

\(\displaystyle 2^{4(n+1)-1}=160m_n+120+8\)

If we define:

\(\displaystyle m_{n+1}=16m_{n}+12\) where \(\displaystyle m_1=0\)

then we may write:

\(\displaystyle 2^{4(n+1)-1}=10m_{n+1}+8\)

thereby completing the proof by induction.

Thus, we may write:

\(\displaystyle 2^{111k}=\left(2^{111} \right)^k=\left(10m_{28}+8 \right)^k\) where \(\displaystyle k\in\mathbb{N}\)

By the binomial theorem (and the fact that $m_n$ is always even), we find that:

\(\displaystyle \left(10m_{28}+8 \right)^k=\sum_{j=0}^k\left({k \choose j}\left(10m_{28} \right)^{k-j}2^{3j} \right)=20n_k+2^{3k}\)

where \(\displaystyle n_k\in\mathbb{N}\)

Hence:

\(\displaystyle 2^{222}=20n_2+2^6=20\left(n_2+3 \right)+4\)

\(\displaystyle 2^{333}=20n_3+2^9=20\left(n_3+25 \right)+12\)

\(\displaystyle 2^{444}=20n_4+2^{12}=20\left(n_4+204 \right)+16\)

Adding, we then find:

\(\displaystyle 2^{222}+2^{333}+2^{444}=20(n_2+n_3+n_4+232)+32=20(n_2+n_3+n_4+233)+12\)

And so, dividing by 2, we find:[/I]

\(\displaystyle \frac{2^{222}+2^{333}+2^{444}}{2}=10(n_2+n_3+n_4+233)+6\)

Thus, the last digit is 6.


Alternate solution (from eddybob123):
We notice a pattern in the last digit of \(\displaystyle 2^n\):

\(\displaystyle \text{If}~n\equiv 1~\text{(mod}~4)~\text{then}~2^n\equiv 2~\text{(mod}~10)\)
\(\displaystyle \text{If}~n\equiv 2~\text{(mod}~4)~\text{then}~2^n\equiv 4~\text{(mod}~10)\)
\(\displaystyle \text{If}~n\equiv 3~\text{(mod}~4)~\text{then}~2^n\equiv 8~\text{(mod}~10)\)
\(\displaystyle \text{If}~n\equiv 0~\text{(mod}~4)~\text{then}~2^n\equiv 6~\text{(mod}~10)\)

Since $221\equiv 1~\text{(mod}~4)$, $332\equiv 0~\text{(mod}~4)$, and $443\equiv 3~\text{(mod}~4)$, then $2^{221}+2^{332}+2^{443}~\text{(mod}~10)\equiv 2+6+8~\text{(mod}~10)\equiv 6 ~\text{(mod}~10)$
 
Status
Not open for further replies.