Jump to content


Photo
- - - - -

The 1000 Coin Problem


  • Please log in to reply
26 replies to this topic

#1 Qetesuesi

Qetesuesi

    HPC Veteran

  • Members
  • PipPipPipPip
  • 2,071 posts

Posted 08 November 2011 - 11:44 AM

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.
Posted Image

"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

#2 Wig

Wig

    HPC Poster

  • New Members
  • PipPip
  • 147 posts

Posted 08 November 2011 - 11:57 AM

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! B)

#3 blackgoose

blackgoose

    HPC Regular

  • Members
  • PipPipPip
  • 834 posts

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 thod

thod

    HPC Veteran

  • New Members
  • PipPipPipPip
  • 2,213 posts

Posted 08 November 2011 - 12:20 PM

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 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 Qetesuesi

Qetesuesi

    HPC Veteran

  • Members
  • PipPipPipPip
  • 2,071 posts

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! B)


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 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.


What do you mean by this?

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

Posted Image

"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

#6 Qetesuesi

Qetesuesi

    HPC Veteran

  • Members
  • PipPipPipPip
  • 2,071 posts

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?
Posted Image

"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

#7 thod

thod

    HPC Veteran

  • New Members
  • PipPipPipPip
  • 2,213 posts

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 Qetesuesi

Qetesuesi

    HPC Veteran

  • Members
  • PipPipPipPip
  • 2,071 posts

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.
Posted Image

"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

#9 europbaron

europbaron

    HPC Regular

  • Members
  • PipPipPip
  • 749 posts
  • Location:Glasgow

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 hotairmail

hotairmail

    Tired of life

  • Members
  • PipPipPipPipPipPipPip
  • 29,539 posts

Posted 08 November 2011 - 03:46 PM

Do we have to do this in our heads?

"The chicken is radiating disorder out into the wider universe."


#11 bendy

bendy

    HPC Senior Veteran

  • Members
  • PipPipPipPipPip
  • 3,199 posts
  • About Me:You nosy bastards!

Posted 08 November 2011 - 03:55 PM

i've not even tried this and i need a drink!

#12 salamander

salamander

    HPC Veteran

  • Members
  • PipPipPipPip
  • 1,484 posts
  • Location:W. London

Posted 08 November 2011 - 04:21 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 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.

Formerly known as narrowescape, having just avoided being caught up in the madness of 2007. Now a happy homeowner, 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 europbaron

europbaron

    HPC Regular

  • Members
  • PipPipPip
  • 749 posts
  • Location:Glasgow

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 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 .


Nice. The proof is blindingly obvious once explained.

#14 bendy

bendy

    HPC Senior Veteran

  • Members
  • PipPipPipPipPip
  • 3,199 posts
  • About Me:You nosy bastards!

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 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 .


that makes sense tbh. :)

#15 Bloo Loo

Bloo Loo

    Ripened on the Diversity Vine

  • Members
  • PipPipPipPipPipPipPip
  • 52,865 posts
  • Location:Essex-the land of Equality
  • About Me:Im Bloo yabba dee yabba die.

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