FOFC Puzzle Time, again

[QuikSand]

Note: I recently saw this puzzle online, so I know both its question and full solution are available somewhere, as is nearly always the case these days. I'm posting it here as a means to try to work on it myself, rather than merely uncovering the solution. My hope is that this thread can remain spoiler-free.


The story infused puzzle goes like this:

A dastardly warden offers you and your cellmate a chance to be released from prison. You have to win a game to do so.

He will create a chessboard with 64 coins on it, one in each square, turned either heads or tails. Beneath one square lies the key for your escape. There is no meta-game or data in this puzzle, apparently, so there's no other information to be had.

You get to see the board, know where the key is located, and then you get to change exactly one coin from heads to tails (or vice versa). From that information alone, your partner can then enter the room, and he gets one guess to locate the square holding the key.

What is your strategy?


Another note: the setup I just saw indicated there are two ways of setting up this puzzle, one where the initial array of H/T is random, and another assumes that the warden knows your scheme/plan and creates the pattern deliberately to frustrate you. I don't know the answer yet, so I don't know how important this is, but I'm sharing it since I am now privy to it. But since the initial setup can be purely random, I'm assuming that case as I contemplate it.

[albionmoonlight]

Clarifying question: Do you and your cellmate get to confer and devise a strategy before you see the board?

I assume yes b/c I can't see how this would work otherwise.

[QuikSand]

My quick thoughts:

-chessboard is 8x8, so it feels possible to communicate two values from 1-8 as a means to identify the key square (i.e. this game might be fundamentally different if it were a 12x12 board)

-the information we have for each square is its location (ordered 1-64, 0-63, or as a two-component system), implicitly its color or odd/even number, and the H/T of the coin upon it

