Coin hunt

[plasmid]

I have a rare coin that’s worth a bazillion dollars and I’ll give you and a buddy a chance to win it.

I’ll bring you (but not your buddy yet) into a room where I have a bunch of coins lined up in a row, probably randomly distributed between being heads up and tails up, and I’ll tell you which coin among those is the bazillion dollar coin. Then you’ll exit the room and your buddy will come in through another entrance (so you can’t communicate after I tell you which is the bazillion dollar coin) and tell me which coin to give to the two of you.

That wouldn't be a very fair game, so you can also tell me to flip whichever coins you want before you leave the room and your buddy comes in. (I’m flipping them myself to make sure you don’t send codes with subtle placement of the coins or such tomfoolery.) But you have to watch 10 minutes of Nyan Cat for every coin I flip so you want to minimize the number of flips lest you go insane. I’m not saying beforehand how many coins will be in the room, and you only get one minute to tell your buddy a strategy (just words that can be spoken in under a minute, no written cheat sheets) before it’s time to play the game.

Clock starts now.

(I would credit the source of where I heard the original form of this puzzle that I'm modifying, but I can't remember the source any more.)

[plasmid]

On 4/30/2018 at 11:40 AM, ThunderCloud said:

 

I am not sure if this works for every case, or if I might be misunderstanding the scheme. For a simple counter-example…

  Reveal hidden contents

Consider a case with 5 coins. Suppose their initial orientation is H H H T H, and that the first coin is the special one. Let H = 1 and T = 0, and number the coins from 1 to 5.

 

Then we should have three "parity" coins: coin 1 is the sum (mod 2) of coins 1, 3, and 5; coin 2 is the sum of coins 2 and 3; coin 4 is the sum of coins 4 and 5. In this example, both coin 2 and 4 have "wrong" parity, and because each sums parity over a completely disjoint set of coins, it will take 2 coin flips to correct the parity — namely coins 3 and 5. But then, if coins 3 and 5 are Tails, all three of the parity coins (1, 2, 4) will be correct regardless of which way they face. How to specify that coin #1 is worth gajillions?

 

Spoiler

After re-reading, I probably misunderstood what plainglazed was saying. I interpreted it as being equivalent to setting things up so the buddy would list all the coins that are heads-up, write out their position in binary, and then take the XOR of all of those binary numbers to see which coin to take. If that were the case, then handling the scenario H H H T H, you would see heads up on coins

1: 001
2: 010
3: 011
5: 101

So the XOR of those would be 101, or 5. You want the XOR to be 1, or 001. So flip coin 4. You would have all of the coins heads-up, the XOR of 001 through 101 would be 001, and your buddy would know to take the first coin. But now I think plainglazed wasn't quite saying that.

 

[harey]

I found a strategy, but far from sure it is optimal.
 

Spoiler

 

Divide the coins from left to right as 'pointer' and 'data' so that the 'pointer' is just large enough to access all 'data'. (Example with 17 coins: 4 coins are pointer, necessary to address 13 coins of data. With a pointer of 3 coins, we could not address the remaining 14 coins of data.)

What if the rare coin is within the 'pointer'? We can solve it this way:
Count the number of heads:
- if it is even, the pointer solution apply
- if it is odd, take the first head from left.

 

 

[bonanova]

Thinking. Meantime I'll call your 10 minutes of cat flight and raise you 25 minutes of Roomfull of Teeth, as they explore new uses for the human voice, which you might actually enjoy.

[aiemdao]

to number coins from 0 to n-1

Convert number of bazillion coin to binary with head is 1, tale is 0

So need to flip: log(2,n) or Int(log(2,n)) +1

[plasmid]

It looks like harey and aiemdao have sort of similar strategies, and that the number of coins flipped would be up to log base 2 of the total number of coins. With harey's answer it could be less for certain numbers of coins in play, but not for all.

But if there are more than even a mere 32 coins, then you could be in for up to a solid hour of nyan-ing which might not be worth a bazillion bucks. Try for an approach with less, especially when the number of coins gets large.

