Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

and every 2nd coin is flipped over to tails


then every 3rd coin is flipped over again


and so on, until every 1000th coin.

What coins remain as heads?

share|cite|improve this question

marked as duplicate by Gerry Myerson, t.b., Henning Makholm, Steven Stadnicki, Rasmus Nov 13 '11 at 7:47

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.

I have worked out that if the number of prime factors is even, then that coin number is going to be heads up. – bobobobo Nov 13 '11 at 3:33
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. – Henning Makholm Nov 13 '11 at 3:42
@HenningMakholm: given that the question ends with 'every 1000th' I'm presuming it's the former (and make this assumption in my answer). – Steven Stadnicki Nov 13 '11 at 3:45
It was on a show... perhaps it wasn't very much mathematical in context, so "4th, 5th, 6th" is most probably what OP meant. – Patrick Da Silva Nov 13 '11 at 3:55
@GerryMyerson Yeah, looks it to me. I was sure the question must have been asked previously but couldn't find an instance of it... – Steven Stadnicki Nov 13 '11 at 5:13
up vote 5 down vote accepted

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?

share|cite|improve this answer

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