[bonanova]

While your back is turned a friend places three coins, numbered 1, 2 and 3 on a table.

They are placed so that 1, 2, or 3 Tails are showing. That is, they are not all Heads.

Your task, without looking, is to have your friend make them all show Heads.

You do this by a series of instructions in which you identify one of the coins by number and ask him to turn it over.

After turning over the identified coin your friends tells you whether or not you have succeeded.

Because this is a finite game, success is eventually guaranteed - within say N trials.

What strategy minimizes N?

What is the minimum value of N?

What is the probability of success in (N-1) moves or fewer? (N-2) moves or fewer? ... down to 2 moves or fewer?

[Guest]

I think the maximum you should need is seven moves. 1, 2, 1, 3, 1, 2, 1.

The minimum value of N seems like a silly question...1

[Guest]

First time here.. nice puzzle to start with..

The puzzle can be restated as: you start with all tails facing up, and your friend has some pattern in his/her mind (say: head,tail,tail). You need to flip coins until you reach the pattern your friend has in mind.

...is to use gray coding:

000 -> Initial state

001 -> Flip coin 3

011 -> Flip coin 1

010 -> Flip coin 3 ..etc

110

111

101

100

So N is 7.

[Guest]

..would then be:

p(6) = prob that the pattern is not 100 = 1 - 1/8

p(5) = prob that the pattern is not 100 or 101 = 1 - 2/8

..

p(2) = prob that the pattern is 001 or 011 = 2/8

Edited August 14, 2009 by methinks

[Guest]

While your back is turned a friend places three coins, numbered 1, 2 and 3 on a table.

They are placed so that 1, 2, or 3 Tails are showing. That is, they are not all Heads.

Your task, without looking, is to have your friend make them all show Heads.

You do this by a series of instructions in which you identify one of the coins by number and ask him to turn it over.

After turning over the identified coin your friends tells you whether or not you have succeeded.

Because this is a finite game, success is eventually guaranteed - within say N trials.

What strategy minimizes N?

What is the minimum value of N?

What is the probability of success in (N-1) moves or fewer? (N-2) moves or fewer? ... down to 2 moves or fewer?

There are 7 distinct starting positions, because the H H H configuration is not an option. What this means is that for each position, there is a 4 in 7 chance that the coin is tails and thus requires flipping. You want to turn over the coins in such a sequence that maximizes the number of positions that have been flipped from the original, without producing identical configurations. I'll use the notation: T for Turned from original configuration, U for Unturned.

So you start UUU:

TUU

TTU

TTT

TUT

UUT

UTT

UTU

In this order, all 7 possible configurations are hit without duplication and you must hit all 7 to be certain, so N in this case is 7. Thingking about the probability, even though a T is slightly more likely than a U, the odds of each of the 7 given configurations are equally likely, so the probability of success in 6 moves is 6 out of 7, probability of success in 5 moves is 5 out of 7... etc ... down to success in 1 move as 1 out of 7.

[Guest]

Answers to the Questions

What strategy minimizes N?

Use a form of binary grey scale (see below)

What is the minimum value of N?

7

What is the probability of success in (N-1) moves or fewer? (N-2) moves or fewer? ... down to 2 moves or fewer?

P = (N-X)/N with X being number of steps fewer that N.

Explanation of the Answers

For those who don't know, Grey scale is a way to go though all possible combinations of X number of binary digits without repetition and only changing one bit (penny) at a time in a countiuous cycle.

For example, to go through all possible combinations of 2 bits (pennies), normally would be 00, 01, 10, 11. In grey scale it would be 00, 01, 11, 10 or 00, 10, 11, 01.

The minimum value is 7 because that is one less that all the possible combinations of 3 pennies besides the initial placement. "While your back is turned a friend places three coins, numbered 1, 2 and 3 on a table". Lets call heads 1 and tails 0. All possible combinations are:

0,0,0 - all tails

0,0,1

0,1,0

0,1,1

1,0,0

1,0,1

1,1,0

1,1,1 - all heads

And, we know that the first combination is not all heads by the statements "They are placed so that 1, 2, or 3 Tails are showing. That is, they are not all Heads."

Assuming they are all tails (0,0,0) and coins are numbered left to right 1,2,3, how can we make them all heads and still go through all combinations? Normal binary counting would have you go as shown above. But as you can see, several times 2 coins are moved. We need to move only one at a time and still get to the end result. Using the grey scale method you can change the coins as follows:

0,0,0 - Assumed Initial Start

0,1,0 - First move

