Possible Duplicate:
Game Theory Matching a Deck of Cards

Suppose we take a blank deck of $52$ cards, write the number $1$ on the first card, $2$ on the second card, and so on until we write $52$ on the final card. Then we shuffle this deck of cards and stack it. Then two people take turns switching the positions of any two consecutive cards in the deck. No order of cards can be repeated. The player who first gets the deck back to the order $1,2,3...52$ wins, unless the shuffled deck is already in that order, in which case the second player wins. If a player can show that there is no way to get to the $1,2,3,...52$ ordering without repeating any arrangement previously made then that player wins.

I can see from this set-up that any given order of cards is predisposed to being transformed to the $1,2...52$ order in either an even or an odd number of moves(though I am not certain precisely why). Hence the probability, given a random shuffled ordering, of either player winning, should be $\frac{1}{2}$.

Now suppose that the game is being played in Vegas! The mediator of the game holds a winning value dependent on how many turns the game takes. Every turn, the mediator increases the winning prize amount by a factor $p$. If the game takes no turns, the second player wins a dollar. However the mediator can only award the prize if all moves made are the smallest possible path from the shuffled ordering to $1,2,3,..52$. For instance, the second player would not get any winnings if(for the sake of example I will play the game with 3 cards, with the initial ordering $231$,the game was played as $231\rightarrow321\rightarrow312\rightarrow132\rightarrow123$ as opposed to $231\rightarrow 213\rightarrow123$, in which case player 2 will win $p^2$ dollars- he/she can't win $p^4$ dollars. So instead, I suppose we can simply say that for a given starting ordering the game is always played such that the fewest number of turns possible are taken(anyways we know who is going to win!) How can we find the expected number of turns? How can we find the expected winning prize?


marked as duplicate by Gerry Myerson, Henning Makholm, Ross Millikan, joriki, Austin Mohr Nov 26 '12 at 0:13

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 1
    $\begingroup$ Are you familiar with even and odd permutations? $\endgroup$ – Brian M. Scott Nov 25 '12 at 22:47
  • $\begingroup$ Sounds interesting. But I suspect that when playing in practice it can be rather unwieldy to keep track of the already-used orderings. $\endgroup$ – Henning Makholm Nov 25 '12 at 22:52
  • $\begingroup$ @GerryMyerson I do think that the question I am asking a little different, however. $\endgroup$ – Layla Patil Nov 25 '12 at 22:53
  • 3
    $\begingroup$ It was closed because five people considered it to be a duplicate of a question that had already been asked and answered. If you want it reopened you should edit it to include a reference to (and/or discussion of) the earlier problem, indicating precisely what is new here. And you might also want to explain how it differs from Problem 9 of the ongoing competition at mit.edu/primes/materials/2013/entproUSA13.pdf $\endgroup$ – Gerry Myerson Nov 26 '12 at 1:31
  • 8
    $\begingroup$ @Layla: Posting a contest problem without mentioning the source was particularly inappropriate in this case, since you wasted our time with flawed reformulations of the problem (including the present one) that could have been avoided if you had simply linked to the source. Very annoying. $\endgroup$ – joriki Nov 26 '12 at 4:17