2
$\begingroup$

Possible Duplicate:
A tedious puzzle (but not homework)

There was this question on a show called "Growing Pains Of a Teenage Genius"

The question is as follows:

  • 1000 coins are lined up, heads up
 oooooooooooooooooooooooooooooooooooo... 

and every 2nd coin is flipped over to tails

 o•o•o•o•o•o•o•o•o•o•o•o•o•o•o•o•o•o•... 

then every 3rd coin is flipped over again

 o•••ooo•••ooo•••ooo•••ooo•••ooo•••oo... 

and so on, until every 1000th coin.

What coins remain as heads?

  • 0
    @GerryMyerson Yeah, looks it to me. I was sure the question must have been asked previously but couldn't find an instance of it...2011-11-13

1 Answers 1

6

You're close - it's not just prime factors, but in fact all numbers with an odd number of factors that will wind up heads. Imagine that the coins start tails: then every number with a factor of 1 will be flipped over (i.e., all of them); next, every number with a factor of 2 will be flipped back, etc., so each number will be flipped over once for each of its factors, and those numbers with an odd number of total factors will be left heads-up.

The big hint from here: for every number $n$, if $x$ is a factor of $n$ then so is $n/x$, and that lets you pair off the factors - so how can such a number have an odd number of total factors?