2
$\begingroup$

This question already has an answer here:

$10$ people are seating on chairs around a circular table. These chairs are marked in a clockwise manner. There is a ball on the man’s hand who is seated on $0$ marked chair, and the ball will be passed from one man to another in clockwise manner. In first step, the ball goes to $1$ marked chair with $1^1$ turn. In second step, from there, the ball goes to 5 marked chair with $2^2$ turns. In third step, the ball goes to $2$ marked chair by $3^3$ turns from $5$ marked chair. By this means, in which chair the ball will be in $2020$th step?

Source: Bangladesh Mathematical Olympiad (BdMO)

I'm not sure about exactly how many turns are required in the 2020th step. The question is a great deal ambiguous. Does the $n$th step require $n^n$ turns? Or does the pattern of $1^1, 2^2, 3^3$ repeat itself?

But often in cases like this where there are multiple possibilities for the answer, the one that seems more intuitive and makes more common sense is more likely to be the answer. After solving the problem in both the possible ways, comparing the two different answers should make the answer obvious.

I've already tried to solve the problem the triad of turns style in a self-answer. However, I can't solve it the $n^n$ way; it's too advanced for me. I'm only an 8th grader, you see.

$\endgroup$

marked as duplicate by Jyrki Lahtonen, Lord Shark the Unknown, José Carlos Santos sequences-and-series Jan 9 at 10:14

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ 2020th step you mean that it will take $2020^{2020}$ turns from it's previous position right? $\endgroup$ – Devendra Singh Rana Dec 23 '17 at 18:45
  • 1
    $\begingroup$ @DevendraSinghRana i'm not sure. this is what i'm confused about. my keyboard isn't working anymore, i couldn't write much in the question $\endgroup$ – Soha Farhin Pine Dec 23 '17 at 18:48
  • $\begingroup$ I have got an interesting sequence summation $n^n$ then take modulo 10 it is your position in the nth step $\endgroup$ – Devendra Singh Rana Dec 23 '17 at 18:49
  • 1
    $\begingroup$ @CloseVoters if you voting to close this question because the question appears to lack any attempt, see this answer. $\endgroup$ – Simply Beautiful Art Dec 24 '17 at 0:39
  • $\begingroup$ @SimplyBeautifulArt Sorry for my vote. I've casted a re-open vote. One more to go. $\endgroup$ – GNUSupporter 8964民主女神 地下教會 Dec 24 '17 at 13:41
4
$\begingroup$

Assuming that the $n$th step moves the ball $n^n$ places around the circle, we need to find the integer $x$ such that $0 \leq x < 10$ and $$ \sum_{n=1}^{2020} n^n \equiv x \pmod{10}. $$

Note that $$\sum_{n=1}^{2020} n^n \equiv \sum_{n=1}^{2020} a_n \pmod{10},$$ where $0 \leq a_n < 10$ and $n^n \equiv a_n$ for each $n,$ and that $n^n \equiv m^n \pmod{10}$ if $n \equiv m \pmod{10}.$ Also observe the following for any integer $k$: \begin{align} 3^4 \equiv 7^4 \equiv 9^2 &\equiv 1 \pmod{10}, \\ 2^4 \equiv 4^2 \equiv 8^4 &\equiv 6 \pmod{10}, \\ 6^k &\equiv 6 \pmod{10}, \\ 5^k &\equiv 5 \pmod{10}. \end{align}

The first $20$ terms of the series have the following equivalences: \begin{align} 1^1 &\equiv 1 \pmod{10}, \\ 2^2 &\equiv 4 \pmod{10}, \\ 3^3 &\equiv 7 \pmod{10}, \\ 4^4 &\equiv 6 \pmod{10}, \\ 5^5 &\equiv 5 \pmod{10}, \\ 6^6 &\equiv 6 \pmod{10}, \\ 7^7 \equiv (-3)^7 &\equiv 3 \pmod{10}, \\ 8^8 \equiv (-2)^8 &\equiv 6 \pmod{10}, \\ 9^9 \equiv (-1)^9 &\equiv 9 \pmod{10}, \\ 10^{10} \equiv 0^{10} &\equiv 0 \pmod{10}, \\ 11^{11} \equiv 1^{11} &\equiv 1 \pmod{10}, \\ 12^{12} \equiv 2^{12} &\equiv 6 \pmod{10}, \\ 13^{13} \equiv 3^{13} &\equiv 3 \pmod{10}, \\ 14^{14} \equiv 4^{14} &\equiv 6 \pmod{10}, \\ 15^{15} \equiv 5^{15} &\equiv 5 \pmod{10}, \\ 16^{16} \equiv 6^{16} &\equiv 6 \pmod{10}, \\ 17^{17} \equiv (-3)^{17} &\equiv 7 \pmod{10}, \\ 18^{18} \equiv (-2)^{18} &\equiv 4 \pmod{10}, \\ 19^{19} \equiv (-1)^{19} &\equiv 9 \pmod{10}, \\ 20^{20} \equiv 0^{20} &\equiv 0 \pmod{10}. \end{align}

