# The 1000 Coin Problem

### #1

Posted 08 November 2011 - 11:44 AM

The problem comes in at 1:10 and I transcribe it below:

“You’ve got a row of coins. Lots of coins, 1000 coins. They’re all heads up. I go along, and every second coin I turn over. So, the second, the fourth, the sixth – I turn them all over back to tails. Then I take every third coin, so coins number three, six, nine and so on, and turn them over. So I guess coin number six is now back to being heads. And so on, and so on, and so on, until eventually I turn over every 1000th coin, i.e. the last coin.

“Here’s the question: Which coins are heads up?”

Have a go.

"I think the idea is that if you hear something for long enough from a variety of sources, you automatically end up thinking it is self evident, without questionning the matter." - *_w_*

"People would rather be wrong, but in the right crowd." - *Daniel Hannan*

*"People believe what they've repeatedly been told is true even when the evidence strongly refutes it and even when they know the evidence strongly refutes it.*" - RK

**"Faced with the choice between changing one's mind and proving that there is no need to do so, almost everyone gets busy on the proof**."

**"****There is something wonderful in seeing a wrong-headed majority assailed by truth**"** - J K Galbraith**

### #2

Posted 08 November 2011 - 11:57 AM

Coins ending up heads up are the square numbers by the looks of it...

1

4

9

16

25

36

49

64

81

100

all the way up to 961

etc...

Like it!

### #3

Posted 08 November 2011 - 12:03 PM

See the video extract.

“Here’s the question: Which coins are heads up?”

Have a go.

Those numbers that are either

1. not divisible by 2 or 3

2. divisible by both 2 and 3.

That is satisfied by the number 1 and numbers of the form 6n-1, 6n, 6n+1 where n is a positive whole number.

Incidently that boy also suffers from aspbergers, so should not be presented as a typical maths genius, as per the program title. Plus genius is taking it too far - prodigy is a better definition.

### #4

Posted 08 November 2011 - 12:20 PM

2 will be turned once.

3 will be turned once.

4 will be turned twice, once on the 2 pass, once on the 4 pass.

5 will be turned once.

6 will be turned 3 times, once on the 2 pass, once on the 3 pass, once on the 6 pass.

7 will be turned once.

8 will be turned 3 times, once on the 2 pass, once on the 4 pass, once on the 8 pass.

9 will be turned twice once on the 3 pass, once of the 9 pass,

Thus we see that heads or tails depends on the parity of the number of factors of that number. I suspect that this is like prime numbers where there is no simple formula for saying which numbers are prime.

### #5

Posted 08 November 2011 - 01:04 PM

Just lined up my stash of maples and it works out as below~

Coins ending up heads up are the square numbers by the looks of it...

1

4

9

16

25

36

49

64

81

100

all the way up to 961

etc...

Like it!

How do you prove that they are the only ones?

Those numbers that are either

1. not divisible by 2 or 3

2. divisible by both 2 and 3.

That is satisfied by the number 1 and numbers of the form 6n-1, 6n, 6n+1 where n is a positive whole number.

Incidently that boy also suffers from aspbergers, so should not be presented as a typical maths genius, as per the program title. Plus genius is taking it too far - prodigy is a better definition.

Counterexample to (1) - 5

Counterexample to (2) - 12

How would you define the difference? Genius being more original, prodigy just a matter of taking GCSEs and A levels five years before yer mates?

1 will never be turned..

2 will be turned once.

3 will be turned once.

4 will be turned twice, once on the 2 pass, once on the 4 pass.

5 will be turned once.

6 will be turned 3 times, once on the 2 pass, once on the 3 pass, once on the 6 pass.

7 will be turned once.

8 will be turned 3 times, once on the 2 pass, once on the 4 pass, once on the 8 pass.

9 will be turned twice once on the 3 pass, once of the 9 pass,

Thus we see that heads or tails depends on theparity of the number of factorsof that number. I suspect that this is like prime numbers where there is no simple formula for saying which numbers are prime.

What do you mean by this?

