[math-fun] Mensa Correctional Facility
There’s a growing class of puzzles I call Mensa Correctional Facility puzzles. In these puzzles there is always a warden who challenges prisoners with math/logic puzzles and grants them freedom when they succeed in solving them. Does anyone know the origins of the following one: In this puzzle the warden challenges a pair of Mensa inmates. The first inmate is shown to the warden’s room and the warden proceeds to place identical coins, each one either heads up or tails up, onto the 64 squares of a checkerboard. He then points to one of the coins and declares it to be the “freedom coin”. The inmate watching this is then invited to flip one of the coins to help his partner identify the freedom coin. Then, without allowing the inmates to communicate with each other, the second inmate is lead into the room, shown the coins, and after a little head scratching points to the freedom coin — he is, after all, a Mensa inmate — and the prisoners are set free. How did they do it? -Veit
I first heard it last year from a coworker who likes such puzzles, but the setup was slightly different: the warden allows the two to agree on a strategy in his presence first; then one of them leaves; then the warden is free to place the coins in whatever way he pleases and choose any coin as the freedom coin. Then the other prisoner leaves, the first one comes back, and has to make his choice. On Wed, Apr 15, 2015 at 12:55 PM, Veit Elser <ve10@cornell.edu> wrote:
There's a growing class of puzzles I call Mensa Correctional Facility puzzles. In these puzzles there is always a warden who challenges prisoners with math/logic puzzles and grants them freedom when they succeed in solving them. Does anyone know the origins of the following one:
In this puzzle the warden challenges a pair of Mensa inmates. The first inmate is shown to the warden's room and the warden proceeds to place identical coins, each one either heads up or tails up, onto the 64 squares of a checkerboard. He then points to one of the coins and declares it to be the "freedom coin". The inmate watching this is then invited to flip one of the coins to help his partner identify the freedom coin. Then, without allowing the inmates to communicate with each other, the second inmate is lead into the room, shown the coins, and after a little head scratching points to the freedom coin -- he is, after all, a Mensa inmate -- and the prisoners are set free.
How did they do it?
-Veit _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Mike Stay - metaweta@gmail.com http://www.cs.auckland.ac.nz/~mike http://reperiendi.wordpress.com
This puzzle, and related ones, seem to be coming up a lot. It was performed (with 16 replacing 64) at a recreational math conference I recently attended in Portugal earlier this year. I was also told about it at the last Gathering 4 Gardner in Atlanta (spring 2014). The person who showed it to me first was Colin Wright I think (cc'ed), who might be able to say where he heard about it (if he didn't make it up himself). On Wed, Apr 15, 2015 at 1:04 PM, Mike Stay <metaweta@gmail.com> wrote:
I first heard it last year from a coworker who likes such puzzles, but the setup was slightly different: the warden allows the two to agree on a strategy in his presence first; then one of them leaves; then the warden is free to place the coins in whatever way he pleases and choose any coin as the freedom coin. Then the other prisoner leaves, the first one comes back, and has to make his choice.
On Wed, Apr 15, 2015 at 12:55 PM, Veit Elser <ve10@cornell.edu> wrote:
There's a growing class of puzzles I call Mensa Correctional Facility puzzles. In these puzzles there is always a warden who challenges prisoners with math/logic puzzles and grants them freedom when they succeed in solving them. Does anyone know the origins of the following one:
In this puzzle the warden challenges a pair of Mensa inmates. The first inmate is shown to the warden's room and the warden proceeds to place identical coins, each one either heads up or tails up, onto the 64 squares of a checkerboard. He then points to one of the coins and declares it to be the "freedom coin". The inmate watching this is then invited to flip one of the coins to help his partner identify the freedom coin. Then, without allowing the inmates to communicate with each other, the second inmate is lead into the room, shown the coins, and after a little head scratching points to the freedom coin -- he is, after all, a Mensa inmate -- and the prisoners are set free.
How did they do it?
-Veit _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Mike Stay - metaweta@gmail.com http://www.cs.auckland.ac.nz/~mike http://reperiendi.wordpress.com
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Thane Plambeck tplambeck@gmail.com http://counterwave.com/
Tanya Khovanova's Math Blog, in a 2010 posting, attributes the puzzle to Leonid Makar-Limanov. Another excellent example of this kind of puzzle is Lionel Levine’s hats puzzle*. Sometimes the warden is a sultan and the prisoners are his wizards. In any case, the premise is that the protagonists manage to transmit information in seemingly impossible circumstances. * N prisoners are in a room. Each is wearing an infinite tower of hats of two colors, black and white. The hats were placed on each prisoner by the warden, who chose the sequence of colors on each head by flipping a fair coin. The hat towers are visible to each prisoner, except of course a prisoner cannot see his own tower. Before all this happened, the prisoners were allowed to have a strategy session and communicate freely. In the hat room, however, all communication is forbidden. There, each prisoner is only able to examine the hats on all the other prisoners. After the prisoners have had a chance to do this, they all must write down a likely position (1 or 2 or 3 etc.) of a black hat in their own tower. The scoring for this game is very simple. If all N prisoners correctly locate a black hat they are all released from prison. But if even one prisoner gives the position of a white hat, then all are given a life sentence. Do the prisoners have a strategy that improves the probability they are released (over just random guesses), and if so, what is the best strategy?
On Apr 15, 2015, at 1:25 PM, Thane Plambeck <tplambeck@gmail.com> wrote:
This puzzle, and related ones, seem to be coming up a lot. It was performed (with 16 replacing 64) at a recreational math conference I recently attended in Portugal earlier this year. I was also told about it at the last Gathering 4 Gardner in Atlanta (spring 2014). The person who showed it to me first was Colin Wright I think (cc'ed), who might be able to say where he heard about it (if he didn't make it up himself).
Another classic: N prisoners, each with a black or white hat, chosen uniformly and independently. When a bell rings (and it only rings once) each either guesses the color of their own hat or remains silent. If no one speaks, they all die; if _anyone_ guesses their hat color wrong, they all die; but if at least one person guesses their own hat correctly, and no one guesses incorrectly, they all live. Note that whenever someone speaks, they are correct with probability 1/2. Nevertheless, show that (with some planning beforehand) the prisoners can win with probability approaching 1 as N -> infinity. This got some nice press: http://www.nytimes.com/2001/04/10/science/why-mathematicians-now-care-about-... - Cris On Apr 16, 2015, at 8:40 AM, Veit Elser <ve10@cornell.edu> wrote:
Tanya Khovanova's Math Blog, in a 2010 posting, attributes the puzzle to Leonid Makar-Limanov. Another excellent example of this kind of puzzle is Lionel Levine’s hats puzzle*. Sometimes the warden is a sultan and the prisoners are his wizards. In any case, the premise is that the protagonists manage to transmit information in seemingly impossible circumstances.
* N prisoners are in a room. Each is wearing an infinite tower of hats of two colors, black and white. The hats were placed on each prisoner by the warden, who chose the sequence of colors on each head by flipping a fair coin. The hat towers are visible to each prisoner, except of course a prisoner cannot see his own tower.
Before all this happened, the prisoners were allowed to have a strategy session and communicate freely. In the hat room, however, all communication is forbidden. There, each prisoner is only able to examine the hats on all the other prisoners. After the prisoners have had a chance to do this, they all must write down a likely position (1 or 2 or 3 etc.) of a black hat in their own tower.
The scoring for this game is very simple. If all N prisoners correctly locate a black hat they are all released from prison. But if even one prisoner gives the position of a white hat, then all are given a life sentence.
Do the prisoners have a strategy that improves the probability they are released (over just random guesses), and if so, what is the best strategy?
On Apr 15, 2015, at 1:25 PM, Thane Plambeck <tplambeck@gmail.com> wrote:
This puzzle, and related ones, seem to be coming up a lot. It was performed (with 16 replacing 64) at a recreational math conference I recently attended in Portugal earlier this year. I was also told about it at the last Gathering 4 Gardner in Atlanta (spring 2014). The person who showed it to me first was Colin Wright I think (cc'ed), who might be able to say where he heard about it (if he didn't make it up himself).
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Is the inmate allowed to _not_ flip any coin? Cris On Apr 15, 2015, at 1:55 PM, Veit Elser <ve10@cornell.edu> wrote:
There’s a growing class of puzzles I call Mensa Correctional Facility puzzles. In these puzzles there is always a warden who challenges prisoners with math/logic puzzles and grants them freedom when they succeed in solving them. Does anyone know the origins of the following one:
In this puzzle the warden challenges a pair of Mensa inmates. The first inmate is shown to the warden’s room and the warden proceeds to place identical coins, each one either heads up or tails up, onto the 64 squares of a checkerboard. He then points to one of the coins and declares it to be the “freedom coin”. The inmate watching this is then invited to flip one of the coins to help his partner identify the freedom coin. Then, without allowing the inmates to communicate with each other, the second inmate is lead into the room, shown the coins, and after a little head scratching points to the freedom coin — he is, after all, a Mensa inmate — and the prisoners are set free.
How did they do it?
-Veit _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
This type of puzzle has been around since at least 1975. Gosper told me the S-and-P puzzle. I hope he can recall the exact details; my memory of it is fuzzed. Roughly (for flavor -- don't waste time trying to solve this): Two players, Sam & Paul. There are two numbers between 1 and 99. Sam is told the sum, Paul is told the product. Each can hear the other's answers; is a perfect logician, etc. Each is asked, in turn, if he knows the numbers. Sam: I don't know. Paul: I don't know. Sam: I don't know. Paul: Now I know. Sam: Now I know too. The puzzle is (of course) "What are the numbers?" Rich -------- Quoting Veit Elser <ve10@cornell.edu>:
There is a solution when the inmate is required to flip a coin, so let's stick with that more restrictive variant.
-Veit
On Apr 15, 2015, at 5:47 PM, Cris Moore <moore@santafe.edu> wrote:
Is the inmate allowed to _not_ flip any coin?
Cris
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Is this what you're thinking of? http://en.wikipedia.org/wiki/Impossible_Puzzle Tom rcs@xmission.com writes:
This type of puzzle has been around since at least 1975. Gosper told me the S-and-P puzzle. I hope he can recall the exact details; my memory of it is fuzzed. Roughly (for flavor -- don't waste time trying to solve this): Two players, Sam & Paul. There are two numbers between 1 and 99. Sam is told the sum, Paul is told the product. Each can hear the other's answers; is a perfect logician, etc. Each is asked, in turn, if he knows the numbers. Sam: I don't know. Paul: I don't know. Sam: I don't know. Paul: Now I know. Sam: Now I know too. The puzzle is (of course) "What are the numbers?"
Rich
-------- Quoting Veit Elser <ve10@cornell.edu>:
There is a solution when the inmate is required to flip a coin, so let's stick with that more restrictive variant.
-Veit
On Apr 15, 2015, at 5:47 PM, Cris Moore <moore@santafe.edu> wrote:
Is the inmate allowed to _not_ flip any coin?
Cris
Do not follow this link unless you have better reflexes than I do; they went directly from the statement to a solution before I could look away, thus ruining the problem for me. Here is the statement, copied: X and Y are two different integers, greater than 1, with sum less than 100. S and P are two mathematicians; S knows the sum X+Y, P knows the product X*Y, and both know the information in these two sentences. The following conversation occurs: P says "I do not know X and Y." S says "I knew you don't know X and Y." P says "Now I know X and Y." S says "Now I know X and Y too!" What are X and Y? On Wed, Apr 15, 2015 at 7:01 PM, Tom Karzes <karzes@sonic.net> wrote:
Is this what you're thinking of?
http://en.wikipedia.org/wiki/Impossible_Puzzle
Tom
rcs@xmission.com writes:
This type of puzzle has been around since at least 1975. Gosper told me the S-and-P puzzle. I hope he can recall the exact details; my memory of it is fuzzed. Roughly (for flavor -- don't waste time trying to solve this): Two players, Sam & Paul. There are two numbers between 1 and 99. Sam is told the sum, Paul is told the product. Each can hear the other's answers; is a perfect logician, etc. Each is asked, in turn, if he knows the numbers. Sam: I don't know. Paul: I don't know. Sam: I don't know. Paul: Now I know. Sam: Now I know too. The puzzle is (of course) "What are the numbers?"
Rich
-------- Quoting Veit Elser <ve10@cornell.edu>:
There is a solution when the inmate is required to flip a coin, so let's stick with that more restrictive variant.
-Veit
On Apr 15, 2015, at 5:47 PM, Cris Moore <moore@santafe.edu> wrote:
Is the inmate allowed to _not_ flip any coin?
Cris
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- -- http://cube20.org/ -- [Golly link suppressed; ask me why] --
Number the coins from 000000 to 111111 (in binary), and let F be the freedom coin. The prisoner then flips coin (F XOR G), where G is the XOR of all of the heads-up coins. Then the next prisoner just XORs all of the heads-up coins to obtain F. Sincerely, Adam P. Goucher
Sent: Thursday, April 16, 2015 at 2:03 AM From: "Veit Elser" <ve10@cornell.edu> To: math-fun <math-fun@mailman.xmission.com> Subject: Re: [math-fun] Mensa Correctional Facility
There is a solution when the inmate is required to flip a coin, so let’s stick with that more restrictive variant.
-Veit
On Apr 15, 2015, at 5:47 PM, Cris Moore <moore@santafe.edu> wrote:
Is the inmate allowed to _not_ flip any coin?
Cris
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
participants (8)
-
Adam P. Goucher -
Cris Moore -
Mike Stay -
rcs＠xmission.com -
Thane Plambeck -
Tom Karzes -
Tom Rokicki -
Veit Elser