Sign in to follow this  
Followers 0
Qetesuesi

The 1000 Coin Problem

27 posts in this topic

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.

Share this post


Link to post
Share on other sites

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)

Share this post


Link to post
Share on other sites

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.

Share this post


Link to post
Share on other sites

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.

Share this post


Link to post
Share on other sites

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

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites

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.

Share this post


Link to post
Share on other sites

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.

Share this post


Link to post
Share on other sites

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

Share this post


Link to post
Share on other sites

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.

Share this post


Link to post
Share on other sites

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

Share this post


Link to post
Share on other sites

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?

Share this post


Link to post
Share on other sites

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)

+1 Wig is correct

Share this post


Link to post
Share on other sites

Yes; since 16 is a square it will be overturned.

Best post of the lot for humour! What a clever way to combine the parallel threads-within-the-thread.

I was wondering if TBF could come up with a proof of his one-word answer?

And well done to Salamander. What I'd like to know though, is how you first set about approaching this problem. Did you go with the idea of squares from the start? My own typed-up proof (which I'll post if anyone's interested) starts at a fundamental level and only touches the question of squares towards the end....

Share this post


Link to post
Share on other sites

Best post of the lot for humour! What a clever way to combine the parallel threads-within-the-thread.

I was wondering if TBF could come up with a proof of his one-word answer?

And well done to Salamander. What I'd like to know though, is how you first set about approaching this problem. Did you go with the idea of squares from the start? My own typed-up proof (which I'll post if anyone's interested) starts at a fundamental level and only touches the question of squares towards the end....

Thanks :)

It actually took quite a while to figure it out, and I needed to read other posts to get me on my way. I'd seen the posts about 'factor parities', which made sense and spent some time scratching my head trying to think of some kind of formula to calculate the total number of factors. I'd also seen the posts about squares being the answer (without explanation) so wrote a simple program to print out all of the numbers with an even number of factors apart from the number 1 to check if only squares were valid answers. It was only once this was confirmed that I thought a bit more about exactly what the program was doing and the penny finally dropped about the pairing of factors apart from square roots.

As has been alluded to elsewhere, it 'should' be fairly obvious that for each factor, there is another factor that is its partner, and that the only case of identical partners is for square numbers but I had to go through through the above to 'get' this.

I'd be very interested to see your proof BTW :)

Share this post


Link to post
Share on other sites

Thanks :)

It actually took quite a while to figure it out, and I needed to read other posts to get me on my way. I'd seen the posts about 'factor parities', which made sense and spent some time scratching my head trying to think of some kind of formula to calculate the total number of factors. I'd also seen the posts about squares being the answer (without explanation) so wrote a simple program to print out all of the numbers with an even number of factors apart from the number 1 to check if only squares were valid answers. It was only once this was confirmed that I thought a bit more about exactly what the program was doing and the penny finally dropped about the pairing of factors apart from square roots.

As has been alluded to elsewhere, it 'should' be fairly obvious that for each factor, there is another factor that is its partner, and that the only case of identical partners is for square numbers but I had to go through through the above to 'get' this.

I'd be very interested to see your proof BTW :)

The proof is nice because of it's simplicity. Like you I initially started by trying to calculate how many factors a general number had, missing the obvious bit that it had to be even for most numbers. It gets quite nasty as you have to test each prime up to 499 for the larger numbers(there are 95 of them). Easy to do with a computer program by brute force but that is not a proof.

Qetesui - is this what you did when approaching from fundamentals? I'd like to see the proof.

Share this post


Link to post
Share on other sites

Many thanks both of you below.

Thanks :)

It actually took quite a while to figure it out, and I needed to read other posts to get me on my way. I'd seen the posts about 'factor parities', which made sense and spent some time scratching my head trying to think of some kind of formula to calculate the total number of factors. I'd also seen the posts about squares being the answer (without explanation) so wrote a simple program to print out all of the numbers with an even number of factors apart from the number 1 to check if only squares were valid answers. It was only once this was confirmed that I thought a bit more about exactly what the program was doing and the penny finally dropped about the pairing of factors apart from square roots.

As has been alluded to elsewhere, it 'should' be fairly obvious that for each factor, there is another factor that is its partner, and that the only case of identical partners is for square numbers but I had to go through through the above to 'get' this.

I'd be very interested to see your proof BTW :)

At the end of this post ;)

Of course if you're going to write a program to test all 1000 numbers in that way, no need for any pure maths at all. However that by itself will never yield a general proof you can generalise to any number of coins, so it's just as well that the computer, plus previous posters, gave you the impetus to light the bulb as to what was going on and why.

As you'll see from my proof (devised before I started this thread, without any help from anyone), I actually got to the point where I should have realised that it was all squares, but carried on with simple manual testing of particular numbers.

