As a math lover and an amateur magician (owing in part to Martin Gardner's excellent writings), I can't help but ask a question about a classic mathematical card trick. This question could be answered easily with the aid of a computer, I imagine.
The trick is known under numerous names, including Mutus Nomen Dedit Cocus. The gist is that a spectator secretly selects one of ten pairs of cards, and the magician deals them, seemingly randomly, into four rows of five cards apiece, and asks the spectator which row or rows contain the cards. In actuality, the magician is dealing the cards in such a way that each pair of cards corresponds to a different pair of rows. Using a mnemonic such as MUTUS NOMEN DEDIT COCUS or BIBLE ATLAS GOOSE THIGH, the cards can be readily identified. For example, using BIBLE ATLAS GOOSE THIGH as our mnemonic, if the cards are in the first and second rows, they correspond to the pair of L's shared by BIBLE and ATLAS, meaning the fourth card in the first row and the third card in the second row are the answer.
There is also a trick called Rubik's Cards or Order from Chaos where cards in seemingly random order are put in order via an unusual series of moves which at first glance appear to be mixing them up even further. The question is whether instead of dealing the cards out in a seemingly random order, one can appear to thoroughly mix up the cards before dealing them out. Of course, remembering a five-word mnemonic and a series of shuffles might be harder than just memorizing the words and dealing the cards accordingly, but it might make the trick more of a fooler. As an added bonus, there are certain arrangements (such as AABCD BEEFG CFHHI DGIJJ) that would be unsuited for the "deal them randomly" presentation of the trick, because the pattern of the dealing would be obvious, but by appearing to mix the cards up, such arrangements can be employed.
The cards start in the order AABBCCDDEEFFGGHHIIJJ, and our goal is to get them in an order that is equivalent to one of the numerous mnemonics, such as MUTUS NOMEN DEDIT COCUS or BIBLE ATLAS GOOSE THIGH, via a simple-to-remember series of controlled shuffles. If a computer is given a database of several such shuffles, it can work out the simplest way to use them to get from our starting point to our ending point. It is worth noting first that there are not actually 20! permutations of the 20 cards, since we're dealing with 10 pairs of cards. Naively, one might divide 20! by 2^10=1024 to calculate the number of permutations. However, it is even fewer than that; we only care about which cards are paired with which other cards. AABBCDDC is the same as CCAADBBD. Therefore, there are a mere 19*17*15*13*11*9*7*5*3*1=1,382,205,825 permutations in the search space. A Rubik's Cube has 43,252,003,274,489,856,000 positions, and God's Algorithm has been calculated for that, so I doubt that this particular problem will be much harder computationally.
Here are the controlled shuffles employed in Rubik's Cards:
2FC: LKBFAEMJIDCGH -> BFAEMJIDCGHKL
3FC: BFAEMJIDCGHKL -> EMJIDCGHKLAFB
4FC: EMJIDCGHKLAFB -> DCGHKLAFBIJME
3,2BC: DCGHKLAFBIJME -> JMEBILAFHKDCG
RIS: JMEBILAFHKDCG -> MBLFKCJEIAHDG
AS: MBLFKCJEIAHDG -> ABCDEFGHIJKLM
The cards don't appear to be in any particular order until the final step. Of course, the person who created this trick probably just took some random-looking, but easily remembered, moves and reversed them to get the starting configuration. In this problem, we're given a starting configuration and an ending configuration, and wish to find the shortest route. It's trivial to prove that any configuration can be reached via 1FC's and 2FC's (although such a solution is potentially extremely long, not to mention that 1FC's seem inelegant to me), but by adding more controlled shuffles to the database and taking advantage of the fact that we have a choice of many ending positions (the words BIBLE ATLAS GOOSE THIGH can be placed in 24 different orders, they can be dealt from a deck of BAGTITOHBLOILASGESEH or from a deck of BIBLEATLASGOOSETHIGH), surely a reasonably memorable solution can be found. We only have under 1.4 billion positions to navigate, after all!
(Addendum: A proposed generalization of the Australian shuffle is the n Australian Shuffle, where there are n unders after each down. Thus, the AS becomes the 1AS, a 0AS reverses the order of the deck, and a 3AS turns ABCDEF into BDFCEA.)
The trick is known under numerous names, including Mutus Nomen Dedit Cocus. The gist is that a spectator secretly selects one of ten pairs of cards, and the magician deals them, seemingly randomly, into four rows of five cards apiece, and asks the spectator which row or rows contain the cards. In actuality, the magician is dealing the cards in such a way that each pair of cards corresponds to a different pair of rows. Using a mnemonic such as MUTUS NOMEN DEDIT COCUS or BIBLE ATLAS GOOSE THIGH, the cards can be readily identified. For example, using BIBLE ATLAS GOOSE THIGH as our mnemonic, if the cards are in the first and second rows, they correspond to the pair of L's shared by BIBLE and ATLAS, meaning the fourth card in the first row and the third card in the second row are the answer.
There is also a trick called Rubik's Cards or Order from Chaos where cards in seemingly random order are put in order via an unusual series of moves which at first glance appear to be mixing them up even further. The question is whether instead of dealing the cards out in a seemingly random order, one can appear to thoroughly mix up the cards before dealing them out. Of course, remembering a five-word mnemonic and a series of shuffles might be harder than just memorizing the words and dealing the cards accordingly, but it might make the trick more of a fooler. As an added bonus, there are certain arrangements (such as AABCD BEEFG CFHHI DGIJJ) that would be unsuited for the "deal them randomly" presentation of the trick, because the pattern of the dealing would be obvious, but by appearing to mix the cards up, such arrangements can be employed.
The cards start in the order AABBCCDDEEFFGGHHIIJJ, and our goal is to get them in an order that is equivalent to one of the numerous mnemonics, such as MUTUS NOMEN DEDIT COCUS or BIBLE ATLAS GOOSE THIGH, via a simple-to-remember series of controlled shuffles. If a computer is given a database of several such shuffles, it can work out the simplest way to use them to get from our starting point to our ending point. It is worth noting first that there are not actually 20! permutations of the 20 cards, since we're dealing with 10 pairs of cards. Naively, one might divide 20! by 2^10=1024 to calculate the number of permutations. However, it is even fewer than that; we only care about which cards are paired with which other cards. AABBCDDC is the same as CCAADBBD. Therefore, there are a mere 19*17*15*13*11*9*7*5*3*1=1,382,205,825 permutations in the search space. A Rubik's Cube has 43,252,003,274,489,856,000 positions, and God's Algorithm has been calculated for that, so I doubt that this particular problem will be much harder computationally.
Here are the controlled shuffles employed in Rubik's Cards:
- The n Frustration Count: The top n cards are reversed and put below the rest of the deck. A 2 Frustration Count (2FC) on ABCDEFGHIJKLM yields CDEFGHIJKLMBA.
- The n,m Block Count: Cards are dealt to the table in blocks of n and m, reversing the order of the blocks, but not the cards within the blocks. A 3,2 Block Count (3,2BC) on ABCDEFGHIJKLM yields KLMIJFGHDEABC.
- The Reverse Faro Shuffle: Cards are alternately injogged and outjogged so the cards in even-numbered positions stick out, and then are put either below (for a Reverse Out Shuffle) or on top of (for a Reverse In Shuffle) the cards in odd-numbered positions. A Reverse In Shuffle (RIS) on ABCDEFGHIJKLM yields BDFHJLACEGIKM.
- The Australian Shuffle: The cards are alternately dealt "down" to the table and "under" the rest of the pack. ABCDEFGHIJKLM becomes JFBLHDMKIGECA.
2FC: LKBFAEMJIDCGH -> BFAEMJIDCGHKL
3FC: BFAEMJIDCGHKL -> EMJIDCGHKLAFB
4FC: EMJIDCGHKLAFB -> DCGHKLAFBIJME
3,2BC: DCGHKLAFBIJME -> JMEBILAFHKDCG
RIS: JMEBILAFHKDCG -> MBLFKCJEIAHDG
AS: MBLFKCJEIAHDG -> ABCDEFGHIJKLM
The cards don't appear to be in any particular order until the final step. Of course, the person who created this trick probably just took some random-looking, but easily remembered, moves and reversed them to get the starting configuration. In this problem, we're given a starting configuration and an ending configuration, and wish to find the shortest route. It's trivial to prove that any configuration can be reached via 1FC's and 2FC's (although such a solution is potentially extremely long, not to mention that 1FC's seem inelegant to me), but by adding more controlled shuffles to the database and taking advantage of the fact that we have a choice of many ending positions (the words BIBLE ATLAS GOOSE THIGH can be placed in 24 different orders, they can be dealt from a deck of BAGTITOHBLOILASGESEH or from a deck of BIBLEATLASGOOSETHIGH), surely a reasonably memorable solution can be found. We only have under 1.4 billion positions to navigate, after all!
(Addendum: A proposed generalization of the Australian shuffle is the n Australian Shuffle, where there are n unders after each down. Thus, the AS becomes the 1AS, a 0AS reverses the order of the deck, and a 3AS turns ABCDEF into BDFCEA.)