**Edited by Qetesuesi, 08 November 2011 - 01:06 PM.**

"I think the idea is that if you hear something for long enough from a variety of sources, you automatically end up thinking it is self evident, without questionning the matter." - *_w_*

"People would rather be wrong, but in the right crowd." - *Daniel Hannan*

*"People believe what they've repeatedly been told is true even when the evidence strongly refutes it and even when they know the evidence strongly refutes it.*" - RK

**"Faced with the choice between changing one's mind and proving that there is no need to do so, almost everyone gets busy on the proof**."

**"****There is something wonderful in seeing a wrong-headed majority assailed by truth**"** - J K Galbraith**

### #6

Posted 08 November 2011 - 01:20 PM

Dunno - give me one on sport.

Okay - will either Nadal or Djokovic surpass Federer's Grand Slam record of 16 titles?

"I think the idea is that if you hear something for long enough from a variety of sources, you automatically end up thinking it is self evident, without questionning the matter." - *_w_*

"People would rather be wrong, but in the right crowd." - *Daniel Hannan*

*"People believe what they've repeatedly been told is true even when the evidence strongly refutes it and even when they know the evidence strongly refutes it.*" - RK

**"Faced with the choice between changing one's mind and proving that there is no need to do so, almost everyone gets busy on the proof**."

**"****There is something wonderful in seeing a wrong-headed majority assailed by truth**"** - J K Galbraith**

### #7

Posted 08 November 2011 - 01:32 PM

parity of the number of factors

What do you mean by this?

Parity means odd or even.

The factors are those integers which divide a number without leaving a remainder.

Thus 12 has the factors 2, 3, 4, and 6. The number of factors is 4, even parity.

### #8

Posted 08 November 2011 - 01:49 PM

Parity means odd or even.

The factors are those integers which divide a number without leaving a remainder.

Thus 12 has the factors 2, 3, 4, and 6. The number of factors is 4, even parity.

But in terms of the problem set, 12 is also a factor. So the parity here is odd.

"I think the idea is that if you hear something for long enough from a variety of sources, you automatically end up thinking it is self evident, without questionning the matter." - *_w_*

"People would rather be wrong, but in the right crowd." - *Daniel Hannan*

**"****There is something wonderful in seeing a wrong-headed majority assailed by truth**"** - J K Galbraith**

### #9

Posted 08 November 2011 - 03:03 PM

But in terms of the problem set, 12 is also a factor. So the parity here is odd.

Clearly, as stated, this does boil down to the parity of the number of factors. If the parity of the number of factors is even then the coin will be turned an odd number of times. 12 has 6 factors 1, 2, 3, 4, 6, 12. So the coin is turned 5 times leaving it tails up.

It's easy to work it out for any given number, but I can't think of a general proof (as there is no formula for primes and hence factors).

For example coin 536.

Prime factors are 2, 2, 2 and 67. So all factors are 1, 2, 4, 8, 67, 134, 268 and 536, i.e. there are 8 factors. Parity is even so coin is turned an odd number of times. So coin 536 is tails up at the end.

### #10

Posted 08 November 2011 - 03:46 PM

### #11

Posted 08 November 2011 - 03:55 PM

### #12

Posted 08 November 2011 - 04:21 PM

Any coin will only end heads up if it is flipped an even number of times (or not at all, as will be thecase for the first coin)

All prime numbered coins will only ever be flipped once so will always end up on tails and can be ignored

Every other numbered coin will be flipped once for each of its unique factors (excluding 1) e.g. 6 will be flipped 3 times - when flipping coins that are multiples of 2, 3, and 6

For any number that

**isn't**a square, dividing by any of the unique factors will give another one of the unique factors, so every unique factor can be paired with another, meaning that there will always be an even number of factors if 1 is included.

eg. for 12:

1 X 12, 2 X 6, 4 X3 (= 6 unique factors)

Therefore all such numbers (after excluding 1) will be flipped an odd number of times and end up on tails.

For square numbered coins however, all of the factors will pair up as above

**except for the square root**(which divides into the number to give itself), meaning that the total number of unique factors will be odd.

