1
$\begingroup$

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?

  • 1
    Are you familiar with [even and odd permutations](http://en.wikipedia.org/wiki/Parity_of_a_permutation)?2012-11-25
  • 0
    Sounds interesting. But I suspect that when playing in practice it can be rather unwieldy to keep track of the already-used orderings.2012-11-25
  • 0
    @GerryMyerson I do think that the question I am asking a little different, however.2012-11-25
  • 0
    @BrianM.Scott In that case why are half of the permutations even? How precisely can that be explained?2012-11-25
  • 0
    Look at joriki's last comment [here](http://math.stackexchange.com/questions/231843/game-theory-matching-a-deck-of-cards#comment515414_231933).2012-11-25
  • 0
    @Layla: As far as I can tell, the only part of your question that wasn't asked and answered in that other thread is your last paragraph. I'm not sure I understand what you mean there -- "ideal" in which sense? For one of the players? Or are you asking, independent of the players' goals in the game, how the deck can be ordered without repeating any arrangement? For that, simply swap the $1$ upwards until it's on top; then swap the $2$ upwards until it's second, etc.2012-11-25
  • 0
    @joriki does that strategy (decidedly a greedy algorithm)satisfy being the shortest, though?2012-11-25
  • 0
    Layla, I'm glad you think your question was a little different (even before you edited in the Las Vegas paragraph), but your thinking so and it being so are two different things. What exactly was there in your question that wasn't asked and answered in the earlier question? You have to make a case, not just an assertion.2012-11-25
  • 0
    @Gerry I did think that the portion with the ideal playing strategy lining up with the smallest possible number of turns was unique.2012-11-25
  • 0
    @Layla: Your edit has made things less, not more clear to me. It seems that the losing player has no interest in increasing the profit for the winning player by cooperating to choose the shortest sequence of swaps; so I don't see why the formulation with two players should be equivalent to the problem of finding the shortest sequence. In any case, it's a suboptimal setup to edit that one paragraph to clarify what was originally a small subquestion -- it seems the cleanest way to proceed now is if we close this as a duplicate and you ask a new question with a clear formulation of the last part.2012-11-25
  • 0
    @joriki I suppose what I am asking is the following: the two players play this game, with no knowledge of who will win. They are experienced and hence perfect players, always playing the game on the shortest path. Even with this in mind is it possible that the rule "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." can be invoked even if the smallest number of turns is made? To rephrase, is there a ordering whose corresponding shortest path of moves must repeat a config to reach the game's end?2012-11-25
  • 0
    @joriki or would the shortest game simply become the next shortest path without repeats? I see that your algorithm of switching 1 to the top first, then 2, and so on produces no repeats but is doing that the shortest way of playing the game?2012-11-25
  • 0
    @joriki in any case I have made the question unique now so that it doesn't overlap with the other one.2012-11-25
  • 0
    @GerryMyerson I do not see why this was closed...2012-11-26
  • 3
    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 http://mit.edu/primes/materials/2013/entproUSA13.pdf2012-11-26
  • 8
    @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.2012-11-26

0 Answers 0