[bonanova]

I can ask you to flip a coin for a 2^nd time?

[plasmid]

3 hours ago, bonanova said:

I can ask you to flip a coin for a 2^nd time?

Flipping the same coin twice would be indistinguishable from not flipping it at all to your buddy. So you would just be exposing yourself to more nyaning without accomplishing anything.

[bonanova]

13 hours ago, plasmid said:

Flipping the same coin twice would be indistinguishable from not flipping it at all to your buddy. So you would just be exposing yourself to more nyaning without accomplishing anything.

Naively.I might want the first n-1 coins to be heads if the valuable one was tails in the nth position. I'd have you keep flipping them until they showed heads. But /// I watched the video, so ... nah.

[CaptainEd]

Fuzzy thoughts:

Display the coded location on the further  end of the line of coins.

count random walk zeroes: H = +1, T = -1.

display as HH...T, replacing ... with n H, to refer to the coin right AFTER the nth zero. If the first card is bazillion, HHT, if the third card is right after the zero, HHHT.

display as TT...H, similarly, if it is the card just BEFORE the nth zero.

Make sure to change the near end to HT or TH, whichever is cheaper, so your buddy knows how to tell which end has the coding.

Finally, you may need to tweak a few coins to put a zero adjacent to the bazillion coin.

 

[jordancollins]

And what exactly coin do you have? 

[plasmid]

This one

[harey]

What about a hint?

[plasmid]

4 hours ago, harey said:

What about a hint?

Ok.

Spoiler

The technique that I know of has a small upper limit of how many coins you would ever need to flip, regardless of how many coins there are to choose from. You could always get the bazillion dollar coin with much less than an hour of nyan-ing.

 

[Molly Mae]

You could represent the bazillion dollar coin as a binary number using the first 10 coins.  That covers the 2

¹⁰ possibilities.  You can make it more efficient by using the 11th bit to define whether heads is 0 or 1.  This saves flips in the event that you need to flip more than half of the coins to make the correct binary number.  Depending on the number of coins, you could extend or reduce the amount of bits you use by using the fewest bits that can represent the highest possible number.

[plainglazed]

Spoiler

Flip coins to make the bazillion coin the center of the longest string of the same value (heads or tails).  Would expect about nine consecutive heads or tails would be enough to be both easily spotted and not take very many flips.  At some point it could make more sense to break up other existing long strings vs adding to the indicating string.  The downfall of this strategy is if the valuable coin is near either end, but you could strategize to flip the first or last coin to heads if the money coin is in the say first eight coins and the next three coins then tell at what position taking at most five flips, otherwise flip (if necessary) the first and last coins to tails.

 

[plasmid]

On 3/14/2018 at 9:09 AM, Molly Mae said:

 

  Hide contents

You could represent the bazillion dollar coin as a binary number using the first 10 coins.  That covers the 2

¹⁰ possibilities.  You can make it more efficient by using the 11th bit to define whether heads is 0 or 1.  This saves flips in the event that you need to flip more than half of the coins to make the correct binary number.  Depending on the number of coins, you could extend or reduce the amount of bits you use by using the fewest bits that can represent the highest possible number.

 

So if you have N coins to choose from, instead of needing log₂N coins to specify its position you can guarantee that you only need (log₂N / 2) + 1 flips. Nice move to halve the upper limit, but with 1000 coins you could still be in for an hour of nyan.

On 3/15/2018 at 4:54 AM, plainglazed said:

  Hide contents

Flip coins to make the bazillion coin the center of the longest string of the same value (heads or tails).  Would expect about nine consecutive heads or tails would be enough to be both easily spotted and not take very many flips.  At some point it could make more sense to break up other existing long strings vs adding to the indicating string.  The downfall of this strategy is if the valuable coin is near either end, but you could strategize to flip the first or last coin to heads if the money coin is in the say first eight coins and the next three coins then tell at what position taking at most five flips, otherwise flip (if necessary) the first and last coins to tails.

 

