This problem came to me while I was doing the English alphabet flashcards with my four year old. Each day I would shuffle the cards and lay them out in front of her, and she would follow my movement until she finds "A", then "B", then "C", etc, without going back to the cards that were laid down earlier. If I finish laying out all the cards before she finds the next letter, she would start at the end and search for the next letter in reverse order until she reaches the first card I put down. The process repeats. These two problems are a simplified (and later generalized) version of this process.
I. Suppose there are ten cards marked 1-10. I shuffle them and lay them out, like so, for example:
9, 5, 6, 10, 7, 1, 4, 2, 8, 3
Now I start from left to right and look for the numbers in order. The first round going from left to right, I would find:
1, 2 ,3
Then I go from right to left for the second round:
4, 5
Then left to right again for the third round:
6, 7, 8
Fourth round, right to left:
9
Fifth round, left to right:
10
This arrangement of cards takes 5 rounds to sort back to the original order.
A. There is only one arrangement that would take exactly 1 round to sort back to the original order, and that’s the original order itself:
1, 2, 3, 4, 5, 6, 7, 8, 9, 10.
How many arrangements would take exactly 2 rounds to sort back to the original order?
B. Make another arrangement of these ten cards that takes 5 rounds to sort back to the original order.
C. Make another arrangement of these ten cards that gives the same sorting rounds:
1, 2, 3
4, 5
6, 7, 8
9
10
D. How many arrangements are there that give the same sorting rounds as in Part C?
E. How do you calculate the number of arrangements that give any particular list of sorting rounds?
F. How many arrangements of these ten cards are there that would take exactly 5 rounds to sort back to the original order?
G. How many arrangements of n cards are there that would take k rounds to sort back to the original order?