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!