Problem of the Week 1219

Prisoner Dilemma

Prisoner Dilemma

Alice and Bob are prisoners of warden Charlie. Alice will be brought into Charlie's room on Sunday and shown a standard deck of 52 cards, face-up in a row in some arbitrary order. Alice can, if she wishes, interchange two cards. She then leaves the room and Charlie turns all cards face-down in their places.

Bob is then brought to the room. Charlie calls out a random target card. Bob can turn over cards, at most 26, in an attempt to locate the target. He can base his choice of card to flip on what he has seen so far. If Bob finds the target, both prisoners are freed immediately. If he fails to find the target, they stay imprisoned.

Find a strategy that guarantees success for the prisoners in all cases.

As always: Alice and Bob have the game described to them on Saturday and they are allowed to plan a strategy. On Sunday, there is no communication whatever between the prisoners; in particular, Alice has no idea what the target card will be.

Source: Originator not known. Piotr Krason told Kiran Kedlaya told Joe Buhler, and it is in the latest issue of Emissary, the newsletter of MSRI, Berkeley, page 11. The newsletter (with other nice problems in the problem section of Joe Buhler and Elwyn Berlekamp) is available from https://www.msri.org/web/msri/about-msri/news/emissary-newsletter

[View the solution]



February 2016