Problem of the Week 1221

Minimizing the Flip-Count

Note: This beautiful problem, by Stan Wagon and Larry Carter, extends a previous one. To make progress here, one must first understand Problem 1219.

Alice and Bob are prisoners of warden Charlie. Alice will be brought into Charlie's room on Sunday and shown 8 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 T. Bob will turn over the cards, one at a time, in search of T. When he finds T, he stops.

Find a strategy for Alice and Bob that yields a lower expected flip count than the value E(8) that is the answer to MacPOW 1220. Perhaps Charlie will release X prisoners, where X is the number of unflipped cards. Then minimizing the expected flipcount maximize the number of freed prisoners.

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. If Bob finds the target, both prisoners are freed immediately. If he fails to find the target, they stay imprisoned.

Certainly, problems like this can involve a lot of computing. I should know, as I have investigated several million trial cases over the past week!