That might work well for random configurations ... the math to figure out how many flips it would take on average would be difficult and maybe worth being its own question. But the worst case scenario if the bazillion coin is in the middle, the left half is all heads, and the right half is all tails would be a real pain.

[plasmid]

I know of a way to do this while flipping no more than two coins. And a hint:

Spoiler

If the total number of coins in play is a power of 2, I know how to do it with a single coin flip.

 

[plainglazed]

Been extremely interested in this one plasmid my friend, and for the longest time thought the above post must be a mistake.  Now think am on to you.  Just need to figure out how to simply explain the solution if indeed my most recent process pans out.  Just wanted to let you know am still on the case.  Know it can be frustrating when a thread goes on without response, especially when it's a fine puzzle such as this one.  I'll be back...

[plainglazed]

an attempt at an explanation by example

Spoiler

Let's say there are twenty four coins.  Label 0 for tails and 1 for heads.  Thus a string of twenty four ones and zeros describes

the coins in play.  Let's also say the tenth coin is the money coin.  So something like this:

   H H T H T T T H T T H H H H T H T H T T H T H T
   1 1 O 1 O O O 1 O O 1 1 1 1 O 1 0 1 0 0 1 0 1 0
 

Listing each coin position in binary and corresponding coin value:

      1 - 1(heads)
    10 - 1
    11 - 0
   100 - 1
   101 - 0
   110 - 0
   111 - 0
  1000 - 1
  1001 - 0
  1010 - 0
  1011 - 1
  1100 - 1
  1101 - 1
  1110 - 1
  1111 - 0
 10000 - 1
 10001 - 0
 10010 - 1
 10011 - 0
 10100 - 0
 10101 - 1
 10110 - 0
 10111 - 1
 11000 - 0

We use the bit positions that are powers of two as parity checks to our string of coins.

Define the parity at bit position 1 as the sum mod 2 of all bits that are in positions where the least significant digit of that

position in binary is a one (the ones column if you will).  Thus the sum mod 2 of the bits in positions 1,3,5,7,9,etc.  In our

case that is (1+0+0+0+0+1+1+0+0+0+1+1)mod2=1

Define the parity at bit position 2 as the sum mod 2 of all bits that are in positions where the second least significant digit

of that posistion in binary is a one (the twos column).  Thus the sum mod 2 of the bits in positions 2,3,6,7,10,11,etc.  In our

case that is (1+0+0+0+0+1+1+0+0+1+1+0)mod2=1

Define the parity at bit position 4 as the sum mod 2 of all bits that are in positions where the third least significant digit of

that position in binary is a one (the fours column).  Thus the sum mod 2 of the bits in positions 4-7,12-15,20-23,etc.  In our

case that is (1+0+0+0+1+1+1+0+0+1+0+1)mod2=0

The parity at position 8 is the sum mod 2 of the bits in positions 8–15,24–31,40–47,etc.  In our case that is

(1+0+0+1+1+1+1+0+0)mod2=1

The parity at position 16 is the sum mod 2 of the bits in positions 16–31,48–63,80–95,etc.  In our case that is

(1+0+1+0+0+1+0+1+0)mod2=0

etc.

The values (heads or tails) at bit positions that are powers of two (positions 1,2,4,8,16) are 1,1,1,1,1

And we've calculated the parity at bit positions that are powers of two to be 1,1,0,1,0

The bits at positions 4 and 16 of the calculated parity do not match the actual bit value of our coins in those positions.  But

if we flip the coin at position 10100 and recalculate the parity, it matches the value of our coins.

Now if we flip the money coin, our partner can calculate the parity at positions 1,2,4,8,16 and see that bit values do not match

at positions 2 and 8 and know the money coin is at position ten.

If the total number of coins is a power of two, the steps of making the calculated parity match the actual bit values and then

flipping the money coin can be combined into one flip.

For a better explanation wiki Hamming Code

 

 

[plasmid]

2 hours ago, plainglazed said:

an attempt at an explanation by example

  Reveal hidden contents

Let's say there are twenty four coins.  Label 0 for tails and 1 for heads.  Thus a string of twenty four ones and zeros describes

