How many coins are still heads up? I'm watching this documentary: https://www.youtube.com/watch?v=qVjnPvFENEE&t=2212s and around the 6 minute mark, the professor asks a question that goes like this:
"I have 1000 coins and they're all heads up. I go along and turn over every 2nd coin, so 2, 4, 6, 8 and so on. I then turn over every 3rd one, so 3, 6, 9, 12 and so on. So now coin 6 and 12 are back in the heads position. I do this all the way up to 1000, so which coins are heads up?"
I attempted it and I thought it was all the odd numbers but the coins turning back onto heads tripped me up so what do you guys think it is?
Thanks,
PS. I don't have any degree in maths, I'm just a curious kid.
 A: A useful technique in solving such problems is to scale things down--work on a smaller case, to detect patterns.
For instance, suppose we have only $6$ coins.  Put them in a row, and number them from $1$ to $6$:  $$\{1, 2, 3, 4, 5, 6\}.$$
Now look at any single coin, say coin $4$.  How many times does it get flipped when we go through this process?  Well, it gets flipped once when going through the multiples of $2$:  $\{2, 4, 6\}$.  It does not get flipped when going through the multiples of $3$, since $4$ is not a multiple of $3$.  And then it does get flipped once again when we go through the multiples of $4$.  So it get flipped a total of $2$ times.
How many times does $5$ get flipped?  Well, only once, when we go through multiples of $5$.
And how many times does $6$ get flipped?  Three times.
Clearly, this situation has something to do with the divisors of the number on the coin.  The divisors of $4$ are $1, 2, 4$.  And the divisors of $5$ are $1, 5$, and the divisors of $6$ are $1, 2, 3, 6$.  So it looks like the number of times a given coin is flipped is one less than its number of divisors.  The reason why it is one less, is because we don't start the process by flipping every coin--we start with the multiples of $2$.
Let's work out a larger example.  Say we are interested in coin number $100$.  The divisors of $100$ are:  $$1, 2, 4, 5, 10, 20, 25, 50, 100.$$  There are $9$ divisors, so we suspect that this coin would be flipped $8$ times.  Can you check that this is true?
So if there are $1000$ coins, the number of coins that are heads up is equal to the number of coins that have an odd number of divisors (including $1$, and the number itself).  Can you go through a list of the first $1000$ such numbers and see which ones have an odd number of divisors?  I will start you out with a partial list:
$$\begin{array}{c|c}
n & \sigma_0(n) \\
\hline 1 & 1 \\
 2 & 2 \\
 3 & 2 \\
 4 & 3 \\
 5 & 2 \\
 6 & 4 \\
 7 & 2 \\
 8 & 4 \\
 9 & 3 \\
 10 & 4 \\
 11 & 2 \\
 12 & 6 \\
 13 & 2 \\
 14 & 4 \\
 15 & 4 \\
 16 & 5 \\
\end{array}$$
The second column with heading $\sigma_0(n)$ represents the number of divisors of $n$.  Which of these are odd?  Do you see a pattern?  If you do, how would you go about proving this pattern?
