4
$\begingroup$

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 configuration 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!

  • 0
    I've undeleted the answer because the contest has ended.2012-12-10

1 Answers 1

4

As EuYu pointed out, the winner is determined by the parity of the permutation. Each move toggles the parity, so only one of the players can reach the identity. The other player cannot block the path to the identity because then she would lose by iv), and she can't force the winning player to block the path.

  • 0
    @joriki: I see what you mean (though it only fails for the 321 pattern) - I will delete my earlier comment2015-08-25