Solution
Problem 1219 placed Alice and and Bob in the custody of Charlie, who offered them a way out — if they were clever. Several of you would have achieved release! Kudos to A. Kunin, Jim Guilford, P. J. LoPresti, J.Yoak, J. Grossman, and J. Brawner.
The idea is that Bob will "follow what he knows." When he hears the target card T, he opens door T. If he sees S there, he then opens door S. And so forth.
At some point, this will cycle around back to position T. To do that, the preceding card must be T. This is because every permutation is a product of cycles. So if the cycle has length k, he will have to flip k cards. Alice, by her initial switch, can guarantee that the largest cycle has length 26 or less.
Here are more details, as provided by Abraham Kunin:
Assign an order to the cards in the deck. Now let us talk about the cards as being numbered 1, ..., 52.
Suppose the target card is numbered T. Bob's strategy is to turn over the card in slot T. If that is not the target card, but is instead numbered S, Bob turns over the card in slot S. As long as Alice leaves a permutation of 1, ..., 52 that is a product of cycles of length less than or equal to 26, Bob will succeed.
Now, the permutation of 1, ..., 52 that Alice sees is a product of cycles of various lengths. Let the maximum length of one of these cycles be N. If N ≤ 26, then Alice leaves the cards as is, and Bob wins. If N > 26, then there is a single cycle of length N, and all other cycles must have length less than 26. All Alice has to do is break the lone longest cycle into two or more cycles of length less than 27.
This is easily done as follows: suppose without loss of generality that the cycle is 1-2-3-...-N. That is, 1 gets sent to 2, 2 gets sent to 3, ..., N gets sent to 1. Then swap card N with card 26 and you will end up with two cycles, 1-2-3-...-26 and 27-...-N.
There are some very interesting variations on this puzzle, one of which appears as MacPOW 1220.
[Back to Problem 1219]
© Copyright 2016 Stan Wagon. Reproduced with permission.