0,1,1

0,0,1

1,0,1

1,0,0

1,1,0

1,1,1 - Seventh move

As shown, all combinations are made in only seven moves. No matter if there are 1, 2, or 3 heads showing you will always find all heads within seven moves. If there are any heads showing on the initial move, you will get to all heads when the reverse is gotten to in the list. As an example, lets say the coins are 0,1,0. You will get all heads on the fourth move. This happens because we assumed the initial state was all tails (0,0,0). Since we picked 0 as the initial state of all coins, a 0 means this is the initial state of the coin, whether it is a heads or tails.

The probability of success for each move is P=(N-X)/N. With N=7, we get P=(7-X)/7. With only 7 moves, each move has a 1 in seven chance of being right. But as each move eliminates a combination, the probability has to get higher, until the last move, which is a certainty.

The probabilities of each step (S) is S/7, or 1/7 for step one, 2/7 for step two, up to 7/7 for the seventh and final move.

As a side note, following the moves above, you can determine the original state of the coins. There are other solutions and order you can go through. The moves above are not in Grey Scale.

As an add to this, assume the starting condition could have all three heads, but you had to have your friend turn one over before he could say you were successfull. Now what is you strategy? What is N? what is the probability?

[Guest]

while there are clearly 7 combinations left from the 3 pennies not considering H H H (2^3-1), it appears you would need 8 [edit] moves if T T T is a valid initial condition and there is no feedback provided until after the first coin is flipped.

Edited August 14, 2009 by ogden_tbsa

[Guest]

8 moves total - after 1 move, you would have 1/7 chance of being correct, up through 6 moves yielding 6/7. The last combination would require 2 moves (not 3 as I indicated previously).

flipping coins as follows:

1, 2, 1, 3, 2, 1, 1 and 3.

Edited August 14, 2009 by ogden_tbsa

[Guest]

I think I've enumerated the possible starting values and the intermediate stages to hit the target using the following flip pattern:

1, 2, 1, 3, 1, 2, 1

This flip sequence takes every starting position to target in at most 7 flips. Also, Pr(Required flips <= 7-k) = (7-k)/7 for k = 0,1,2,3,4,5,6, empirically.

Coin

321

001

000 - 1

010 - 2

011 - 1

111 - 3

010

011 - 1

001 - 2

000 - 1

100 - 3

101 - 1

111 - 2

100

101 - 1

111 - 2

000

001 - 1

011 - 2

010 - 1

110 - 3

111 - 1

011

010 - 1

000 - 2

001 - 1

101 - 3

100 - 1

110 - 2

111 - 1

101

100 - 1

110 - 2

111 - 1

110

111 - 1

[Guest]

I think I've enumerated the possible starting values and the intermediate stages to hit the target using the following flip pattern:

1, 2, 1, 3, 1, 2, 1

This flip sequence takes every starting position to target in at most 7 flips. Also, Pr(Required flips <= 7-k) = (7-k)/7 for k = 0,1,2,3,4,5,6, empirically.

Coin

321

001

000 - 1

010 - 2

011 - 1

111 - 3

010

011 - 1

001 - 2

000 - 1

100 - 3

101 - 1

111 - 2

100

101 - 1

111 - 2

000

001 - 1

011 - 2

010 - 1

110 - 3

111 - 1

011

010 - 1

000 - 2

001 - 1

101 - 3

100 - 1

110 - 2

111 - 1

101

100 - 1

110 - 2

111 - 1

110

111 - 1

Right.

Not trying to get all tails from 1, 2, or 3 tails, but instead trying to get all heads from 1, 2, or 3 tails. Ignore my posts above.

Edited August 15, 2009 by ogden_tbsa

[Guest]

what about the starting case of 111?

111 is not a valid starting position from the OP - they are not all heads...

[Guest]

How much different would the result have been if the original question had been:

While your back is turned a friend places three coins, numbered 1, 2 and 3 on a table.

They are placed so that 1, 2, or 3 Tails are showing. That is, they are not all Heads.

Your task, without looking, is to have your friend make them all show Tails.

You do this by a series of instructions in which you identify one of the coins by number and ask him to turn it over.

After turning over the identified coin your friends tells you whether or not you have succeeded. You must first ask him to turn over a coin before you get your first response.

Because this is a finite game, success is eventually guaranteed - within say N trials.

What strategy minimizes N?

What is the minimum value of N?

What is the probability of success in (N-1) moves or fewer? (N-2) moves or fewer? ... down to 2 moves or fewer?