Formula for permutation problem

1) Lay out 13 cards (Ace to King) in a row in some random order. 

2) Move the Ace to the front of the row, such that it leaves an empty space. (7A9... becomes A7_9...). 

3) Swap the empty space with the card that comes after the card directly left of the empty space ( ...2_Q3K... becomes ...23Q_K...).

4) Repeat step 3 until the King is to the left of the empty space (...K_5...).

A permutation is considered "solvable" if the permutation eventually becomes A234...JQK_. 

a) If it exists, find a formula that determines if an arbitrary permutation P is solvable.

b) If possible, generalize the formula for n cards.

Show your reasoning for both.

  • Martin Martin

    In (3) I think you mean "right of the empty space". Is that the case?

    • No I mean left. In …2_Q3K…, the 2 card is to the left of the space. 3 come after 2, so the space should be swapped with the 3 card.

  • Martin Martin

    What about Q then?

    • Martin Martin

      Oh, never mind I got it. So you mean the card 3 itself is after 2, not in the permutation

  • Martin Martin

    And in (4) you mean K is immediately left to the space?

    • Yes. The idea being that since the King is the greatest card, there is no card that comes after it, and thus there is no card to swap the empty space with.

  • Martin Martin

    Yes, I get it now. At first I was confused by your example in rule (3) and thought you mean empty moves two to the right. So I prepared an answer based on that. Now with what you actually intend, the problem is much harder. I highly doubt that there is any "formula" or simple criteria that determine "solvable" permutations. I have some partial results explaining how a permutation evolves in this process, which may or may not characterize "solvable" permutations at the end.

    • Martin Martin

      If you are interested in that I can keep working on it. Otherwise we can ask a moderator to undo my taking the problem and see if others have more to say.

    • Lhs1002 Lhs1002

      Thank you for your insight. I’d like to see your partial results.


Answers can only be viewed under the following conditions:
  1. The questioner was satisfied with and accepted the answer, or
  2. The answer was evaluated as being 100% correct by the judge.
View the answer

1 Attachment

The answer is accepted.
Join Matchmaticians Affiliate Marketing Program to earn up to a 50% commission on every question that your affiliated users ask or answer.