the coins in play.  Let's also say the tenth coin is the money coin.  So something like this:

   H H T H T T T H T T H H H H T H T H T T H T H T
   1 1 O 1 O O O 1 O O 1 1 1 1 O 1 0 1 0 0 1 0 1 0
 

Listing each coin position in binary and corresponding coin value:

      1 - 1(heads)
    10 - 1
    11 - 0
   100 - 1
   101 - 0
   110 - 0
   111 - 0
  1000 - 1
  1001 - 0
  1010 - 0
  1011 - 1
  1100 - 1
  1101 - 1
  1110 - 1
  1111 - 0
 10000 - 1
 10001 - 0
 10010 - 1
 10011 - 0
 10100 - 0
 10101 - 1
 10110 - 0
 10111 - 1
 11000 - 0

We use the bit positions that are powers of two as parity checks to our string of coins.

Define the parity at bit position 1 as the sum mod 2 of all bits that are in positions where the least significant digit of that

position in binary is a one (the ones column if you will).  Thus the sum mod 2 of the bits in positions 1,3,5,7,9,etc.  In our

case that is (1+0+0+0+0+1+1+0+0+0+1+1)mod2=1

Define the parity at bit position 2 as the sum mod 2 of all bits that are in positions where the second least significant digit

of that posistion in binary is a one (the twos column).  Thus the sum mod 2 of the bits in positions 2,3,6,7,10,11,etc.  In our

case that is (1+0+0+0+0+1+1+0+0+1+1+0)mod2=1

Define the parity at bit position 4 as the sum mod 2 of all bits that are in positions where the third least significant digit of

that position in binary is a one (the fours column).  Thus the sum mod 2 of the bits in positions 4-7,12-15,20-23,etc.  In our

case that is (1+0+0+0+1+1+1+0+0+1+0+1)mod2=0

The parity at position 8 is the sum mod 2 of the bits in positions 8–15,24–31,40–47,etc.  In our case that is

(1+0+0+1+1+1+1+0+0)mod2=1

The parity at position 16 is the sum mod 2 of the bits in positions 16–31,48–63,80–95,etc.  In our case that is

(1+0+1+0+0+1+0+1+0)mod2=0

etc.

The values (heads or tails) at bit positions that are powers of two (positions 1,2,4,8,16) are 1,1,1,1,1

And we've calculated the parity at bit positions that are powers of two to be 1,1,0,1,0

The bits at positions 4 and 16 of the calculated parity do not match the actual bit value of our coins in those positions.  But

if we flip the coin at position 10100 and recalculate the parity, it matches the value of our coins.

Now if we flip the money coin, our partner can calculate the parity at positions 1,2,4,8,16 and see that bit values do not match

at positions 2 and 8 and know the money coin is at position ten.

If the total number of coins is a power of two, the steps of making the calculated parity match the actual bit values and then

flipping the money coin can be combined into one flip.

For a better explanation wiki Hamming Code

 

 

That looks like it nailed it, PG! As for a way of saying it in under a minute...

Spoiler

... use the binary operator XOR

 

[CaptainEd]

Amazing!

[flamebirde]

That's a beautiful solution.

[ThunderCloud]

On 4/19/2018 at 8:36 AM, plainglazed said:

an attempt at an explanation by example

  Hide contents

Let's say there are twenty four coins.  Label 0 for tails and 1 for heads.  Thus a string of twenty four ones and zeros describes

the coins in play.  Let's also say the tenth coin is the money coin.  So something like this:

   H H T H T T T H T T H H H H T H T H T T H T H T
   1 1 O 1 O O O 1 O O 1 1 1 1 O 1 0 1 0 0 1 0 1 0
 

Listing each coin position in binary and corresponding coin value:

      1 - 1(heads)
    10 - 1
    11 - 0
   100 - 1
   101 - 0
   110 - 0
   111 - 0
  1000 - 1
  1001 - 0
  1010 - 0
  1011 - 1
  1100 - 1
  1101 - 1
  1110 - 1
  1111 - 0
 10000 - 1
 10001 - 0
 10010 - 1
 10011 - 0
 10100 - 0
 10101 - 1
 10110 - 0
 10111 - 1
 11000 - 0