e.g. for 36

1 x 36, 2 x 18, 3 x 12, 4 x 9,

**6 x 6**( = 9 unique factors)

Therefore, after ignoring 1 as a factor, all square numbered coins will be flipped an even number of times (or none at all for the first coin) and these are the only numbers that will end up on heads .

**Edited by salamander, 08 November 2011 - 04:24 PM.**

**owner**, courtesy of gold appreciation since then. Still expecting an HPC but perhaps not so much for houses in Greater London, where I live and work.

### #13

Posted 08 November 2011 - 04:31 PM

Only the square numbered coins end up as heads. Here's why:

Any coin will only end heads up if it is flipped an even number of times (or not at all, as will be thecase for the first coin)

All prime numbered coins will only ever be flipped once so will always end up on tails and can be ignored

Every other numbered coin will be flipped once for each of its unique factors (excluding 1) e.g. 6 will be flipped 3 times - when flipping coins that are multiples of 2, 3, and 6

For any number thatisn'ta square, dividing by any of the unique factors will give another one of the unique factors, so every unique factor can be paired with another, meaning that there will always be an even number of factors if 1 is included.

eg. for 12:

1 X 12, 2 X 6, 4 X3 (= 6 unique factors)

Therefore all such numbers (after excluding 1) will be flipped an odd number of times and end up on tails.

For square numbered coins however, all of the factors will pair up as aboveexcept for the square root(which divides into the number to give itself), meaning that the total number of unique factors will be odd.

e.g. for 36

1 x 36, 2 x 18, 3 x 12, 4 x 9,6 x 6( = 9 unique factors)

Therefore, after ignoring 1 as a factor, all square numbered coins will be flipped an even number of times (or none at all for the first coin) and these are the only numbers that will end up on heads .

Nice. The proof is blindingly obvious once explained.

### #14

Posted 08 November 2011 - 04:34 PM

Only the square numbered coins end up as heads. Here's why:

Any coin will only end heads up if it is flipped an even number of times (or not at all, as will be thecase for the first coin)

All prime numbered coins will only ever be flipped once so will always end up on tails and can be ignored

Every other numbered coin will be flipped once for each of its unique factors (excluding 1) e.g. 6 will be flipped 3 times - when flipping coins that are multiples of 2, 3, and 6

For any number thatisn'ta square, dividing by any of the unique factors will give another one of the unique factors, so every unique factor can be paired with another, meaning that there will always be an even number of factors if 1 is included.

eg. for 12:

1 X 12, 2 X 6, 4 X3 (= 6 unique factors)

Therefore all such numbers (after excluding 1) will be flipped an odd number of times and end up on tails.

For square numbered coins however, all of the factors will pair up as aboveexcept for the square root(which divides into the number to give itself), meaning that the total number of unique factors will be odd.

e.g. for 36

1 x 36, 2 x 18, 3 x 12, 4 x 9,6 x 6( = 9 unique factors)

Therefore, after ignoring 1 as a factor, all square numbered coins will be flipped an even number of times (or none at all for the first coin) and these are the only numbers that will end up on heads .

that makes sense tbh.

### #15

Posted 08 November 2011 - 05:38 PM

See the video extract.

The problem comes in at 1:10 and I transcribe it below:

"You've got a row of coins. Lots of coins, 1000 coins. They're all heads up. I go along, and every second coin I turn over. So, the second, the fourth, the sixth – I turn them all over back to tails. Then I take every third coin, so coins number three, six, nine and so on, and turn them over. So I guess coin number six is now back to being heads. And so on, and so on, and so on, until eventually I turn over every 1000th coin, i.e. the last coin.

"Here's the question: Which coins are heads up?"

Have a go.

how did they all get to be heads up in the first place....must have been a lot of turning before the cameras show up?

^{WARNING}

**Your ****country is at risk ****if you**** do not keep up repayments ****on a gilt or other loan secured on it**

** **

^{}

#### 0 user(s) are reading this topic

0 members, 0 guests, 0 anonymous users