Problem of the Week 1220

The Expected 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 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 T. Bob will turn over the cards, one at a time, in search of T. When he finds T, he stops.

If Charlie's choices (initial permutation and target) are purely random (i.e., each possibility is equally likely) and Alice uses the cycle-reducing strategy that is the solution to Problem 1219, what is the expected number E(52) of cards that Bob will flip before finding T?

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.

The cycle-reducing strategy means that Alice locates the longest cycle in p and makes a transposition so as to split it into two cycles of equal, or nearly equal size.

This problem is about n = 52, but it makes sense to think about smaller values (or indeed all values). Some easy values that can serve as a check include E(2) = 1 and E(3) = 11/9. E(8) is an interesting value for reasons to be shared later.

[View the solution]



February 2016