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.
Lhs1002
55
Answer
Answers can be viewed only if
- The questioner was satisfied and accepted the answer, or
- The answer was disputed, but the judge evaluated it as 100% correct.
1 Attachment
Martin
767
The answer is accepted.
Join Matchmaticians Affiliate Marketing
Program to earn up to 50% commission on every question your affiliated users ask or answer.
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.
What about Q then?
Oh, never mind I got it. So you mean the card 3 itself is after 2, not in the permutation
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.
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.
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.
Thank you for your insight. I’d like to see your partial results.