The proof is nice because of it's simplicity.

Agreed - simpler than mine below, which makes me feel a bit of a fool. I managed the hard part and then never realised the relatively simple point that I should be thinking in terms of squares!

Like you I initially started by trying to calculate how many factors a general number had, missing the obvious bit that it had to be even for most numbers. It gets quite nasty as you have to test each prime up to 499 for the larger numbers(there are 95 of them).

You do? What were you attempting? Of course that can't yield a general proof valid for any number of coins.

Easy to do with a computer program by brute force but that is not a proof.

Precisely, as above.

Qetesui - is this what you did when approaching from fundamentals? I'd like to see the proof.

Proof duly submitted:

Consider the following propositions:

(1) The coins that are finally heads up are precisely those which have been turned over an even number of times.

(2) A coin is turned over once for every divisor of its number including itself but excluding 1.

(3) Therefore, the problem is that of finding all numbers between 1 and 1000 which have an even number of such divisors.

(4) Every whole number x can be expressed as the product of its n distinct prime factors as follows:

x = p1q1 p2q2 ... pn-1q(n-1) pnq(n)

where the various p are the prime factors and the various q are their respective powers.

(5) So the set of all possible divisors of x is

{ p1r1 p2r2 ... pn-1r(n-1) pnr(n) }

for all ri such that 0 ≤ ri ≤ qi .

(6) So the set of all divisors relevant to our question is the above without the ‘trivial’ case where all the powers of the prime factors are zero, i.e. the factor 1.

(7) So for the xth coin to be heads in the end, we require the number of elements of the set described in (6) to be even; so the number in the set described in (5) must be odd.

(8) In other words, (q1 + 1) (q2 + 1) ... (qn-1 + 1) (qn + 1) must be odd.

(9) But this is possible only when every bracketed factor is odd.

(10) Therefore every q must be even.

(11) So the numbers we’re looking for are precisely those which can be expressed as products of even powers of primes.

(12) This, certainly, includes all those which are even powers of only one prime, viz.

22, 24, 26, 28 (and no further with 2 because 210 = 1024 > 1000),

32, 34, 36 (and again no further because 38 = 6561 > 1000),

52, 54,

72 (and no further because 74 = 2401 > 1000, so a fortiori with higher primes),

112, 132, 172, 192, 232, 292, 312 (and no further because 312 = 961 but 372 > 1000).

(13) It also includes all products of pairs of the above which are still under 1000. But if we count down, we know that such a product has to be at least 22 times one of the numbers listed above, so given that 172 x 22 > 1000, we know that no such product involves the last five in the list in (12).

(14) 112 x 22 and 132 x 22 are possible, but as 112 x 32 > 1000, no other multiple involving 11 or 13 can be.

(15) At this point I think it’s helpful to write out the above smaller-prime solutions in ascending order: 4, 9, 16, 25, 49, 64, 81, 256, 625, 729.

(16) Now at a glance, we can identify the remaining pair-product solutions as follows:

4 x 9, 4 x 25, 4 x 49, 4 x 81, 9 x 16, 9 x 25, 9 x 49, 9 x 64, 16 x 25, 16 x 49.

(17) Finally, there is just one solution which is the product of three of the ‘basic’ solutions listed in (12), namely 22 x 32 x 52 or 900. Clearly, there can be none higher than that.

(18) By my reckoning that makes 30 solutions out of the 1000. But of course the first coin is never turned over so will also be heads. So total is 31. Really very surprising how few that is!

As you can see from the above, it's all very elegant up to (11) - and that was the point at which I should have realised they were all squares and only squares. That would have saved the messiness from (12) on!

Share this post


Link to post
Share on other sites

Firstly, it's good to see a bunch of maths types having a good chat. I am genuinely in awe of how your minds work.

Nadal has bad knees and I think he will be pat his peak before he can get past Federer. I also think he's run into Djokevic at the wrong time and he will take some of the majors that otherwise will be there for Nadal. I don't think Federer will win another, which is a shame as I think he is/was the most talented tennis player ever.

And just to show that "us maths types" aren't all geeky, I'll rejoin the sports part of this thread.

I agree about Nadal - though not sure about the knees thing, people have been saying that for years and still he won several more GSs with them. The big issue is indeed Djokovic. This time last year I'd have said it was a virtual cert Nadal would overhaul Federer - but the Djoker's fantastic current year immediately puts that in doubt. It now looks like each of these two will prevent the other from getting to 16 or 17 - but their combined final tally could still be an impressive 25 or so!

Also, what a shame we didn't get to see Nadal vs Djoker at the French Open final. Who knows what would have happened?