We use the bit positions that are powers of two as parity checks to our string of coins.

Define the parity at bit position 1 as the sum mod 2 of all bits that are in positions where the least significant digit of that

position in binary is a one (the ones column if you will).  Thus the sum mod 2 of the bits in positions 1,3,5,7,9,etc.  In our

case that is (1+0+0+0+0+1+1+0+0+0+1+1)mod2=1

Define the parity at bit position 2 as the sum mod 2 of all bits that are in positions where the second least significant digit

of that posistion in binary is a one (the twos column).  Thus the sum mod 2 of the bits in positions 2,3,6,7,10,11,etc.  In our

case that is (1+0+0+0+0+1+1+0+0+1+1+0)mod2=1

Define the parity at bit position 4 as the sum mod 2 of all bits that are in positions where the third least significant digit of

that position in binary is a one (the fours column).  Thus the sum mod 2 of the bits in positions 4-7,12-15,20-23,etc.  In our

case that is (1+0+0+0+1+1+1+0+0+1+0+1)mod2=0

The parity at position 8 is the sum mod 2 of the bits in positions 8–15,24–31,40–47,etc.  In our case that is

(1+0+0+1+1+1+1+0+0)mod2=1

The parity at position 16 is the sum mod 2 of the bits in positions 16–31,48–63,80–95,etc.  In our case that is

(1+0+1+0+0+1+0+1+0)mod2=0

etc.

The values (heads or tails) at bit positions that are powers of two (positions 1,2,4,8,16) are 1,1,1,1,1

And we've calculated the parity at bit positions that are powers of two to be 1,1,0,1,0

The bits at positions 4 and 16 of the calculated parity do not match the actual bit value of our coins in those positions.  But

if we flip the coin at position 10100 and recalculate the parity, it matches the value of our coins.

Now if we flip the money coin, our partner can calculate the parity at positions 1,2,4,8,16 and see that bit values do not match

at positions 2 and 8 and know the money coin is at position ten.

If the total number of coins is a power of two, the steps of making the calculated parity match the actual bit values and then

flipping the money coin can be combined into one flip.

For a better explanation wiki Hamming Code

 

 

I am not sure if this works for every case, or if I might be misunderstanding the scheme. For a simple counter-example…

Spoiler

Consider a case with 5 coins. Suppose their initial orientation is H H H T H, and that the first coin is the special one. Let H = 1 and T = 0, and number the coins from 1 to 5.

 

Then we should have three "parity" coins: coin 1 is the sum (mod 2) of coins 1, 3, and 5; coin 2 is the sum of coins 2 and 3; coin 4 is the sum of coins 4 and 5. In this example, both coin 2 and 4 have "wrong" parity, and because each sums parity over a completely disjoint set of coins, it will take 2 coin flips to correct the parity — namely coins 3 and 5. But then, if coins 3 and 5 are Tails, all three of the parity coins (1, 2, 4) will be correct regardless of which way they face. How to specify that coin #1 is worth gajillions?

 

[ThunderCloud]

On 5/3/2018 at 9:22 PM, plasmid said:

  Reveal hidden contents

After re-reading, I probably misunderstood what plainglazed was saying. I interpreted it as being equivalent to setting things up so the buddy would list all the coins that are heads-up, write out their position in binary, and then take the XOR of all of those binary numbers to see which coin to take. If that were the case, then handling the scenario H H H T H, you would see heads up on coins

1: 001
2: 010
3: 011
5: 101

So the XOR of those would be 101, or 5. You want the XOR to be 1, or 001. So flip coin 4. You would have all of the coins heads-up, the XOR of 001 through 101 would be 001, and your buddy would know to take the first coin. But now I think plainglazed wasn't quite saying that.

 

Wow… I love it! This is one of the best puzzles I've ever seen, thank you for sharing it, and for clarifying the solution. ^.^