# Game Theory Matching a Deck of Cards

Moderator Note: This question is from a contest which ended 1 Dec 2012.

Suppose we have a deck of cards labeled from $1$ to $52$. Let them be shuffled in a random configuration, then made visible.

Two players, player $A$ and $B$ play a game in which they try to organize the deck back to the order $1,2,3,...,52$. The players alternate turns with $A$ going first. The rules are as follows:

i) On each turn, you may only switch adjacent cards.

ii) Once a certain conﬁguration of cards has been reached, it may not be repeated.

iii) The player that orders the deck as $1,2,3,...,52$ after his move wins.

iv) If your opponent makes a move from where it is impossible to reach the configuration $1,2,3,...,52$, you win.

v) If the cards are already initially ordered $1,2,3,...,52$, player $B$ wins.

I have two questions regarding this game:

If both $A$ and $B$ play optimally, how can you tell who wins?

What is the probability that player $A$ wins?

I was thinking along the broad lines of finding some sort of invariant, but other than that I have no clue. Any help is appreciated. Thank you!

-
yes, precisely that. I have edited the post. – Andy Nov 7 '12 at 2:23
Wouldn't the winner simply be determined from the parity of the permutation? – EuYu Nov 7 '12 at 2:24
^can you please explain? – Andy Nov 7 '12 at 2:26
Every permutation is odd or even (i.e. not simultaneously both), meaning that it can be undone either using an even number of switches or an odd number of switches. If your shuffle happens to be odd, then then player $A$ will win no matter how they play. If your shuffle happens to be even, then player $B$ will win. – EuYu Nov 7 '12 at 2:27
I've deleted my answer since it turned out that this question is from an ongoing contest. This fact should have been mentioned in the original post. – joriki Nov 26 '12 at 4:21

@Andy: Regarding the probability: This is $\frac12$, since half of all permtuations (those forming the alternating group $A_{52}$) are even. This follows e.g. from the fact that the cosets with respect to any transposition are of equal size and contain the even and odd permutations, respectively. – joriki Nov 7 '12 at 15:11