The coolest checkerboard magic trick. Version 2

Question

Version 1: The coolest checkerboard magic trick

You and your friend are imprisoned. Your jailer offers a challenge. If you complete the challenge you are both free to go. The rules are

The jailer will take you into a private cell. In the cell will be a triangular chessboard and a jar containing 100 coins.

The jailer will take the coins, one-by-one, and place a coin on each triangle on the board. He will place the coins randomly on the board. Some coins will be heads, and some tails (or maybe they will be all heads, or all tails; you have no idea. It's all at the jailers whim. He may elect to look and choose to make a pattern himself, he may toss them placing them the way they land, he might look at them as he places them, he might not …). If you attempt to interfere with the placing of the coins, it is instant death for you. If you attempt to coerce, suggest, or persuade the jailer in any way, instant death. All you can do it watch.

Once all the coins have been laid out, the jailer will point to one of the triangles on the board and say: “This one!” He is indicating the magic triangle. This triangle is the key to your freedom.

The jailer will then allow you to turn over one coin on the board. Just one. A single coin, but it can be any coin, you have full choice. If the coin you select is a head, it will flip to a tail. If it is a tail it will flip to a head. This is the only change you are allowed to make to the jailers initial layout. You will then be lead out of the room. If you attempt to leave other messages behind, or clues for your friend … yes, you guessed it, instant death!

The jailer will then bring your friend into the room. Your friend will look at the board (no touching allowed), then examine the board of coins and decide which location he thinks is the magic triangle. He gets one chance only (no feedback). Based on the configuration of the coins he will point to one triangle and say: “This one!” If he guesses correctly, you are both pardoned, and instantly set free. If he guesses incorrectly, you are both executed.

The jailer explains all these rules, to both you and your friend, beforehand and then gives you time to confer with each other to devise a strategy for which coin to flip.

What strategy would you use to escape?

Answer 1

I don't think it's possible to escape 100% of the time. The best strategy (I think) is this:

Tell your friend to pick the head that is highest up (closest to the peak of the pyramid) and most to the left (These directions can be chosen arbitrarily). If there are no heads, tell him to pick the bottom right triangle.

When you are in the room:

1. If the magic triangle is a tail and there are no heads 'before' it (to the left or above), flip it. 2. If it is already a head, and there are no other heads 'before' it (above or to the left), flip a coin 'after' it (to the right or below). If this is the bottom right coin and there are no coins after it, flip the only head. Your friend will know what to do. 3. If it is already a head, and there is only one other head that is 'before' it (to the left or above), flip that to a tail.

If none of these situations apply, you are basically dead already.

This strategy will double your chances of surviving from 1/100 (if you play randomly) to about 1/50, I think.

To try to prove this, let's rearange the coins in a line, in order to make it easier to think about them. The order is the same as if you would read a book: the top coin is first, then the the next line, starting from leftmost coin. Let us number the coins from 1 to 100.

• If the first triangle is magic, you win no matter what, because of the strategy (you may check). Probability of this happening: 1/100
• If any other triangle is magic, you win only if:
  • The magic triangle is a head and there are no more than 1 heads preceding it. Probability of this happening: (1/2) * ((1/2)^(n-1) + (1/2)^(n-1)*(n-1)), where n is the coin number
  • The magic triangle is a tail and there are no heads preceding it. P = (1/2)*(1/2)^(n-1)

So the probability that you survive is:

(Which is twice as big as the probability you survive from a random guess.)

Answer 2

I wasn't going to put this in because it is obvious and I'm sure there are better answers, but the two answers so far give such a woeful chance of success that I thought I would provide my own.

Assumption: there is a known "top" to the board. You and your friend automatically can tell where the top of the board is based on cues in the room. Where the door is for example. If this is not possible (i.e. the board is randomly rotated before your friend enters) then we need a different strategy.

You

Once the board is laid out and the jailer indicates the magic triangle, mentally flip this coin in your head; for all the calculations below, you will pretend that the coin on the magic triangle actually has the opposite value.

Now, take the first 64 squares starting at the top of the board working top to bottom, left to right. Map these to an 8x8 checker board. If the magic triangle is not in this set, start at bottom of the board instead taking the last 64 triangles.

Now solve the problem based on this well received answer. Basically compute the parity of all sections of the board and find the one square which when flipped makes all the parities 0. Call this square the target square. Since we are pretending that the magic square is flipped, we know that if the target square and the magic square are flipped, all the groupings will have a 0 parity. So by flipping the target square but not the magic square, your friend can compute the same parity and deduce which square when flipped will get back to 0 parity for all groups; this will be the magic square.

Back to the task at hand, you can now easily identify which triangle was mapped to the target square and this is the coin that you will flip.

Your Friend

Your friend comes into the room and sees the board. He now has to make a choice; either take the first 64 triangles and map them to an 8x8 checker board, or take the last 64 triangles. If he guesses the same set that you chose, then he will create the same 8x8 checker board that you did. He will then compute the parity of all the groupings and identify the square that will make all the groups have 0 parity. Once mapped back to to the triangular board, he will make his selection.

Survival Chance

Since an 8x8 checker board can guarantee 100% survival, we know that if your friend picks correctly, you will survive. If he doesn't, you will die. Your friend has a 50% chance of picking correctly, so you have a 50% chance of survival.

Rotated Board

One of the assumptions was you and your friend know the top of the board. If the board is randomly rotated, then you can achieve 33% by picking the first 64 squares using one of the 3 vertices as the top. If your friend picks the same vertex, you will survive. Otherwise, death.

Thus, your survival chance is 33%.

Conclusion

I didn't originally post this as an answer because I assumed a guaranteed method of survival was available. Judging by the responses so far, this is a better answer, but still far from perfect. For example, since there are 100 triangles, 64 is more than half. Can we use this in some way? What if the magic square is valid for both orientations? Is there some way we can use this information?

I haven't attempted to look into these questions yet but may do so later.

Answer 3

Seems there is still no real good answer on this question. There is indeed no 100% chance. I am not sure 'my' strategy is the best, but I think it is relatively easy and pretty successful.

Preparation:
1 Make sure that the top of the triangle is clear, and that the warden cannot hear your strategy so the chances remain random
2 Do the chessboard trick mentioned (for 128 i.s.o. 64 fields):
1 Number the triangles from 1 to 100 (e.g. top to bottom left to right)
2 Do a bitwise xor of all triangles with a head
3 Xor this with number (n) of the magic triangle The resulting value is a random number 0-127

- If 1-100 toggle that number (you will be free)
- If 0 take no action (you will be free)
Else
Since you could not 'make' n try the 'backup'
- n>28: no backup
- else: backup = n+100
- xor n (to reset), xor n+100
- if result 1-100 toggle result (you will be free)
- if result 0 take no action (you will be free)
The backup result is 0-100 with chance 101/127 (since the original mapped wrong)

Choice:
- Number the triangles from 1 to 100 as discussed/done in preparation
- Do a bitwise xor of all triangles with a head
The resulting value is a random number 0-127
- If 1-100 choose the triangle with that number (101/128 chance)
else choose the triangle n-100
Chance of escape: 101/128 + 27/128(chance backup needed)*28%(chance backup available)*101/127(chance backup successful) (+/- 83.6% )
Note: By toggling n, 'unsolvable' distributions can be mapped to values >100. So if you do not like dying, and if the jailor allows it, you could decline playing such values and remain imprisoned instead of dying (but escape chance than drops to 101/128).

Answer 4

Okay, I've thought about it and I believe that

It is not possible.
Consider a graph with $2^{100}$ nodes (these are the possible states of the board). Draw an edge between two nodes if it possible to get from one to the other by flipping a coin (This is a 100-cube, in a way). Now, we want to colour the vertices of this graph in 100 colours such that, given any node, there exists an adjacent node of each colour (that's pretty much the question, where each colour is a square). I'll expand on this in the note below. So for any colour $i$, there exist $2^{100}$ ordered (node, node) pairs where the first node has colour $i$. But, there exists a colour such that there are strictly less than $2^{100}/100$ nodes of that colour (since 100 is not a factor of $2^{100}$. Therefore there are strictly less than $2^{100}/100*100=2^{100}$ (node, node) ordered pairs where the first node has that colour, a contradiction.]

Note: Okay, re-reading what I wrote, it makes practically no sense at all. I'll see if I can fix it

Basically a node is coloured colour $i$ if, when your friend sees the board at that node, then they choose the $i$th square on the board. This should clarify things up a bit. And, with Jan Ivan's comment, instead of needing at least one of each colour in just the adjacent nodes, it needs of of each colour in either the adjacent nodes or itself. This seems more possible, but even if I come up with a situation which works, I wouldn't be able to translate that into an easily memorisable plan for you and your friend...