That is, $a_1 = a_{11} = 1,$ $a_2 = a_{18} = 4,$ $a_3 = a_{17} = 7,$ $a_4 = a_6 = a_8 = a_{12} = a_{14} = a_{16} = 6,$ $a_5 = a_{15} = 5,$ $a_7 = a_{13} = 3,$ $a_9 = a_{19} = 9,$ and $a_{10} = a_{20} = 0.$

Also note that for any integer $n$ such that $1 \leq n \leq 20$ and any non-negative integer $k,$ $$ (n + 20k)^{n+20k} \equiv n^{n+20k} \equiv n^n \pmod{10}. $$ For $n = 10$ or $20$ this follows since $(n + 20k)^{n+20k} \equiv 0^{n+20k} \equiv 0 \pmod{10};$ for $n = 5$ or $15$ because $(n + 20k)^{n+20k} \equiv 5^{n+20k} \equiv 5 \pmod{10};$ for $n = 2$ or $18$ because $(n + 20k)^{n+20k} \equiv n^n n^{20k} \equiv 4 n^{20k} \pmod{10}$ and because $n^{20k} \equiv 6 \pmod{10};$ for $n = 4,6,8,12,14$ or $16$ because $(n + 20k)^{n+20k} \equiv n^n n^{20k} \equiv 6 n^{20k} \pmod{10}$ and because $n^{20k} \equiv 6 \pmod{10};$ and for $n = 1,3,7,9,11,13,17$ or $19$ because $(n + 20k)^{n+20k} \equiv n^n n^{20k} \pmod{10}$ and because $n^{20k} \equiv 1 \pmod{10}.$

The terms $a_n$ therefore repeat in a cycle of length $20,$ so $$ \sum_{n=1}^{2020} a_n = 101 \sum_{n=1}^{20} a_n = 101 \times 94 \equiv 4 \pmod{10}.$$

$\endgroup$
  • $\begingroup$ See here for a more general way. $\endgroup$ – Bill Dubuque Jan 9 at 4:36
  • $\begingroup$ @BillDubuque Very nice. I wondered whether it would have made more sense to post that answer here and mark the other question as a duplicate, although the newer question is formulated differently. $\endgroup$ – David K Jan 9 at 5:06
  • $\begingroup$ The problem is my answer uses methods far beyond 8th grade (= OP level here). $\endgroup$ – Bill Dubuque Jan 9 at 5:09
  • 1
    $\begingroup$ @BillDubuque That could be a consideration, but people sometimes post answers above an OP's skill level for the benefit of other readers. In this particular case I thought we might have a duplicate question situation. Or perhaps the cross-links that have now been established are good enough. $\endgroup$ – David K Jan 9 at 5:15
0
$\begingroup$

If the number of turns is greater than $9$, the actual number of chairs we have to ultimately move through can be calculated by taking modulo $10$.

Triad of $1^1, 2^2, 3^3$

  • Step #1 = $1^1$ turns
    Step #2 = $2^2$ turns
    Step #3 = $3^3$ turns

  • Step #4 = $1^1$ turns
    Step #5 = $2^2$ turns
    Step #6 = $3^3$ turns

$$...$$

The formula here is:

Step $n$ =

  • if   $n$$\mod 3$   equals $1$,  $1^1$ turns
  • if   $n$$\mod 3$   equals $2$,  $2^2$ turns
  • if   $n$$\mod 3$   equals $0$,  $3^3$ turns

The ball's position is furthered by $2$ places at the end of each triad of turns. This is because $1^1+2^2+3^2=32 \equiv 2\pmod {10}$.

You'll see that—
In triad $1$, initially the ball is in chair $0$ and ends up in chair $2$.
In triad $2$, initially the ball is in chair $2$ and ends up in chair $4$.
In triad $3$, initially the ball is in chair $4$ and ends up in chair $6$.

