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
    yes, precisely that. I have edited the post.2012-11-07
  • 1
    Wouldn't the winner simply be determined from the parity of the permutation?2012-11-07
  • 0
    ^can you please explain?2012-11-07
  • 1
    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.2012-11-07
  • 0
    Sure, but then how would we go about precisely telling who wins (i.e. whether it's even or odd), based on the original configuration? And then what relevance would rule iv) have (i assume you mean by your comment that the deck can ALWAYS be rearranged, in which case rule iv is superfluous)2012-11-07
  • 2
    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.2012-11-26
  • 0
    I've undeleted the answer because the contest has ended.2012-12-10

1 Answers 1