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
    I have worked out that if the number of prime factors is _even_, then that coin number is going to be heads up.2011-11-13
  • 0
    Interesting. Does the sequence "2nd, 3rd" continue "4th, 5th, 6th", or "5th, 7th, 11th"? In the former case, coin 4 is going to end up opposite to coin 2, but both have only one prime factor.2011-11-13
  • 0
    @HenningMakholm: given that the question ends with 'every 1000th' I'm presuming it's the former (and make this assumption in my answer).2011-11-13
  • 0
    It was on a show... perhaps it wasn't very much mathematical in context, so "4th, 5th, 6th" is most probably what OP meant.2011-11-13
  • 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?