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!

|cite|improve this question
$\endgroup$
  • $\begingroup$ yes, precisely that. I have edited the post. $\endgroup$ – Andy Nov 7 '12 at 2:23
  • 1
    $\begingroup$ Wouldn't the winner simply be determined from the parity of the permutation? $\endgroup$ – EuYu Nov 7 '12 at 2:24
  • $\begingroup$ ^can you please explain? $\endgroup$ – Andy Nov 7 '12 at 2:26
  • 1
    $\begingroup$ 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. $\endgroup$ – EuYu Nov 7 '12 at 2:27
  • 2
    $\begingroup$ 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. $\endgroup$ – joriki Nov 26 '12 at 4:21
4
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Sorry, I have looked at the Wikipedia article on permutations and dont see how one could immediately tell if it is even or odd. I assume that will lead into the probability. $\endgroup$ – Andy Nov 7 '12 at 14:27
  • $\begingroup$ @Andy: Did you read this part of the article? "In practice, in order to determine whether a given permutation is even or odd, one writes the permutation as a product of disjoint cycles. The permutation is odd if and only if this factorization contains an odd number of even-length cycles. Another method for determining whether a given permutation is even or odd is to construct the corresponding permutation matrix and compute its determinant. The value of the determinant is the same as the parity of the permutation." If so, what part of that is unclear? $\endgroup$ – joriki Nov 7 '12 at 15:09
  • $\begingroup$ @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. $\endgroup$ – joriki Nov 7 '12 at 15:11
  • $\begingroup$ @joriki: I see what you mean (though it only fails for the 321 pattern) - I will delete my earlier comment $\endgroup$ – Henry Aug 25 '15 at 9:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.