-three bits of binary data (H/T, B/W, or something constructed like right/wrong, can give us exactly 8 outcomes, which feels rather convenient here

[QuikSand]

Originally Posted by albionmoonlight

Clarifying question: Do you and your cellmate get to confer and devise a strategy before you see the board?

I assume yes b/c I can't see how this would work otherwise.

I think so, and the pre-solution conversation in the solution video seems to back that up.

Here's a video short that sets it up properly, in case I abbreviated somewhere.

- YouTube

[albionmoonlight]

You can convey 64 bits of information in the first 6 squares. If you could lay out the coins yourself, that's all you'd need.

But because the board is set randomly, I don't see how flipping one coin could matter.

[QuikSand]

I am trying to find some way that a pattern emerges between the black/white and heads/tails, even if the latter is random. Like, if we say HEADS=BLACK and TAILS=WHITE and set matches as 1 and misses as 0, we create a third dimension of binary data for each square. Then we have a third dimension to get us to 2x2x2=8, which seems intuitively appealing.

[NobodyHere]

Well QuickSand you just ruined the rest of my workday because I'll be thinking of this all afternoon.

[QuikSand]

Originally Posted by albionmoonlight

You can convey 64 bits of information in the first 6 squares. If you could lay out the coins yourself, that's all you'd need.

But because the board is set randomly, I don't see how flipping one coin could matter.

Trying to think about using your coin-flip to convey where on the board to start counting to get that "six coins tell you the right spot, 1-64" outcome.

Like, let's say that spaces 20-25 happen to correlate to the right location according to the binary setup we came up with in advance (yay we got lucky). How could I inform you to look there? (That seems as hard as just telling you where the key is)

[QuikSand]

Originally Posted by NobodyHere

Well QuickSand you just ruined the rest of my workday because I'll be thinking of this all afternoon.

[NobodyHere]

And I'm going to assume the placement of the key is random, as placing it yourself would make the puzzle easy.

[QuikSand]

Lots of chessboard problems rely on the fact that there are 32 black and 32 white squares as a simplifying matter.

Like, could you cover a chessboard with 31 dominoes (that cover two orthoganally adjacent squares) if you remove the top left and bottom right squares? You can manually and visually try and try, but the shortcut is NO because these are both white squares and every domino must by definition cover one black and one white square. You hear that and you stop thinking about it, it's fully solved even if you can't explain the math behind it.

I feel like there's something here that might work similarly. Like some combination of stuff inevitably yields an odd or even number, and we can spot that aggregated info to see where it got corrupted by your one coin flip and that outcome has 64 possible variations.

But that's just a loose strand...

[QuikSand]

Originally Posted by NobodyHere

And I'm going to assume the placement of the key is random, as placing it yourself would make the puzzle easy.

I think the setup is that it is either random, or decided maliciously by the warden, but in either case this isn't a slam dunk puzzle of we just tell our cellmate where it's going to be.

We form our strategy without knowing where the key will be located, nor what the array of H/T will look like.

[albionmoonlight]

Still just brainstorming.

Take Q's idea of a "match" between color and H/T is worth a hit.

Then say each row is worth different points. So a hit on row 1 is worth 1, a hit on row 2 is worth 2, etc. all the way down to row 8.

Is there some way that we could manipulate one coin to guarantee any number we want?

[QuikSand]

Okay, lots of puzzles can be solved by starting with an extreme case, and then working one step at a time toward the generic solution.

Say the key lies at position 3,3 or square number 19 of 64.

Say the entire board is covered with HEADS.

The most obvious ways to communicate 19 to our partner seem to be:

-flip the coin at 19
-flip the coin at 46, the counterpart space starting from the reverse (i like this somehow)

...and anything else but that seems random to me.

If we count H=1 then communicating a 19 in a sequence requires TTTHTTHH and there's no way to construct that anywhere contiguously on the board from one coin flip. Even with my overlay of HT and BW we still can't get that pattern anywhere contiguous with one coin flip.

[QuikSand]

I have a lunch meeting, so will be dipping shortly. Sorry in advance.

[albionmoonlight]

Maybe a brute force approach:

The entire board contains 2^64 bits of information. We need only to communicate which of 64 squares contains the key.

Could we make 64 lists of numbers such that each list cooresponds to one square and we could manipulate the board to make it possible to get to any list by altering one coin?

That seems too inelegant for a puzzle like this. And I'm not sure that it's really practical in any sense to be dealing with 2^64 numbers as part of a solution.

[cuervo72]

* looks at problem *

"Fuck, I don't have the time/brain cycles for this. I'll just seek out the answer."

* begins watching video with answer *

"Fuck, I don't have the time/brain cycles for this."

[NobodyHere]

Yeah, I can get about a 75% success rate with just one flip. With 2 I could get 100%.

[albionmoonlight]

What's your approach to get 75%?

[NobodyHere]

Originally Posted by albionmoonlight

What's your approach to get 75%?

My method:

Spoiler

Step 1. Number each square on the board 0 - 63 (first square 0, second square 1 etc...
Step 2. For each head, add its square number to a running total.
Step 3. Mod this total by 64.
Step 4. Use your coin flip to add or subtract from this number and mod 64 to get the square number the key is hidden under.

This second person can then just run the same math and get the square the key is under.

There will be two possible squares you can use to get to your target number (one you can add and one you can subtract. Each of which has a 50% chance of being valid. This is why I say 75% chance.

Now I need to go get some work done...

[QuikSand]

I feel like there has to be a conditional of some sort... but I can't isolate it.

What if the rule was: look at the first row of H/T and count the heads. If it's even, leave it, and look at the heads count of the next row. When you get to the first row that has an ODD number of heads, you flip the coin in the column corresponding to the key location.

Yeah that sucks in specifics, but work with me on the generals... some sort of IF/THEN here seems to be the way to tell the person what you saw initially, and that guided you to make the certain change that you did.

[albionmoonlight]

Originally Posted by NobodyHere

My method:

Spoiler

Step 1. Number each square on the board 0 - 63 (first square 0, second square 1 etc...
Step 2. For each head, add its square number to a running total.
Step 3. Mod this total by 64.
Step 4. Use your coin flip to add or subtract from this number and mod 64 to get the square number the key is hidden under.

This second person can then just run the same math and get the square the key is under.

There will be two possible squares you can use to get to your target number (one you can add and one you can subtract. Each of which has a 50% chance of being valid. This is why I say 75% chance.

Now I need to go get some work done...

Spoiler

the Mod(64) seems like the needed breakthrough here

[albionmoonlight]

Any new thoughts?

I think that NobodyHere's approach is the right way to go. Just can't finish it out

[QuikSand]

same here

[AnalBumCover]

Instead of looking at the board as Rows and Columns, or 64 individual squares, what about looking at it as 4 quadrants? And within each quadrant, another level of quadrants.

[AlexB]

Assuming the layout is as per the video with all heads & tails nicely aligned, why not just flip the coin over the key and replace it ‘upside down’ so that it stood out against the rest.

It’s probably not what the puzzle intends, but it doesn’t seem explicitly against the rules!

[Toddzilla]

I've been trying to work this out and figure out a way one could communicate using only the side of a coin and came up with this, no idea how scalable it is, but it may be a start.

Assume you only have 2 squares, then the position of the first coin tells you where the key is - heads means it's under the first square, tails means it's under the second square. The state of the second coin is irrelevant.

Now thinking of a 2x2 grid, you'd need a way to indicate both the column and row of the key by moving only one coin. In this case, the state of the other coins matters, since you can't pass 2 pieces of info with one coin. So essentially the coin you are going to move doesn't matter, it's the state of all 4 coins that tells you where the key is.

Consider heads = 1 and tails = 0, taking the coins in order left-to-right and top-to-bottom, you have 16 different numbers (0000 or all tails is 0, 0001 = 1, 0010 = 2, 1101 = 13, you get the idea) and you assign numbers to the squares like this:

Top left = 0,4,8,12, Top right = 1,5,9,13, Bottom left = 2,6,10,14, Bottom right = 3,7,11,15

You know where the coin is, you know what number 0-15 represents the square with the key, you just need to flip over the one coin that changes the 4-digit binary number to the desired result.

For example:

The board looks like this:

H H
T T

and the key is under the 3rd square (bottom left).

HHTT = 1100 = 12 and the bottom left is represented by 2,6,10, and 14.

so you'd need to flip over one coin to get to either:

2 (TTHT)
6 (THHT)
10 (HTHT) or
14 (HHHT)

in this case, we flip over the coin on square 3 resulting in

H H
H T

or HHHT = 1110 = 14 = key is under square 3, bottom left.

Now I'll leave it as an exercise to the reader to expand this to an 8x8 grid.

[Toddzilla]

Spoiler

I emailed my PhD advisor today and she let me know that, indeed, the solution scales, however it's decidedly not the easiest way - basically, good luck calculating a 64-digit binary number (in prison).

[Toddzilla]

I'm sorry I killed the thread.

[albionmoonlight]

I looked up the answer.

We were on the right track, but there was one trick we were missing.

I am confident that I would have never figured it out without looking it up

[korme]

Originally Posted by albionmoonlight

I looked up the answer.

We were on the right track, but there was one trick we were missing.

I am confident that I would have never figured it out without looking it up

So you're saying we are 2/3 of the way there

[Toddzilla]

There's a very quick algorithm to solving the puzzle in seconds, trying to wrap my head around why it works