Meanwhile, to mention the elephant in the room - the trouble with Murray is that Nadal and Djoker are, currently, the only two players whom he's unlikely to beat in any given encounter. So to win a GS he basically has to hope they're both knocked out before he can meet them. One, possibly - but two in the same tournament? That, I think, sums up the obstacle to his first GS title.

Given that almighty constraint, his 2011 GSs have been about as good as it could possibly be: a final and three semis. And they're all a case in point: he got to the Australian Open final by virtue of Nadal's dismissal by Ferrer, and Nadal beat him in all three other semifinals.

Share this post


Link to post
Share on other sites

I'm sorry.... just because at times you can offer a perfectly reasonable and well thought out opinion on a sporting matter doesn't meant fundamentally you are not still a very proud 'geek'. :lol:

Would you call yourself a sports geek then?

Anyway maths isn't my #1 interest so I can't be a geek can I?

Share this post


Link to post
Share on other sites

I'm sorry.... just because at times you can offer a perfectly reasonable and well thought out opinion on a sporting matter doesn't meant fundamentally you are not still a very proud 'geek'. :lol:

Yeah, but real geeks, the nerdiest sort, go to cosplay conventions and dress up like their heros and know all the details about their heros' exploits and even stage "skits" where they act out pathetic imitations of their heros' pursuits.

You'd never find sports fanatics doing that kind of thing ...

trap1.jpg

:D

Share this post


Link to post
Share on other sites

Consider the following propositions:

(1) The coins that are finally heads up are precisely those which have been turned over an even number of times.

(2) A coin is turned over once for every divisor of its number including itself but excluding 1.

(3) Therefore, the problem is that of finding all numbers between 1 and 1000 which have an even number of such divisors.

(4) Every whole number x can be expressed as the product of its n distinct prime factors as follows:

x = p1q1 p2q2 ... pn-1q(n-1) pnq(n)

where the various p are the prime factors and the various q are their respective powers.

(5) So the set of all possible divisors of x is

{ p1r1 p2r2 ... pn-1r(n-1) pnr(n) }

for all ri such that 0 ≤ ri ≤ qi .

(6) So the set of all divisors relevant to our question is the above without the ‘trivial’ case where all the powers of the prime factors are zero, i.e. the factor 1.

(7) So for the xth coin to be heads in the end, we require the number of elements of the set described in (6) to be even; so the number in the set described in (5) must be odd.

(8) In other words, (q1 + 1) (q2 + 1) ... (qn-1 + 1) (qn + 1) must be odd.

(9) But this is possible only when every bracketed factor is odd.

(10) Therefore every q must be even.

(11) So the numbers we’re looking for are precisely those which can be expressed as products of even powers of primes.

(12) This, certainly, includes all those which are even powers of only one prime, viz.

22, 24, 26, 28 (and no further with 2 because 210 = 1024 > 1000),

32, 34, 36 (and again no further because 38 = 6561 > 1000),

52, 54,

72 (and no further because 74 = 2401 > 1000, so a fortiori with higher primes),

112, 132, 172, 192, 232, 292, 312 (and no further because 312 = 961 but 372 > 1000).

(13) It also includes all products of pairs of the above which are still under 1000. But if we count down, we know that such a product has to be at least 22 times one of the numbers listed above, so given that 172 x 22 > 1000, we know that no such product involves the last five in the list in (12).

(14) 112 x 22 and 132 x 22 are possible, but as 112 x 32 > 1000, no other multiple involving 11 or 13 can be.

(15) At this point I think it’s helpful to write out the above smaller-prime solutions in ascending order: 4, 9, 16, 25, 49, 64, 81, 256, 625, 729.

(16) Now at a glance, we can identify the remaining pair-product solutions as follows:

4 x 9, 4 x 25, 4 x 49, 4 x 81, 9 x 16, 9 x 25, 9 x 49, 9 x 64, 16 x 25, 16 x 49.

(17) Finally, there is just one solution which is the product of three of the ‘basic’ solutions listed in (12), namely 22 x 32 x 52 or 900. Clearly, there can be none higher than that.

(18) By my reckoning that makes 30 solutions out of the 1000. But of course the first coin is never turned over so will also be heads. So total is 31. Really very surprising how few that is!

As you can see from the above, it's all very elegant up to (11) - and that was the point at which I should have realised they were all squares and only squares. That would have saved the messiness from (12) on!

I've got to admit that going from the definition of the set in (5) to the formula giving the total number of factors in (8) puzzled me for a while, but then I didn't do much on sets while at Uni, and that was a looong time ago.

All very elegant, and all the more impressive that you figured it out from scratch without any help :)

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!


Register a new account

Sign in

Already have an account? Sign in here.


Sign In Now
Sign in to follow this  
Followers 0