Now how many full triads are there in $2020$ steps?
$2020 \div 3=673$.
$2020 \equiv 1 \pmod{3}$.

This means the ball must have been moved $673\times2$ times. Modulo 10 gives us $6$. And the extra one step has $1^1$ turn. So the chair holding the ball should be the one marked $7$.

$\endgroup$
0
$\begingroup$

Sum sequence of $n^n$ = $1^1+2^2+3^3+\cdot\cdot\cdot+2020^{2020}$

Because of the cyclicity of powers:

$$1^1+2^2+3^3+4^4+5^5+6^6+7^7+8^8+9^9\\+10^{10}+11^{11}+12^{12}+13^{13}+14^{14}+15^{15}+16^{16}+17^{17}+18^{18}+19^{19}\\+20^{20}+21^{21}+22^{22}+23^{23}+24^{24}+25^{25}+26^{26}+27^{27}+28^{28}+29^{19}\\+30^{30}+31^{31}+32^{32}+33^{33}+34^{34}+35^{35}+36^{36}+37^{37}+38^{38}+39^{39}...\mod 10$$ $$=$$ $$1^1+2^2+3^3+4^4+5^1+6^2+7^3+8^4+9^1\\+10^2+11^3+12^4+13^1+14^2+15^3+16^4+17^1+18^2+19^3\\+20^4+21^1+22^2+23^3+24^4+25^1+26^2+27^3+28^4+29^1\\+30^2+31^3+32^4+33^1+34^2+35^3+36^4+37^1+38^2+39^3...\mod 10$$ $$=$$ $$1^1+2^2+3^3+4^4+5^1+6^2+7^3+8^4+9^1\\+0^2+1^3+2^4+3^1+4^2+5^3+6^4+7^1+8^2+9^3\\+0^4+1^1+2^2+3^3+4^4+5^1+6^2+7^3+8^4+9^1\\+0^2+1^3+2^4+3^1+4^2+5^3+6^4+7^1+8^2+9^3$$ $$...\mod 10$$

  1. $\boxed{x^\boxed{1}}=x^5=x^9=x^{13}=\cdot\cdot\cdot=x^{1+4n}$
    $\boxed{x^\boxed{2}}=x^6=x^{10}=x^{14}=\cdot\cdot\cdot=x^{2+4n}$
    $\boxed{x^\boxed{3}}=x^7=x^{11}=x^{15}=\cdot\cdot\cdot=x^{3+4n}$
    $\boxed{x^\boxed{4}}=x^8=x^{12}=x^{16}=\cdot\cdot\cdot=x^{4+4n}$

  2. For any digit $d$ and for any non-negative integer $p$,

    $d^p \mod 10=(10n+d)^p \mod 10$

The tens in the sequence can be gotten rid of. They don't add upto anything. The last digits are always zero.

$2020-\frac{2020}{10}\\=2020-202\\=1818.$

Now we are left with

$$\color{blue}{1^1+2^2+3^3+4^4+5^1+6^2+7^3+8^4+9^1}\\+\color{red}{1^3+2^4+3^1+4^2+5^3+6^4+7^1+8^2+9^3}\\+\color{blue}{1^1+2^2+3^3+4^4+5^1+6^2+7^3+8^4+9^1}\\+\color{red}{1^3+2^4+3^1+4^2+5^3+6^4+7^1+8^2+9^3}\\...$$

Every element in the blue-coloured set of numbers has an corresponding element of equal value in the red-coloured set of numbers.

  • $1^1 \equiv 1^3 \equiv 1 \pmod{10}$
  • $4^2 \equiv 4^4 \equiv 6 \pmod{10}$
  • $5^1 \equiv 5^3 \equiv 5 \pmod{10}$
  • $6^2 \equiv 6^4 \equiv 6 \pmod{10}$
  • $9^1 \equiv 9^3 \equiv 9 \pmod{10}$

  • $2^2 \equiv 8^2 \equiv 4 \pmod{10}$

  • $2^4 \equiv 8^4 \equiv 6 \pmod{10}$
  • $3^1 \equiv 7^3 \equiv 3 \pmod{10}$
  • $3^3 \equiv 7^1 \equiv 7 \pmod{10}$

Last digit of powers of n

The modulo 10 of the original sum is therefore:

$\frac{1818}{9+9}\times2(1+6+5+6+9+4+6+3+7)\\=\frac{1818}{18}\times2(47)\\=101\times94$

$101\times94 \equiv \boxed{4} \pmod{10}$

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.