tag:blogger.com,1999:blog-11247422294983153392014-04-21T05:49:21.566-04:00Card ColmCard Colm is a bimonthly column sponsored by the Mathematical Association of America.
This column explores mathematical card principles and effects for fun, very much inspired by the extensive writings of Martin Gardner (1914-2010) on the subject, going back to his seminal Mathematics, Magic and Mystery (1956).Mathematical Association of Americahttp://www.blogger.com/profile/10559021045290192742noreply@blogger.comBlogger16125tag:blogger.com,1999:blog-1124742229498315339.post-56789073569870800792014-02-28T11:12:00.000-05:002014-03-03T11:44:42.515-05:00Postage Stamp IssueThere's no denying that the theme and spirit of <a href="http://www.mathaware.org/" target="_blank">Mathematics Awareness Month 2014</a> is inspired by the landmark book <a href="http://store.doverpublications.com/0486203352.html" target="_blank"><i>Mathematics, Magic and Mystery</i></a> (Dover, 1956) by legendary writer <a href="http://www.huffingtonpost.com/colm-mulcahy/martin-gardner_b_4125273.html" target="_blank">Martin Gardner, the best friend mathematics ever had</a>. <br /><br /><center><img alt="title" src="http://www.martin-gardner.org/pix/MGB%201956%20MMM1st.jpg" height="250px" /> <img alt="title" src="http://ecx.images-amazon.com/images/I/51F8CJ1ETRL._SY344_BO1,204,203,200_.jpg" height="250px" /> <a href="http://1.bp.blogspot.com/-L0tajmFCFKM/UxSxBmGuBSI/AAAAAAAAJYo/z7H_6pdInE0/s1600/mam2014.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="http://1.bp.blogspot.com/-L0tajmFCFKM/UxSxBmGuBSI/AAAAAAAAJYo/z7H_6pdInE0/s1600/mam2014.jpg" height="250" /></a></center><br />The beautiful MAM 2014 poster on the right here, a high resolution version of which can be <a href="http://www.mathaware.org/mam/2014/poster/final-version.pdf" target="_blank">downloaded</a>, was designed by <a href="http://www.mathaware.org/mam/2014/committee" target="_blank">Bruce and Eve Torrence</a> of Randolph-Macon College. It echos many of Martin Gardner's most beloved motifs: magic squares, knots, geometric vanishes, Möbius bands, illusions, and playing cards. <br /><h2><span style="font-size: large;"><br /></span></h2><h2><span style="font-size: large;">The Alumni Midterms </span></h2>Did somebody mention cards? For us, Martin's <a href="http://blogs.scientificamerican.com/guest-blog/2013/10/29/celebrations-of-mind-honor-maths-best-friend-martin-gardner/" target="_blank">extensive legacy</a> has proved to be a rich source of ideas for amusements with cards, going back to 1999, and many of these have surfaced in <i>Card Colm</i>s. It seems appropriate, in <a href="http://www.martin-gardner.org/" target="_blank">his centennial year</a>, to focus on new card activities derived from things Martin wrote about. What follows may serve as a way to generate interest in a classic combinatorial problem. <br /><br />Find a willing participant; let's call her Willa. A red-backed deck and a blue-backed deck are produced, and you quickly run through the cards in each deck face up, tossing aside all Jacks, Queens, and Kings. "We won't need those," you say, before giving Willa free choice of the two slimmed-down decks. Assume she takes the red deck and you take the blue one. <br /><br />Say, "Willa, let's play a game. We'll first do it with your deck, then we'll try it with mine. First you need to shuffle the cards. Please split the red deck roughly in the middle, and riffle the two resulting halves together." While Willa is shuffling, produce a pen, and a piece of paper on which is written a vertical list of the counting numbers from 1 to 30. <br /><br />Continue, "Please lift off the top half of those shuffled cards, as best you can estimate, it doesn't have to be precise. I get the other half." Set aside your half for later. "Now, please take about half of your cards, that should be ten cards, roughly. Your goal it to see how high you can get on this list, using at most three of these random card values added up, I'll keep track for you. Please look at your card faces, do you have an Ace? Great!" She does, and you write write A next to the the 1 on the list. Next to the 2 write either 2 or A + A, depending on whether she has a 2 or two Aces. Keep going as long as is possible, beside each number writing the values of cards she has which equal or add up to that number. <br /><br />The first time three card values are used, pause, and say, "Sorry, I forgot to mention that to make it more interesting, whenever you have three card values making up a particular number, you must use one of those cards again for the next number. Got it?" Since, you only just sprung this surprise on Willa, offer her the chance to redo that first three-value sum if she wants to. <br /><br />The result of Willa's efforts might be all numbers from 1 to 16 (or some other number) achieved, before she failed to get 17 subject to the "continuity" condition when using three cards. Have Willa do it all over, with the other roughly ten cards of her half deck, and another copy of the list. The results should be along the same lines. <br /><br />Yet, when you do the same with your cards, in two approximately 10-card palettes just like Willa, with her keeping track this time, on new copies of the list, you should do much better, getting to 25 or maybe even higher. <br /><br />The deck is rigged of course. Suits are irrelevant. You want to end up with three 4s and 5s in in your initial twenty cards, with Willa only getting one each of those values in hers. Furthermore, you arrange it to that each of you starts with an Ace and a 2 in each of your 10-card card palettes, otherwise it's hard to get started! It turns out that having several 4s and 5s helps you to beat her. <br /><br />Here's a suggested set-up, consisting of four 10-card packets. <br /><br /><div style="margin-left: 1em;">Packet A is these cards in this order, from the top down: any Ace, 2, 5, 7, 8, 4, 2, Ace, 7, 8. </div><br />Willa will end up with most of these, and the first and internal Ace and 2 for sure. You're letting her have one 4 and one 5 to deflect suspicion, otherwise, she may notice upon repetition that she never had a 4 or a 5. It turns out that if you had all four of each (and even more Aces) you'd be sure of getting to at least 15. <br /><br /><div style="margin-left: 1em;">Packet B is these cards in some jumbled order: all of the 3s and 6s, and two of the 7s. </div><br />You will end up with most of these. <br /><br /><div style="margin-left: 1em;">Packet C is these cards in some jumbled order: all of the 9s and 10s, and two of the 8s. </div><br />Willa will end up with most of these. <br /><br /><div style="margin-left: 1em;">Packet D is these cards in this order, from the top down: any 4, 5, Ace, 2, 5, 5, 4, 4, 2, Ace. </div><br />Most importantly, you will end up with most of these, and the internal and last Ace and 2 for sure. <br /><br />Stack A on top of B, on top of C stacked on top of D. Randomly insert the Jacks, Queens and Kings; they're only to add to the illusion of fairness, as they are pulled out again at the start of the effect. When Willa splits the resulting 40-card deck, she more or less riffle shuffles A and B into C and D. <br /><br />Furthermore, when she takes the top half of that for herself, she should get most of A and C, in such a way that the final split into two roughly 10-card packets gives her an Ace and 2 in each. Similar conclusions apply to the cards you end up with, which are more or less B and D. <br /><br />The restriction about having to reuse one of three cards used for a previous sum is designed to make it harder for Willa to win. <br /><br />It can be repeated with the other deck, which we suggest arranging in an order which exactly mirrors the type of set-up just proposed, i.e., runs in the opposite order. That way, you can take a gamble on saying, "Let's try that again. Maybe you'll have more luck if you take the bottom half of the deck this time." You may want to vary the card set-up a little so Willa doesn't realize that she's been duped a second time. <br /><br />We now explain the mathematics underlying this game. <br /><h2><span style="font-size: large;"><br /></span></h2><h2><span style="font-size: large;">Aha! Little Poet</span></h2><center><div class="wrap_around_image-left"><img alt="title" src="http://www.martin-gardner.org/pix/MGB%201981%20SFPT.jpg" height="250px" /> <img alt="title" src="http://www.martin-gardner.org/pix/MGB%202000%20MPT.jpg" height="250px" /><br /><br /></div></center>This month's <i>Card Colm</i> was inspired by Martin's science fiction puzzle tale "The Postage Stamps of Philo Tate" on page 15 of <a href="http://www.maa.org/publications/maa-reviews/mathematical-puzzle-tales" target="_blank"><i>Mathematical Puzzle Tales</i></a> (MAA, 2000), which is a reissue of <i>Science-Fiction Puzzle Tales</i> (Potter, 1981). That tale concerns the classic postage stamp problem (see <a href="http://en.wikipedia.org/wiki/Postage_stamp_problem" target="_blank">Wikipedia</a> and <a href="http://mathworld.wolfram.com/PostageStampProblem.html" target="_blank">MathWorld</a>). <a href="https://www.blogger.com/blogger.g?blogID=1124742229498315339"> <i></i></a><a href="https://www.blogger.com/blogger.g?blogID=1124742229498315339"> <i></i></a><a href="https://www.blogger.com/blogger.g?blogID=1124742229498315339"> <i></i></a><a href="https://www.blogger.com/blogger.g?blogID=1124742229498315339"> <i></i></a><a href="https://www.blogger.com/blogger.g?blogID=1124742229498315339"> <i></i></a> <br /><br />Postage stamps in D different demoninations (or values) are available. What amounts of postage can be made up using at most S stamps, where stamps of any denomination (or value) may be repeated? <br /><br />For instance, if D = 2, the values being 1 and 2, and S = 2, clearly we can make up 1, 2 (in two ways, as 2 or 1 + 1), 3 = 1 + 2 and 4 = 2 + 2, and no other amounts are possible. On the other hand, if D = 2 and the values are 1 and 3, and S = 2 again, then we can make up 1, 2 = 1 + 1, 3, 4 = 1 + 3, and 6 = 3 + 3, and no more amounts are possible. Note that 5 is not possible. <br /><br />The goal is to be able to make as a large an unbroken range 1 to R as possible using the available stamps, subject to a restriction on how many stamps can be used. In both examples above—where we can use up to two stamps of two values—it's 1 to 4. However, if D = 2, the values being 1 and 5, and S = 2, then 3 is not possible, so R = 2 this time. Obviously, we must always include 1 in the values allowed to even get started. <br /><br />If D = 3, the values being 1, 2 and 5, and S = 2, then it can be checked that 1 to 7 are possible, as is 10, but not 8 or 9. Here R = 7. <br /><br />If D = 3 again, with values 1, 2 and 5, but S = 3, then it can be checked that 1 to 12 are possible, but not 13 or 14, though 15 is. Here R = 12. <br /><br />The following table lists some of the optimal results when S = 3, i.e., when we use up to 3 stamps of various values, for various numbers D of denominations or values. Additional information can be found in <a href="http://oeis.org/A001213" target="_blank">Sequence A001213 in <i>The On-Line Encyclopedia of Integer Sequences</i></a>. One entry in the table is intentionaly left blank; filling it in correctly leads to a pleasant surprise or two. <br /><center><div style="text-align: center;"><br /></div><table border="" style="text-align: center;"><tbody><tr><td colspan="3">Using up to 3 stamps </td> </tr><tr><td>D = # of values </td><td>values </td><td>range 1 to R </td> </tr><tr align="center"><td>2</td><td>1, 3</td><td>1 to 7</td></tr><tr align="center"><td>3</td><td>1, 4, 5</td><td>1 to 15</td></tr><tr align="center"><td>4</td><td>1, 4, 7, 8</td><td>1 to 24</td></tr><tr align="center"><td>5</td><td>1, 4, 6, 14, 15</td><td>1 to 36</td></tr><tr align="center"><td>6</td><td>?</td><td>1 to 52</td></tr></tbody></table><div style="text-align: center;"></div></center><br />If we consider specific small values of D, for any S, then the maximal R are given by the following entries at <a href="http://oeis.org/" target="_blank"><i>The On-Line Encyclopedia of Integer Sequences</i></a>,<br /><br /><div style="margin-left: 1em;">D = 2 values, S = n stamps: <a href="http://oeis.org/A014616" target="_blank">Sequence A014616</a><br /><br />D = 3 values, S = n stamps: <a href="http://oeis.org/A001208" target="_blank">Sequence A001208</a><br /><br />D = 4 values, S = n stamps: <a href="http://oeis.org/A001209" target="_blank">Sequence A001209</a><br /><br />D = 5 values, S = n stamps: <a href="http://oeis.org/A001210" target="_blank">Sequence A001210</a><br /><br />D = 6 values, S = n stamps: <a href="http://oeis.org/A001211" target="_blank">Sequence A001211</a><br /><br /></div><div style="text-align: left;">Likewise, if we consider specific small values of S, for any D, then the maximal R are given by these entries at <a href="http://oeis.org/" target="_blank"><i>The On-Line Encyclopedia of Integer Sequences</i></a>, </div><br /><div style="margin-left: 1em;">D = n values, S = 2 stamps: <a href="http://oeis.org/A001212" target="_blank">Sequence A001212</a><br /><br />D = n values, S = 3 stamps: <a href="http://oeis.org/A001213" target="_blank">Sequence A001213</a><br /><br />D = n values, S = 4 stamps: <a href="http://oeis.org/A001214" target="_blank">Sequence A001214</a><br /><br />D = n values, S = 5 stamps: <a href="http://oeis.org/A001215" target="_blank">Sequence A001215</a><br /><br />D = n values, S = 6 stamps: <a href="http://oeis.org/A001216" target="_blank">Sequence A001216</a></div><br /><div style="text-align: left;">Information about arbitrary values of D and S is coded in this sequence: </div><br /><div style="margin-left: 1em;">D = k values, S = n stamps: <a href="http://oeis.org/A084193" target="_blank">Sequence A084193</a></div><div style="text-align: left;"><br /></div><div style="text-align: left;">Readers still in search of a little thrill may enjoy recent reflections on some old magic and the recycling of the principle from the first <i>Card Colm</i> over at the <a href="http://www.huffingtonpost.com/colm-mulcahy/it-was-50-years-ago-today_b_4734538.html" target="_blank"><i>Huffington Post</i></a>'s "Magical History Tour." </div><div style="text-align: left;"><br /></div><div style="text-align: left;">"The Alumni Midterms" is an anagram of "Three Summand Limit" (so is "The Untrimmed Mails"), and "Aha! Little Poet" is an anagram of "Philo Tate Tale!" </div>Mathematical Association of Americahttp://www.blogger.com/profile/10559021045290192742noreply@blogger.com0tag:blogger.com,1999:blog-1124742229498315339.post-78896154763235365722013-12-31T15:42:00.001-05:002013-12-31T15:42:43.464-05:00X-Ray Vision<link href="http://www.maa.org/Style/2ndgen.css" rel="stylesheet" type="text/css"></link> We embark on the <a href="http://www.martin-gardner.org/" target="_blank">centennial year</a> of <a href="http://www.huffingtonpost.com/colm-mulcahy/martin-gardner_b_4125273.html" target="_blank">Martin Gardner, the best friend mathematics ever had</a>, with a seemingly-impossible, X-ray vision effect we feel he would have enjoyed. <a href="http://blogs.scientificamerican.com/guest-blog/2013/10/29/celebrations-of-mind-honor-maths-best-friend-martin-gardner/" target="_blank">Gardner's extensive legacy</a> inspired the theme of <a href="http://www.mathaware.org/" target="_blank">Mathematics Awareness Month 2014</a>. The <a href="http://jointmathematicsmeetings.org/meetings/national/jmm2014/2160_maasess#sthash.uP4Fq3Ap.dpuf" target="_blank">MAM2014 poster</a> will be unveiled at 11:30am on Thursday 16th January 2014, at 11:30 a.m. at the MAA Pavilion in the exhibit hall at the Joint Math Meetings in Baltimore. <br /><br />The card effect below is based on a clever probability-defying principle involving <a href="http://blog.wolframalpha.com/2011/11/29/working-with-permutations-in-wolframalpha" target="_blank">permutation cycle decomposition</a>, which was learned from a boxes and prisoners puzzle popularized by Pete Winkler of Dartmouth College. Appropriately enough, Pete introduced it at <a href="http://mat.tepper.cmu.edu/blog/?p=148" target="_blank">Gathering 4 Gardner 7</a> in Atlanta in 2006. Much of what follows below grew out of discussions with Dan Kalman of American University; indeed it was Dan's idea to migrate this lovely puzzle to the card setting. <br /><br /><h2><span style="font-size: large;">Inexact Iffy Verso</span></h2><br />Twelve cards from a borrowed deck of cards are jumbled by an audience member, who then deals them into a neat face-up three by four array—something like what is shown here—while you avert your eyes for a while so that you do not see any card faces. Any Ace to Queen in mixed suits are used, but don't draw attention to that. Do emphasize that the cards were borrowed and mixed, so that there is no chance of marked cards being used. <br /><br /><center><img src="http://www.maa.org/sites/default/files/images/columns/colm/card05.gif" height="90" /><img src="http://www.maa.org/sites/default/files/images/columns/colm/card14.gif" height="90" /><img src="http://www.maa.org/sites/default/files/images/columns/colm/card06.gif" height="90" /><img src="http://www.maa.org/sites/default/files/images/columns/colm/card49.gif" height="90" /><br /><img src="http://www.maa.org/sites/default/files/images/columns/colm/card33.gif" height="90" /><img src="http://www.maa.org/sites/default/files/images/columns/colm/card11.gif" height="90" /><img src="http://www.maa.org/sites/default/files/images/columns/colm/card03.gif" height="90" /><img src="http://www.maa.org/sites/default/files/images/columns/colm/card43.gif" height="90" /><br /><img src="http://www.maa.org/sites/default/files/images/columns/colm/card08.gif" height="90" /><img src="http://www.maa.org/sites/default/files/images/columns/colm/card22.gif" height="90" /><img src="http://www.maa.org/sites/default/files/images/columns/colm/card39.gif" height="90" /><img src="http://www.maa.org/sites/default/files/images/columns/colm/card28.gif" height="90" /></center><br />Have any four cards of different suits singled out, and their names written down on a sheet of paper which is then folded over, before the cards are all turned face down. For the sake of argument, let's suppose 4H, JS, 2C, are 8D are the chosen ones. Finally, you turn back to face your audience. <br /><br />"These twelve cards from a borrowed deck have been randomized," you say, adding, "Only those of you who viewed them before they were turned face down know where anything is. I'd like to introduce you to four special friends of mine, who have a knack for finding things on demand. Actually they have x-ray vision." Four people enter the room. In reality, they are accomplices of yours who've agreed in advance on a mathematical strategy for locating any cards they are asked to. <br /><br />Continue, "If one of my friends were to look for the Heart written on the sheet, and we allowed her to peek at up to nine of the twelve cards, she'd have a 75% chance of finding it. If a second of my friends did the same thing for the Spade on the list, and he hadn't seen the outcome of the first search—let's assume the cards always start off in the same neat array—that would be an independent event. Hence, the chance that <i>both</i> of my friends would succeed would be 3/4 squared, which is only about 56%. My other two friends seek the remaining two cards noted—the Club and Diamond—in the same way. For all four to succeed would be even less likely, since 3/4 to the power of four is only about 32%. Yet, that's exactly what I think will happen, about three quarters of the time.'' <br /><br />Pause to let that sink in, before summarizing, "Yes, I'm saying that if four people independently do something with a 75% chance of success, all four will succeed almost 75% of the times. We're re-writing the rules of probability here. The secret is simple: They're really using their x-ray vision to gradually steer them to the correct cards. It's not perfect, but it's much more impressive that leaving things up to mere chance." <br /><br />One of your friends steps forward, you introduce her and add that she's very good at finding specific Hearts via x-ray vision. The rest of your friends turn away. Stress that none of the four gets to see the results of anyone else's peeking. <br /><br />The audience member looks at the sheet, and shows your friend the Heart on the list, the 4H. Your first friend peeks at up to nine cards in the array, stopping as soon as she finds the 4H. If she fails, you admit defeat and start all over, having the cards re-shuffled and re-dealt. If she succeeds, have your second friend shown the Spade on the list, and continue if he too succeeds in finding his target card. If your friends all peeked at random, then as explained above, the chance they'd all succeed would be only 32%. Here's the big surprise: <br /><br /><center><em>It turns out that there is a way to guarantee that all four <br />of your friends succeed about 73% of the time, on average. </em></center><br /><br />Here is the strategy, explained in terms of the specific card array above. It is indeed the result of a kind of x-ray vision: a mathematically-enhanced vision which allows those in possession of this superpower to "see through" an array of card backs and locate a desired card more easily than seems reasonable. <br /><br />First, let's agree to associate each position in a three by four array with a specific number 1-12. We suggest an easy-to-remember but not too obvious assignment such as this "reverse-Z": <br /><br /><center> 04 03 02 01 <br />05 06 07 08 <br />12 11 10 09 </center><br />The values of the cards which end up in those positions can be thought of as a permutation of the numbers 1 to 12. The array shown earlier is reproduced here for convenience. In practice, the cards are all face down. It's all about the card positions and values, suits play no role at all; the earlier fussing about selecting a card of each suit to locate is just a distraction from what's really going on. The "reverse-Z" convention, however, serves a real purpose: it should make it less likely for spectators to catch on to the peeking strategy soon to be explained. <br /><br /><center><img src="http://www.maa.org/sites/default/files/images/columns/colm/card05.gif" height="90" /><img src="http://www.maa.org/sites/default/files/images/columns/colm/card14.gif" height="90" /><img src="http://www.maa.org/sites/default/files/images/columns/colm/card06.gif" height="90" /><img src="http://www.maa.org/sites/default/files/images/columns/colm/card49.gif" height="90" /><br /><img src="http://www.maa.org/sites/default/files/images/columns/colm/card33.gif" height="90" /><img src="http://www.maa.org/sites/default/files/images/columns/colm/card11.gif" height="90" /><img src="http://www.maa.org/sites/default/files/images/columns/colm/card03.gif" height="90" /><img src="http://www.maa.org/sites/default/files/images/columns/colm/card43.gif" height="90" /><br /><img src="http://www.maa.org/sites/default/files/images/columns/colm/card08.gif" height="90" /><img src="http://www.maa.org/sites/default/files/images/columns/colm/card22.gif" height="90" /><img src="http://www.maa.org/sites/default/files/images/columns/colm/card39.gif" height="90" /><img src="http://www.maa.org/sites/default/files/images/columns/colm/card28.gif" height="90" /></center><br />The first person—who hopes to locate the 4H—starts by peeking at the 4th card according to the above convention, namely, the 6H. That suggests that for her second try she peeks at the 6th card on display, which is the QH. That in turn points to the 12th card for her third try, which is the 9H. For her fourth try she peeks at the 9th card, which is the 3D, then for her fifth try she peeks the 3rd card, which is the 2C, then for her sixth try she peeks at the 2nd card, which is the 7H. Her seventh try is the 7th card on display, which is the desired 4H. She has succeeded within nine tries.<br /><br />The cards are restored to a neat face-down array and the second person now views the scene, having not witnessed the first person's peeks. He hopes to locate the JC, and hence starts by peeking at the 11th card, which in the above convention is the 10C. That suggests that for his second try he next peek at the 10th card on display, which is the AD. That points to the 1st card for her third try, which is the desired JC. He too has succeeded, as hoped for. <br /><br />The third person hopes to locate the 2C, and starts by peeking at the 2nd card, which is the 7H. It can be checked that if the procedure outlined above is followed, the 2C is arrived at on the seventh peek. The fourth person hopes to locate the 8D, and starts by peeking at the 8th card, which is the 5S. The 5th card is the 8D, so the target card is arrived at on the second peek. <br /><br />For the specific array depicted above, we can therefore say: <br /><br /><em></em><br /><center><em>All four succeeded in finding their cards within seven tries,<br /> by starting with a peek at the card at the position corresponding<br /> to the target card's value, and then "following the trail." </em></center><em></em> <br /><br />Does it always work, within nine tries? Definitely not! But it works more often than not. The display above corresponds to the permutation that sends 1, 2, 3, ..., 12, to 11, 7, 2, 6, 8, 12, 4, 5, 3, 1, 10, 9, respectively. It can be checked that its cycle decomposition is (1 11 10) (2 7 4 6 12 9 3) (5 8): a product of a 3-cycle, a 7-cycle and a 2-cycle (the last being a transposition or inversion). Here 3 + 7 + 2 = 12, and there is a natural connection with the numbers of tries the four people needed above: 7, 3, 7, and 2, when seeking cards of values 4, 11, 2 and 8, respectively. The 4H and 2C are in the 7-cycle, the JS is in the 3-cycle, and the 8D is in the transposition. For this array, all twelve cards are findable within seven peeks, the AD and 10C only need three peeks, and the 5S only needs two. Moreover, had the 5S and 8D above been switched, each would have been discovered on the first peek, as the cycle decomposition would then have been (1 11 10) (2 7 4 6 12 9 3) (5) (8). <br /><br />What can go wrong? Consider the next array, which only differs from the one depicted above by having the 9H and 10C switched. <br /><br /><center><img src="http://www.maa.org/sites/default/files/images/columns/colm/card05.gif" height="90" /><img src="http://www.maa.org/sites/default/files/images/columns/colm/card14.gif" height="90" /><img src="http://www.maa.org/sites/default/files/images/columns/colm/card06.gif" height="90" /><img src="http://www.maa.org/sites/default/files/images/columns/colm/card49.gif" height="90" /><br /><img src="http://www.maa.org/sites/default/files/images/columns/colm/card33.gif" height="90" /><img src="http://www.maa.org/sites/default/files/images/columns/colm/card11.gif" height="90" /><img src="http://www.maa.org/sites/default/files/images/columns/colm/card03.gif" height="90" /><img src="http://www.maa.org/sites/default/files/images/columns/colm/card43.gif" height="90" /><br /><img src="http://www.maa.org/sites/default/files/images/columns/colm/card22.gif" height="90" /><img src="http://www.maa.org/sites/default/files/images/columns/colm/card08.gif" height="90" /><img src="http://www.maa.org/sites/default/files/images/columns/colm/card39.gif" height="90" /><img src="http://www.maa.org/sites/default/files/images/columns/colm/card28.gif" height="90" /></center><br />This new display corresponds to the permutation that sends 1, 2, 3, ..., 12, to 11, 7, 2, 6, 8, 12, 4, 5, 3, 1, 9, 10, respectively. Its cycle decomposition turns out to be (1 11 9 3 2 7 4 6 12 10) (5 8): a product of a 10-cycle and a transposition. Hence ten of these cards, specifically the AD, JS, 9H, ..., 10C, will require ten peeks to locate using the suggested strategy. <br /><br />The moral is that some arrays, namely those avoiding cycles of length greater than nine, will guarantee 100% success, whereas others will lead to certain failure. The question then arises, how many (or what fraction) are there of each type? <br /><br />On page 3 of Pete Winkler's <a href="http://www.math.dartmouth.edu/~pw/solutions.pdf" target="_blank">"Seven Puzzles You Think You Must Not Have Heard Correctly,"</a> a simple counting argument is given to show that the probability of a uniformly random permutation of 1-12 having a k-cycle (for k > 6) in its cycle decomposition is 1/k. Having such a long cycle rules out the possibility of having another, since the cycle lengths sum to 12. Hence, it follows that the probability of a random permutation of 1-12 having a 10-cycle, 11-cycle or 12-cycle is 1/10 + 1/11 + 1/12, which is roughly 0.2742. Thus, we can assert: <br /><br /><em></em><br /><center><em>The probability of any number of people all finding pre-assigned cards <br />of different values from a random array of 1-12, within nine tries,<br /> using the suggested strategy, is 1 - 1/10 - 1/11 - 1/12, or about 73%. </em></center><em></em><br /><br />It's even more impressive if more than four people are involved, since it beats the odds more convincingly, but it's also too time consuming. The "one of each suit" approach taken above is just an attempt to keep audience interest up for four rounds of peeking. <br /><br /><h2><span style="font-size: large;">Secondly, It's As Easy As ABC</span></h2><br /> We now suggest an improvement on the above: a similar effect which can be pulled off with 100% certainty, but allowing fewer peeks. The probability of any number of people all finding their pre-assigned cards of different values from a random array of 1-12, within six tries, using the suggested strategy, goes down to 1 - 1/7 - 1/8 - 1/9 - 1/10 - 1/11 - 1/12, or about 35%. This is the setting of the problem adapted from Pete Winkler; allowing only half of the cards to be peeked at. It's remarkable that the probability of success is so much higher than the chances of four people finding all of their cards by just peeking randomly, which is (1/2)^4, or about 6%. <br /><br />A way to ensure success every time for your four friends is to control the cycle structure of the initial array permutation. For instance, with only six peeks permitted, it would help if we could somehow arrange that there be a 6-cycle, as then there couldn't also be a longer one. To do this we need to change the rules a bit, and be able to think very fast on our feet. <br /><br />Above we saw how a single switch of two cards turned a 7-cycle and a 3-cycle into an undesirable 10-cycle. The very same kind of switch can be used to break up a long cycle into two more desirable shorter ones. So suppose we proceed as before, throwing in a comment such as, "Mix the cards all you want, and deal them into a three by four grid, face up. Switch pairs of cards over and over to make sure they're really mixed up. Then I'll do one more switch for good luck." This time around, you get to see the card faces of course. <br /><br />If your last switch is done with great care, the final array will not have any cycles longer than six, and total success will follow. It's important to do this before you have the four target cards written down, to allay suspicions that your switch is related to those selections. Nevertheless, human psychology being what it is, it's likely that the cards you switch will not be chosen as two of the four to be found! People will also worry here that you are somehow communicating information gleaned from your viewing the cards to your friends; this is not so, once the cards are all turned face down the four target cards are located solely on the basis of the peeks. <br /><br />Here's an example. Suppose that the audience member mixes the twelve cards and deals them into a three by four array, then does several card switches, leading to this display: <br /><br /><center><img src="http://www.maa.org/sites/default/files/images/columns/colm/card49.gif" height="90" /><img src="http://www.maa.org/sites/default/files/images/columns/colm/card11.gif" height="90" /><img src="http://www.maa.org/sites/default/files/images/columns/colm/card33.gif" height="90" /><img src="http://www.maa.org/sites/default/files/images/columns/colm/card43.gif" height="90" /><br /><img src="http://www.maa.org/sites/default/files/images/columns/colm/card39.gif" height="90" /><img src="http://www.maa.org/sites/default/files/images/columns/colm/card08.gif" height="90" /><img src="http://www.maa.org/sites/default/files/images/columns/colm/card05.gif" height="90" /><img src="http://www.maa.org/sites/default/files/images/columns/colm/card14.gif" height="90" /><br /><img src="http://www.maa.org/sites/default/files/images/columns/colm/card22.gif" height="90" /><img src="http://www.maa.org/sites/default/files/images/columns/colm/card03.gif" height="90" /><img src="http://www.maa.org/sites/default/files/images/columns/colm/card28.gif" height="90" /><img src="http://www.maa.org/sites/default/files/images/columns/colm/card06.gif" height="90" /></center><br />This display corresponds to the permutation that sends 1, 2, 3, ..., 12, to 5, 8, 12, 11, 1, 9, 6, 2, 7, 3, 4, 10, which has cycle decomposition (1 5) (2 8) (3 12 10) (4 11) (6 9 7). This needs no adjustment—every card is findable within three peeks—but for the sake of consistency, switch any two cards within any of the five cycles shown; it's still guaranteed to lead to success. <br /><br />Here's another example. Suppose that this is what you are faced with: <br /><br /><center><img src="http://www.maa.org/sites/default/files/images/columns/colm/card03.gif" height="90" /><img src="http://www.maa.org/sites/default/files/images/columns/colm/card39.gif" height="90" /><img src="http://www.maa.org/sites/default/files/images/columns/colm/card11.gif" height="90" /><img src="http://www.maa.org/sites/default/files/images/columns/colm/card06.gif" height="90" /><br /> <img src="http://www.maa.org/sites/default/files/images/columns/colm/card05.gif" height="90" /><img src="http://www.maa.org/sites/default/files/images/columns/colm/card33.gif" height="90" /><img src="http://www.maa.org/sites/default/files/images/columns/colm/card28.gif" height="90" /><img src="http://www.maa.org/sites/default/files/images/columns/colm/card49.gif" height="90" /><br /> <img src="http://www.maa.org/sites/default/files/images/columns/colm/card08.gif" height="90" /><img src="http://www.maa.org/sites/default/files/images/columns/colm/card22.gif" height="90" /><img src="http://www.maa.org/sites/default/files/images/columns/colm/card14.gif" height="90" /><img src="http://www.maa.org/sites/default/files/images/columns/colm/card43.gif" height="90" /></center><br />This corresponds to the permutation that sends 1, 2, 3, ..., 12, to 7, 12, 1, 4, 6, 8, 3, 11, 5, 2, 10, 9, which has cycle decomposition (1 7 3) (2 12 9 5 6 8 11 10) (4). This has an 8-cycle, which we now consider undesirable. Switching the final 10C with the midstream 5S turns out to break up the 8-cycle into the two 4-cycles (2 12 9 10) and (5 6 8 11). <br /><br />Can something like this be done in general? Namely, the detection and breaking up of a too-long cycle? Yes, here's a better way than that done above, courtesy of Dan Kalman, which avoids working out the full cycle decomposition first. Mentally follow the cycle from the AD until it either ends or goes past a sixth card. If the latter, swap the seventh card in the cycle with the Ace. If, on the other hand, the Ace-generated cycle ends too early, mentally follow the cycle from the 2C (or the lowest-valued one that was not in the first cycle), and this time, if you reach a seventh card, simply switch it with the 2C. This forces a 6-cycle, so that as mentioned above, it doesn't matter what the rest of the cycle structure is. <br /><br />If there <em>is</em> a too-long cycle in the initial arrangement, the chances of finding it in one or two tries as just suggested is high. Otherwise, i.e., if you don't find any long cycles, you can swap any two cards within a cycle you've already examined. <br /><br />Applying this to the last example above, we'd start decomposing as (1 7 3) (2 12 9 5 6 8 11 ...) and switch the JS and 2C. As a result, we'd change the given arrangement to one whose cycle decomposition is (1 7 3) (2 12 9 5 6 8) (4) (10 11), effectively breaking up an 8-cycle into a 6-cycle and a transposition. <br /><br />"Inexact Iffy Verso" is an anagram of "X-Ray Vision Effect," and "Secondly, It's As Easy As ABC" is an anagram of "It's As Easy As No Bad Cycles." <br /><br />Colm will do mathemagic with card demonstrations at book signings for his new <a href="http://www.crcpress.com/product/isbn/9781466509764" target="_blank"><i>Mathematical Card Magic: Fifty-Two New Effects</i></a> at the CRC Press booth at 3pm on both Thursday 16th and Friday 17th January, at the <a href="http://jointmathematicsmeetings.org/meetings/national/jmm2014/2160_exhibits" target="_blank">2014 Joint Mathematics Meetings</a> in Baltimore. Readers attending this meeting may also wish to drop by the <a href="http://blogs.scientificamerican.com/guest-blog/2013/10/29/celebrations-of-mind-honor-maths-best-friend-martin-gardner/" target="_blank">Martin Gardner</a>Centennial booth (number 629, right across from the MAA pavilion).Mathematical Association of Americahttp://www.blogger.com/profile/10559021045290192742noreply@blogger.com1tag:blogger.com,1999:blog-1124742229498315339.post-67869260794850691282013-10-31T12:28:00.000-04:002013-10-31T12:37:48.783-04:00The Sequence I Desire. Magic: When Divided, No RemainderOn 21 October 2013, Martin Gardner, <a href="http://www.huffingtonpost.com/colm-mulcahy/martin-gardner_b_4125273.html"> the best friend mathematics ever had</a>, would have turned 99. <i>Card Colm</i> was launched <a href="http://www.maa.org/community/maa-columns/past-columns-card-colm/low-down-triple-dealing">here</a> back in Oct 2004, to honor his 90th birthday. <a href="http://www.maa.org/community/maa-columns/past-columns-card-colm/a-magic-timepiece-influenced-by-martin-gardner">Other birthdays</a> of his have been causes for <a href="http://blogs.scientificamerican.com/guest-blog/2013/10/29/celebrations-of-mind-honor-maths-best-friend-martin-gardner/">celebration</a> too. So it seems appropriate, as Martin and the <i>Card Colm</i> he inspired enter their 100th and 10th years, respectively, that this month's offering is based on something learned from of a good friend of Gardner's, <a href="http://en.wikipedia.org/wiki/Irving_Joshua_Matrix">Dr. Irving Joshua Matrix</a>, the greatest numerologist the world has ever known. <br /><br /><h2><span style="font-size: large;">The $36 Gamble</span></h2>Start by addressing your audience with words along the lines of, "We all know how to tell if a number is divisible by 2, 3, 5 or 9. It's also not hard to do in the case of division by 4, 6 or 8. <a href="http://en.wikipedia.org/wiki/Divisibility_rule#Divisibility_by_7">Divisibility by 7</a> is trickier, of course, but don't worry, thanks to <a href="http://www.arscalcula.com/mental_math_divisibility_tests.shtml">an ingenious alternative method learned from Art Benjamin</a>, that's within reach too." <br /><br />Continue, "We'll test out those divisibility rules using the digits in a randomly chosen large number. Let's keep a calculator on hand to check our work. I need a volunteer." Pause, as somebody steps forward. "Thank you! You'll determine a nine-digit number completely by chance, using cards from any suit of your choice, after you've shuffled the cards in this deck. That number might be a multiple of 9!, which is 362880, so that it would be divisible by all the digits from 1 to 9 inclusive, but it's not so likely. Instead, we'll focus on the first digit, then the first two digits, next the first three digits, and so on, checking if there is a remainder when each of these is divided by 1, 2, 3, respectively, each time. If there is a remainder, I'll pay you that much in cash. Think of it as a reward for the work you're about to do! Let X be the total amount I pay you. Probabilists call X a random variable, because how much I pay you varies depending on the randomness of the shuffling you're about to do." <br /><br />Continue, "Of course every one-digit number is divisible by 1, so you can't win there. For the two-digit number we'll get looking at the first two digits of the nine-digit number you come up with, clearly there's a 1 in 2 chance that it will be even, in which case I'll owe you nothing, and also a 1 in 2 chance that it's odd, in which case it has remainder 1 upon division by 2, so I'll owe you $1. When we move on to the three-digit number we'll get looking at the first three digits of the nine-digit number you come up with, there's a 1 in 3 chance that it will be divisible by 3, in which case I'll owe you nothing. It's more likely to have remainder 1 or 2 when divided by 3, so I'll owe you $1 or $2. It gets more complicated as the number of digits we look at increases. At the very end, we'll check if the entire nine-digit number is divisible by 9. As before, if division by 9 leaves a remainder, say 5, then I'll give you $5. I guess, 8 times out of 9 there, I'll be paying you something." <br /><br />Put a wad of $1 bills on the table, and say, "The way I see it, in the worst case scenario, I'll have to hand over $1 + $2 + $3 + $4 + $5 + $6 + $7 + $8. As any smart child knows—you don't have to have the brains of a young Gauss to work this out—that adds up to $9 x 4 = $36. I went to the bank this morning and withdrew exactly that much money, just in case, in $1 bills. Your goal is to get as much of it as you can. There are some interesting mathematical questions, such as, how much can you expect to win on average, and how much might your winning total vary overall? Let's leave those for the probabilists to worry about. You get one shot at this. What can go wrong? You can't lose!" <br /><br /><h2><span style="font-size: large;">Beating the Odds Gods</span></h2>A deck of cards is produced, and its faces flashed to the audience to show that it's well mixed. The volunteer is asked to name any suit, as you split the cards into four face-down piles. Let's suppose she says "Hearts." Now, have her shuffle those piles together. Those can be three riffle shuffles—starting with two piles at a time, twice, then shuffling the resulting half decks together—or the obvious four-pile extension of the triple rosette shuffle below, introduced <a href="http://cardcolm-maa.blogspot.com/2013/08/rosette-shuffling-multiple-piles.html">here the last time</a>. <br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="http://1.bp.blogspot.com/-S5KXcKoRceA/UiXqJHLbKbI/AAAAAAAAIMI/BEsdTACEtHY/s1600/ThreeRosette1.JPG" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="http://1.bp.blogspot.com/-S5KXcKoRceA/UiXqJHLbKbI/AAAAAAAAIMI/BEsdTACEtHY/s1600/ThreeRosette1.JPG" width="125" /></a><a href="http://1.bp.blogspot.com/-hYRs3034WfM/UiXqI0DC0JI/AAAAAAAAIMQ/HACTz3bdnEk/s1600/ThreeRosette2.JPG" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="http://1.bp.blogspot.com/-hYRs3034WfM/UiXqI0DC0JI/AAAAAAAAIMQ/HACTz3bdnEk/s1600/ThreeRosette2.JPG" width="125" /></a><a href="http://3.bp.blogspot.com/-lpX3Pg69RXs/UiXqI9No-8I/AAAAAAAAIMM/_qRVXAwXGdM/s1600/ThreeRosette3.JPG" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="http://3.bp.blogspot.com/-lpX3Pg69RXs/UiXqI9No-8I/AAAAAAAAIMM/_qRVXAwXGdM/s1600/ThreeRosette3.JPG" width="125" /></a><a href="http://4.bp.blogspot.com/-AovCeMVkPyQ/UiXqJyw3RfI/AAAAAAAAIMg/9VVWqwJsAYQ/s1600/ThreeRosette4.JPG" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="http://4.bp.blogspot.com/-AovCeMVkPyQ/UiXqJyw3RfI/AAAAAAAAIMg/9VVWqwJsAYQ/s1600/ThreeRosette4.JPG" width="125" /></a></div><span class="Apple-style-span" style="-webkit-text-decorations-in-effect: underline; color: #0000ee;"></span> <br />Take the cards back and fan them face up again so everyone can see that they are now even more jumbled. Say, "We only need the Hearts of single-digit values, namely the Ace to 9," as you openly pull those out in the order in which they occur, to form a new face-down pile. Shuffle the rest of the deck one last time, and set those cards aside. Announce, "Here they are, the nine Hearts we need, your chosen suit in the random order determined by your shuffling." Lay them out in a face-up row, resulting in a display such as this: <br /><br /><center><img src="http://www.maa.org/sites/default/files/images/columns/colm/card02.gif" height="75" /><img src="http://www.maa.org/sites/default/files/images/columns/colm/card07.gif" height="75" /><img src="http://www.maa.org/sites/default/files/images/columns/colm/card13.gif" height="75" /><img src="http://www.maa.org/sites/default/files/images/columns/colm/card05.gif" height="75" /><img src="http://www.maa.org/sites/default/files/images/columns/colm/card04.gif" height="75" /><img src="http://www.maa.org/sites/default/files/images/columns/colm/card03.gif" height="75" /><img src="http://www.maa.org/sites/default/files/images/columns/colm/card06.gif" height="75" /><img src="http://www.maa.org/sites/default/files/images/columns/colm/card01.gif" height="75" /><img src="http://www.maa.org/sites/default/files/images/columns/colm/card08.gif" height="75" /></center><br />With a piece of paper quickly cover up all all but the first card, commenting that 3 is of course divisible by 1 with no remainder. Next, slide the piece of paper to expose the eight, adding, "Now I see 38, which is even. Since there is no remainder upon division by 2, I don't owe you anything yet. Now slide the piece of paper to expose the Ace. Say, "Since the digits of 381 add up to 12, that's divisible by 3. Phew! How long can my luck hold out? Slide the piece of paper over once more, to expose the six. Say, "The last two digits of 3816 are divisible by 4, so 3816 itself is divisible by 4. Amazing! Feel free to check that with this calculator." <br /><br />The next time you slide the piece of paper over, to expose the five, you end up with 38165, which is divisible by 5 since it ends in 5. Again, no cash is handed over since there's no remainder. When the next digit is exposed, you get 381654. Division by 2 yields 190827, and the digits of that number sum to 27, so it's divisible by 3, and hence 381654 is divisible by 6, without remainder. <br /><br />It's not hard to guess where this is going. When the seventh digit is exposed, you get 3816547. This is the only tricky one to deal with. Using the <a href="http://www.arscalcula.com/mental_math_divisibility_tests.shtml">Art Benjamin approach</a>, we note that since 63 is divisible by 7, then 3816547 is divisible by 7 if and only if 3816547 + 63 = 3816610 is. That, in turn, holds if and only if 381661 is divisible by 7. Since 21 is divisible by 7, then 381661 is if and only if 381661 - 21 = 381640 is, which holds if and only if 38164 is. Continuing, we see that 38164 is divisible by 7 if and only if 38164 - 14 = 38150 is divisible by 7, if and only if 3815 is, if and only if 3815 + 35 = 3850 = 7 x 550 is. So all of these numbers are divisible by 7, and there is no remainder when 3816547 is divided by 7. This too can be verified with the calculator. <br /><br />Exposure of the eighth digit reveals 38165472. Division by 2 yields 19082736, whose last two digits are 36, so that's divisible by 4 and the original number is divisible by 8. <br /><br />Say, "You have one more chance to win between $1 and $8 from me, are you ready?" The entire random nine-digit number is 381654729, whose digits sum to 45, so it's divisible by 9 without remainder. Your $36 remains on the table, untouched. You've beaten the <a href="http://aperiodical.com/2012/04/the-odds-gods-smile-on-birthdaycard-matches/">odds gods</a>and escaped unscathed. Conclude, "Weird, what are the chances of that happening? Every single time, when divided, there was no remainder! I'll ask my probabilist friends what kind of random variable X is. A very lucky one I guess, at least for me. I wonder what its standard deviation is?" Pocket the $36 on the table. <br /><br /><h2><span style="font-size: large;">Imperviously Nibbled</span></h2>The deck is of course rigged, and in such a way that the indicated handling still leads without fail to 381654729, the unique nine-digit <a href="http://en.wikipedia.org/wiki/Polydivisible_number">polydivisible number</a> using each of 1 to 9 just once. The Answers and Commentary section for Chapter 21 of <a href="http://www.cut-the-knot.org/books/matrix/flap.shtml"><i>The Magic Numbers of Dr. Matrix</i></a> reveals that while Jaime Poniachik of Buenos Aires had first posed to the author the problem of finding such an arrangement of the digits 1 to 9, it was his wife Lea Gorodisky who had invented it. <br /><br />Start by separating the deck by suits, and setting aside the sixteen cards of no interest, namely the 10s, Jacks, Queens and Kings. For each suit, arrange the Ace to 9 in order 381654729, cutting three of the resulting four piles in notably different places. In each of the four resulting piles, insert three of the Jacks, Queens and Kings randomly, spread out and aiming for good colour variation to withstand a casual glance later. Put a red-dominant twelve-card pile face down on the table, adding a 10 on top, then put a black-dominant pile on top of that, followed by two 10s, another red-dominant pile, the final 10, and then the last, black-dominant pile. <br /><br />At showtime, this carefully arranged deck can be quickly fanned face-up to the audience as you ask for a suit to be named. Split it half, seeking the two 10s in the middle for guidance; the split should be within one card of the gap between those. Pick up the first pile, saying, "Hearts, eh?" as you scan the faces once more and split into face-down quarter decks using the buried 10 as a guide. Quickly repeat for the other half deck, adding, "I'm going to ask you to shuffle these to mix them up even further." <br /><br />Whether the shuffling now done by the volunteer is riffling or rosetting, the case <i>k = 4</i> of the solitaire principle <a href="http://cardcolm-maa.blogspot.com/2013/08/rosette-shuffling-multiple-piles.html">explained here two months ago</a> comes to the rescue: <br /><ul><li>If four piles of cards, one for each suit, each running in some fixed order, are rosette shuffled together, and the cards in the resulting packet are dealt one at a time into piles separated by suit, then the original piles will be reformed, in reverse order.</li></ul>The key cards (Ace to 9) within each suit didn't start in the same order, to reduce the risk of early detection by an alert audience, but it doesn't matter. Cyclically, all is well. Upon receiving the deck back after the shuffle, while scanning and fanning again to show randomness, discretely cut anywhere between the 9 of Hearts and 3 of Hearts and reassemble the resulting two parts in reverse order. Then, when you pull out the nine desired Hearts, they will emerge in the right order. Nothing can go wrong. <br /><br />Nothing, indeed, unless you can't remember the sequence of numbers central to the whole effect. One way to come up this most magic number of Dr. Matrix, as remarked in the book referenced above, is to note a pleasing geometric pattern when the digits in question are traced out in the <a href="http://en.wikipedia.org/wiki/Magic_square">unique magic square of order 3</a>. If that's too much work, or you can't remember that magic square either, you can always <i>count on</i> the title of this column: <b>The Sequence I Desire. Magic: When Divided, No Remainder.</b> <br /><br />"Imperviously Nibbled" is an anagram of "Polydivisible Number."<br /><br />Colm is giving a <a href="http://aumathstat.org/magic/">public lecture on mathematical card magic</a> at American University, at 7pm on Fri, 8 Nov, <a href="http://www.maa.org/news/november-8-event-mathemagic-with-a-deck-of-cards">co-sponsored by the MAA</a>, after which there will be a booksigning for <a href="http://www.crcpress.com/product/isbn/9781466509764">Mathematical Card Magic: Fifty-Two New Effects</a> (AK Peters/CRC Press).Mathematical Association of Americahttp://www.blogger.com/profile/10559021045290192742noreply@blogger.com0tag:blogger.com,1999:blog-1124742229498315339.post-19280716486356027942013-08-30T08:46:00.000-04:002013-09-03T10:00:20.785-04:00Rosette Shuffling Multiple Piles<a href="http://www.crcpress.com/product/isbn/9781466509764"><i>Mathematical Card Magic: Fifty-Two New Effects</i></a> (AK Peters/CRC Press) is finally out. It has sizable overlap with the past nine year's worth of <i>Card Colm</i>s here—about 75%?—but is organized quite differently. It's also written for a wider audience and generally avoids technical language. What follows is a taster of one of the nagging questions addressed in it, first publicly raised two years ago in <a href="http://cardcolm-maa.blogspot.com/2011/08/call-for-new-shuffle-principle-need-rot.html">A Call For A New Shuffle Principle (Need Rot Sextet?)</a>. <br /><br /><h2><span style="font-size: large;">Limit Plus Peel</span> </h2>Some observations and assertions of a mathematical nature are easy, or at least routine, to generalize from two to three or beyond. Others are trickier (e.g., <a href="http://en.wikipedia.org/wiki/Fair_division#Many_players">cake cutting</a>), and a few turn out to be impossible (e.g., <a href="http://mathworld.wolfram.com/AngleTrisection.html">angle trisection using only a straightedge and compass</a>). In the August 2011 <i>Card Colm</i> mentioned above, we made an appeal for a new kind of generalization of the ever-popular Gilbreath shuffle principle, asking <br /><br /><center>Is there a way to riffle shuffle three or more piles of prearranged cards <br />and expect some order to remain, without assuming perfect interweaving? </center><br />The good news is that this month we have something to report along these lines. We can now sleep at night, although a really impressive magic application is still proving elusive. <br /><br /><h2><span style="font-size: large;">Treeless Shutoff</span></h2>First it pays to switch our focus from riffle shuffling—which in the Gilbreath context follows the dealing out of some cards from a packet to form two piles—to something equivalent to that, which has a more obvious generalization to three or more piles. We're referring to <a href="http://en.wikipedia.org/wiki/Lennart_Green">Lennart Green</a>'s rosette shuffle as depicted below. Two side-by-side piles are twirled into rosettes with the fingers before being pushed together and squared up.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="http://4.bp.blogspot.com/-X00FCs3_Zzw/UiXq732EpJI/AAAAAAAAINA/S3FNy092hrQ/s1600/Rosette1a.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="http://4.bp.blogspot.com/-X00FCs3_Zzw/UiXq732EpJI/AAAAAAAAINA/S3FNy092hrQ/s1600/Rosette1a.jpg" height="96" width="120" /></a><a href="http://2.bp.blogspot.com/-CoA4QzLLkbM/UiXq79iBqCI/AAAAAAAAIM0/jJPzcoSlzvI/s1600/Rosette2a.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="http://2.bp.blogspot.com/-CoA4QzLLkbM/UiXq79iBqCI/AAAAAAAAIM0/jJPzcoSlzvI/s1600/Rosette2a.jpg" height="96" width="120" /></a><a href="http://2.bp.blogspot.com/-V7nbWITNRzI/UiXq7-AT0VI/AAAAAAAAIM4/aJnWyGog1gg/s1600/Rosette3a.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="http://2.bp.blogspot.com/-V7nbWITNRzI/UiXq7-AT0VI/AAAAAAAAIM4/aJnWyGog1gg/s1600/Rosette3a.jpg" height="96" width="120" /></a><a href="http://3.bp.blogspot.com/-Uo63HzaRaBo/UiXq8CBSYAI/AAAAAAAAINE/LVPp9GWJgOs/s1600/Rosette4a.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="http://3.bp.blogspot.com/-Uo63HzaRaBo/UiXq8CBSYAI/AAAAAAAAINE/LVPp9GWJgOs/s1600/Rosette4a.jpg" height="96" width="120" /></a></div><br /><span class="Apple-style-span" style="-webkit-text-decorations-in-effect: underline; color: #0000ee;"></span> <br />When we say that this is equivalent to riffle shuffling we really mean that the following internal coherence or solitaire principle applies. <br /><ul><li>If two piles of cards, running Ace to King of Hearts and Ace to King of Spades, respectively, are riffle or rosette shuffled together, and the cards in the resulting packet are dealt one at a time into two piles separated by suit, then the original piles will be reformed, in reverse order. </li></ul>In other words, we'll never be faced with dealing the 7 of Hearts onto a Red card other than the 6 of Hearts. By the time we get to that 7, we can be sure that the Ace, 2, 3, 4, 5 and 6 of Hearts will already have been dealt, in that order. <br /><br /><h2><span style="font-size: large;">Sheaf Bullfighters</span></h2>In the first August edition of <i>Card Colm</i>, back in 2005, we explored the <a href="http://www.maa.org/community/maa-columns/past-columns-card-colm/the-first-norman-invasion">first (or basic) Gilbreath principle</a> from 1958, which concerns the structure retained when two piles of cards are riffle or rosette shuffled, assuming that we start with an alternating packet of some kind and then deal "about half" of the cards to the table to give rise to the two piles. Generalizing that to situations where the packet started by repeating a cyclic pattern of length greater than two leads easily and naturally to the <a href="http://www.maa.org/community/maa-columns/past-columns-card-colm/the-second-norman-invasion">second (or generalized) Gilbreath principle</a> from 1966, which we covered here in August 2006. <br /><br />In a nutshell, the Gilbreath Principle says that <br /><ul><li>If we start with a packet of <i>sm</i> cards that consists of <i>m</i> repeated stacks of a particular set of <i>s</i> cards, each set being in the same fixed order with respect to some characteristic of interest (such as color, suit, or value), and we count out some of these to the table—thereby reversing their order—and then riffle shuffle together the two resulting piles, we're sure to get a packet in which each stack of <i>s</i> cards pulled off the top contains exactly one card of each of the key types, in some order.</li></ul>The basic case is when <i>s</i> = 2. If the cards alternate Red and Black, over and over, at the outset, then the shuffled packet has the property that the cards in positions 1-2, 3-4, 5-6, etc, are always of different colors, though we can't say in which order Red and Black cards occur in each such pair. <br /><br />For the case <i>s</i> = 3, we could start with a packet consisting of trios of Spades, Diamonds, and Hearts, in that order, over and over. The shuffled packet then has the property that the cards in positions 1-3, 4-6, 7-9, etc, always consist of one each of those three suits, again in some order. When <i>s</i> = 13, starting with a packet consisting of four stacks of the thirteen card values, in the same fixed order, we end up with four clumps (the cards 1-13, 14-26, 27-39 and 40-52) consisting of the thirteen values in some mixed order. <br /><br />Lovely though all of this is—and it has spawned a ton of magic over the last half century—it's well-explored territory. What more is there to say? Persi Diaconis & Ron Graham give a complete characterization of such matters in what they call The Ultimate Gilbreath Principle on page 70 of their beautiful, inspirational and prize-winning book <em><a href="http://press.princeton.edu/titles/9510.html">Magical Mathematics: The Mathematical Ideas that Animate Great Magic Tricks</a> </em>(Princeton University Press, 2011). Some Gilbreath variations were considered here in subsequent Augusts, in <a href="http://www.maa.org/community/maa-columns/past-columns-card-colm/the-bligreath-principle">The Bligreath Principle</a> (2009) and <a href="http://cardcolm-maa.blogspot.com/2012/08/gilbreeath-shuuffling.html">Gilbreeath Shuuffling</a> (2012). Just six months ago we couldn't resist sharing a new twist on all of this due to John Hostler in <a href="http://cardcolm-maa.blogspot.com/2013/02/flushed-with-embarrassment.html">Flushed with Embarrassment</a> (February 2013). Normal Gilbreath's own long-awaited book is coming soon, from L&L Publishing. <br /><br />But there is another direction in which to turn, in search of a different kind of thrill. What if we rosette shuffle three or more piles with some simple structure? <br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="http://1.bp.blogspot.com/-S5KXcKoRceA/UiXqJHLbKbI/AAAAAAAAIMI/BEsdTACEtHY/s1600/ThreeRosette1.JPG" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="http://1.bp.blogspot.com/-S5KXcKoRceA/UiXqJHLbKbI/AAAAAAAAIMI/BEsdTACEtHY/s1600/ThreeRosette1.JPG" height="96" width="120" /></a><a href="http://1.bp.blogspot.com/-hYRs3034WfM/UiXqI0DC0JI/AAAAAAAAIMQ/HACTz3bdnEk/s1600/ThreeRosette2.JPG" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="http://1.bp.blogspot.com/-hYRs3034WfM/UiXqI0DC0JI/AAAAAAAAIMQ/HACTz3bdnEk/s1600/ThreeRosette2.JPG" height="96" width="120" /></a><a href="http://3.bp.blogspot.com/-lpX3Pg69RXs/UiXqI9No-8I/AAAAAAAAIMM/_qRVXAwXGdM/s1600/ThreeRosette3.JPG" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="http://3.bp.blogspot.com/-lpX3Pg69RXs/UiXqI9No-8I/AAAAAAAAIMM/_qRVXAwXGdM/s1600/ThreeRosette3.JPG" height="96" width="120" /></a><a href="http://4.bp.blogspot.com/-AovCeMVkPyQ/UiXqJyw3RfI/AAAAAAAAIMg/9VVWqwJsAYQ/s1600/ThreeRosette4.JPG" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="http://4.bp.blogspot.com/-AovCeMVkPyQ/UiXqJyw3RfI/AAAAAAAAIMg/9VVWqwJsAYQ/s1600/ThreeRosette4.JPG" height="96" width="120" /></a></div><div class="separator" style="clear: both; text-align: center;"><br /></div><span class="Apple-style-span" style="-webkit-text-decorations-in-effect: underline; color: #0000ee;"></span> <br />Certainly, the earlier solitaire principle extends in the obvious way: <br /><ul><li>If <i>k</i> piles of cards, running 1-<i>n</i>, representing <i>k</i> "suits," are rosette shuffled together, and the cards in the resulting packet are dealt one at a time into <i>k</i> piles separated by suit, then the original piles will be reformed, in reverse order.</li></ul><br /><h2><span style="font-size: large;">Canonical Indecencies Pix</span></h2>Now we highlight something Karl Fulves pointed out in his hard-to-find book <i>Riffle Shuffle Set-Ups</i> (1968), which saw distribution only in magic circles. The rosette shuffle wasn't on his radar screen, of course, he was thinking in the context of riffle shuffling multiple piles, say, two at a time, until he had a single packet again. Even for the case of two piles, this fact has languished in obscurity for decades. <br /><ul><li>If <i>k</i> piles of cards, running 1-<i>n</i>, representing <i>k</i> "suits," are rosette shuffled together, and the cards in the resulting packet are peeled off <i>k</i> at a time, then if the <i>j</i>th set matches in value, they have value <i>j</i>. </li></ul>In other words, if we rosette the four suits of a standard deck together, each having started in the order Ace to King, and we find that the third, seventh, and eleventh quadlets pulled off the top all match across the board, then they must consist of the 3s, 7s, and Jacks, respectively. <br /><br />In practice, this is better performed with the suits arranged in some less obvious but memorized order. For instance, suppose we use the starting arrangement 3, 5, 10, Ace, 9, Jack, 2, 8, 7, Queen, 6, 4, King, in each suit. (This is much favored by John H. Conway, and is based on the mnemonic "The Five Tenacious Boys Nicely Joke To Hated Servant Girls Sick For Absent Kings"—we've omitted Jokers.) Have an audience member twirl the four face-down suit piles and mush them together, then turn away and request that cards be peeled off four at a time and inspected. If any such quadlet matches, you are informed. If the fifth and eighth quadlets match, say, "Coincidences I can explain." Confidently announce that they are the Jacks and 8s, respectively. <br /><br />Incidentally, Fulves also has something to say about the values in any situation where the <i>j</i>th set of <i>k</i> cards contains of one of each suit (with none repeated). <br /><br /><h2><span style="font-size: large;">Arrange Wall Modish</span></h2>A year ago—and a full year after we issued the <a href="http://cardcolm-maa.blogspot.com/2011/08/call-for-new-shuffle-principle-need-rot.html">Call For A New Shuffle Principle (Need Rot Sextet?)</a>—Ron Graham graciously responded to repeated prodding by coming up with the following key breakthrough, shared here with his kind permission. <br /><ul><li>Arrange a packet in cyclic order 0, 1, 2, 0, 1, 2, .... Now split into three piles that have as their top cards, 0, 0, and 1. In other words, the cards in the three piles are in the order 0, 1, 2, 0, 1, 2, ..., 0, 1, 2, 0, 1, 2, ... and 1, 2, 0, 1, 2, 0, ... . Rosette shuffle them together, so that in the result, the relative order of the three piles is preserved. Start removing sets of three consecutive cards at a time. Then none of these three-card sets will have all values the same. </li></ul>That's not to say that three cards of the same type can't end up together, one coming from each pile, but they won't all be in any one of the triplets 1-3, 4-6, 7-10, and so on; they'd have to straddle two such triplets. More generally, Graham offered the following, which we think of as a kind of Non-Alliance Principle: <br /><ul><li>Start with a packet arranged cyclically as 0, 1, ..., , <i>s</i>-1, 0, 1, ..., <i>s</i>-1, and then break it into <i>s</i> piles, and rosette shuffle those together. If we now remove sets of <i>s</i> cards at a time from the top, and the top card of the original <i>i</i>th pile is denoted by <i>a<sub>i<sub></sub></sub></i>, then assuming the sum of the <i>a<sub>i<sub></sub></sub></i> is not 0 (mod <i>s</i>), we can be sure that none of the sets of <i>s</i> cards will have all values the same. </li></ul>For <i>s</i> = 2, this is equivalent to something we have known for a long time. It says that if we break an alternating packet into two piles whose top cards don't match and then rosette shuffle, we can be sure that the cards in positions 1-2 won't match either, and likewise neither will those in positions 3-4, 5-6, and so on. This is the basic Gilbreath principle once more: the careful splitting suggested here is a quick alternative to the usual dealing out of cards to form the two piles (a shortcut which only works for alternating packets). <br /><br />For <i>s</i> = 3, start with a packet cycling Clubs, Hearts, and Diamonds, and split it into three piles that have as their top cards Clubs, Clubs, and Hearts. Rosette shuffle, and pull cards off the top three at a time. No such triplet will consist of three cards of the same suit. The same conclusion also holds whenever the top cards of the three piles account for exactly two of the three suits in play. The principle is not saying anything when the top cards of the three piles are all the same, or account for one of each suit; but perhaps those cases yield to a different kind of analysis. <br /><br />More details—and a preliminary magic application—can be found in Chapter 8 of <a href="http://www.crcpress.com/product/isbn/9781466509764"><i>Mathematical Card Magic: Fifty-Two New Effects</i></a> (AK Peters/CRC Press, 2013). <br /><br />"Limit Plus Peel" is an anagram of "Multiple Piles," "Treeless Shutoff" is an anagram of "Rosette Shuffles," "Sheaf Bullfighters" is an anagram of "Gilbreath Shuffles," "Canonical Indecencies Pix" is an anagram of "Coincidences I Can Explain," and "Arrange Wall Modish" is an anagram of "Ronald Lewis Graham."Mathematical Association of Americahttp://www.blogger.com/profile/10559021045290192742noreply@blogger.com0tag:blogger.com,1999:blog-1124742229498315339.post-24453770845367036922013-06-27T11:55:00.000-04:002013-07-30T09:41:51.269-04:00Subtler Bracelets and Dissociative Disorders<h2><span style="font-size: large;">Things to Come</span></h2><i>Card Colm</i> has appeared here more or less every two months since <a href="http://www.maa.org/community/maa-columns/past-columns-card-colm/low-down-triple-dealing" target="_blank">October 2004</a>, with more than 52 columns now in the bag. As we approach the completion of its ninth year, we're also getting closer to North America's premier summer mathematics celebration, <a href="http://www.maa.org/mathfest">MAA MathFest</a>.<br /><br />This year it's in Hartford, CT, and at the <a href="http://www.maa.org/mathfest/cps.html#cps10"><i>Recreational Mathematics: New Problems and New Solutions</i></a> session there on Thursday, August 1, there's a talk on "Fitch Cheney's Five Card Trick for Four or Three Cards"—which is appropriate, as <a href="http://www.jstor.org/discover/10.2307/2319595">Cheney</a> spent much of his professional life in the department of mathematics at the University of Hartford. The four-card version has been published twice by the MAA, <a href="http://www.maa.org/community/maa-columns/past-columns-card-colm/fitch-four-glory" target="_blank">here</a>. The three-card take on this was developed on the way to MathFest 2012 in Madison last August, and was performed live there a few days later at the end of an MAA minicourse on mathematical card magic. The Hartford presentation will mark its debut with explanation. (It's scheduled to appear in <a href="http://www.maa.org/Mathhorizons/"><i>Math Horizons</i></a> in the first half of 2014.)<br /><br />MathFest also sees the appearance of the 380-page full color <a href="http://www.crcpress.com/product/isbn/9781466509764"><i>Mathematical Card Magic: Fifty-Two New Effects</i></a> (A K Peters), along with two book signing opportunities in the exhibtion hall (Thursday and Friday at 3pm). This volume actually contains more than 52 effects, along with an equal number of new mathemagical principles—but they are not in a natural one-to-one correspondence. Despite the coincindence of their also having been just as many <i>Card Colm</i>s over the years, those aren't aligned with the effects in the book either. Yes, there is overlap—about three-quarters of the material?—but the book is organized differently, and is almost a grave of diamonds. It's also written for a more general audience and mostly eschews technical mathematical language.<br /><h2></h2><h2><span style="font-size: large;">Subtler Bracelets</span></h2>In the June 2008 <i>Card Colm</i> <a href="http://www.maa.org/community/maa-columns/past-columns-card-colm/sum-rich-circulants" target="_blank">Sum-Rich Circulants</a>we continued a thread on bracelet beads started the previous year. Specifically, we focused on the <b>g4g8 bracelet</b> obtained by joining the ends of<br /><br /><center>[ 8 5 4 1 7 6 3 2 ]. </center><br />Here's a good card incarnation: <br /><br /><center> <table border="0" colspan="3" style="height: 25px; width: 500px;"> <tbody><tr><td align="center"><table border="" style="width: 25%px;"></table><table border="0" colspan="13" style="height: 25px; width: 15%px;"><tbody><tr><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td><img src="http://www.maa.org/sites/default/files/images/columns/colm/card39.gif" height="80" /> </td><td></td><td></td><td></td><td></td><td></td><td><img src="http://www.maa.org/sites/default/files/images/columns/colm/card19.gif" height="80" /></td> <td></td><td></td><td></td> </tr><tr><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td> <td></td></tr><tr><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td> <td></td> </tr><tr><td><img src="http://www.maa.org/sites/default/files/images/columns/colm/card42.gif" height="80" /> </td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td> <td><img src="http://www.maa.org/sites/default/files/images/columns/colm/card05.gif" height="80" /> </td> </tr><tr><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td> <td></td> </tr><tr><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td> <td></td> </tr><tr><td><img src="http://www.maa.org/sites/default/files/images/columns/colm/card04.gif" height="80" /> </td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td> <td><img src="http://www.maa.org/sites/default/files/images/columns/colm/card41.gif" height="80" /> </td> </tr><tr><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td> <td></td></tr><tr><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td> <td></td> </tr><tr><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td><img src="http://www.maa.org/sites/default/files/images/columns/colm/card20.gif" height="80" /> </td><td></td><td></td><td></td><td></td><td></td><td><img src="http://www.maa.org/sites/default/files/images/columns/colm/card27.gif" height="80" /></td> <td></td><td></td><td></td> </tr><tr><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td> <td></td></tr><tr><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td> <td></td> </tr></tbody></table></td></tr><tr></tr></tbody></table></center>Counting out 1, 2, ..., 8, reveals a "suitable" geometric pattern; classic cycling CHaSeD order is used. Moreover, this card display can be viewed as a capital omega (Ω), which brings to mind the word "alphabetical"—and amazingly, <i>Eight, Five, Four, One, Seven, Six, Three, Two</i> are indeed in that easy-to-remember order. <br /><br />Here's the magic: plant these cards in order on the top of a deck and maintain them there throughout some fair-seeming shuffling, before dealing them face down in a circle. Have three adjacent cards peeked at and remembered by different spectators, while you turn away, and have those values summed. Upon being told this total you name all three selected cards. The reason is that this bracelet is <i>sum-rich</i> for triples: the eight possible sums of three adjacent card values are distinct. In fact, we get the numbers 17, 10, 12, 14, 16, 11, 13, 15, which are the eight consecutive numbers 10, 11, 12, ..., 17 in a special order. <br /><br />This array first saw the light of day at the G4G8 conference in Atlanta in March 2008. Four years later, at the G4G10 conference, mathematician <a href="http://orion.math.iastate.edu/butler/" target="steve">Steve Butler</a>unveiled what we call the <b>g4g10 bracelet</b>, obtained by joining the ends of <br /><br /><center>[ 1 3 4 5 9 10 6 7 8 2 ]. </center><br /><br />Not only is this sum-rich for three adjacent beads, it's easily checked that it's also sum-rich for two adjacent beads. (The latter property doesn't hold for the <b>g4g8 bracelet</b> [8 5 4 1 7 6 3 2], as its double sums are 13, 9, 5, 8, 13, 9, 5, and 10.) <br /><br />But wait, there's more: Butler's <b>g4g10 bracelet</b> is magical in a new and unanticipated way. The possible sums for adjacent triples and doubles are not only as large as they could be, as sets, they also have no overlap, being the sets {8, 12, 18, 24, 25, 23, 21, 17, 11, 6} and {4, 7, 9, 14, 19, 16, 13, 15, 10, 3}, respectively. Hence, in a card implementation as above, with 10 specific cards used and their suits memorized, you can deal these face down in a circle before turning away and asking that any two <i>or</i> three spectators select adjacent cards and reveal the value total to you. Without even knowing how many people were involved, you can reveal all. Pretty impressive, eh? Thanks to Steve Butler for sharing his wonderful discovery and allowing us to pass it on.<br /><h2></h2><h2><span style="font-size: large;">Dissociative Disorders</span></h2>In the February 2008 <i>Card Colm</i> <a href="http://www.maa.org/community/maa-columns/past-columns-card-colm/additional-certainties" target="_blank">Additional Certainties</a>, we broke rank with ordered beads on bracelets, abandoned the adjacency assumption, and considered sets such as {1, 2, 3, 5, 8, 13}, {1, 3, 4, 7, 11}, and {3, 4, 6, 8, 12}, which have the the property that if <i>any</i> two numbers from any one of them are added, then you can deduce what the numbers are from the total. In most cases it also works for three numbers, but it in general you'll also need to know how many values are being summed. For instance, if you are told that (Lucas) numbers from the second set sum to 8, but you don't know whether two or three were involved, then you're in trouble, as it could be 1 + 7 or 1 + 3 + 4. (In the June 2009 <i>Card Colm</i> <a href="http://www.maa.org/community/maa-columns/past-columns-card-colm/two-summer-difference-certainties" target="_blank">Two Summer Difference Certainties</a>, we extended these ideas to a wider class of sets, but the same ambiguity remained.)<br /><br />It's natural to ask if something like Butler's g4g10 bracelet exists in the set context, for card values. Let's go all the way and seek sets of <i>k</i> numbers in the range 1-13 with the property that <i>all</i> 2<sup>k</sup>-1 nonempty subsets have distinct sums. Trivial examples are {1, 2, 4, 8} (powers of 2) and {1, 3, 9} (powers of 3), and the more interesting {1, 3, 6, 13}, in which each value is 1 more than twice the previous one. There are many examples of size 4; find some more. <br /><br />Now find one of size 5. How many such examples are there? Are there more if we relax the demands and only ask that the 2-sums and 3-sums be distinct (and all different from one another)? Can we find larger sets if we allow the use of negative numbers too (represented by Red cards, as opposed to Blacks for positive ones)? <br /><br />The upshot is that once suits are also decided upon, five cards can be planted at the top of a deck—maintained there throughout some shuffling—then dealt face down in a circle, before you turn away and ask that any number of cards be peeked at and remembered. Once the sum is announced, you can figure out just how many numbers are involved, and then name all of the selected cards. <br /><br />The existence of such sets of numbers—they are known in the business as <i>dissociated</i> sets—was brought to our attention earlier this month by Neil Calkin of Clemson University. More details can be found in the Coda of <a href="http://www.crcpress.com/product/isbn/9781466509764"><i>Mathematical Card Magic: Fifty-Two New Effects</i></a> (A K Peters), to be published August 2013. <br /><br />"Subtler" is an anagram of "Butler's" and "a grave of diamonds" is an anagram of "devoid of anagrams." <br /><br />Mathematical Association of Americahttp://www.blogger.com/profile/10559021045290192742noreply@blogger.com2tag:blogger.com,1999:blog-1124742229498315339.post-78875320158307272072013-04-30T11:57:00.000-04:002013-07-30T10:50:08.672-04:00Never Forget a Face (Double-Dealing with a Difference)<div class="separator" style="clear: both; text-align: center;"></div><h2><span style="font-size: large;">Low-Down Triple and Quadruple Dealing Reviewed</span></h2><br /><div style="text-align: left;"><span style="font-family: Times, Times New Roman, serif;"><span style="background-color: white;">In October 2004, in the inaugural </span><i>Card Colm</i><span style="background-color: white;">, </span><a href="http://www.maa.org/community/maa-columns/past-columns-card-colm/low-down-triple-dealing" target="_blank">Low Down Triple Dealing</a><span style="background-color: white;">, we presented something discovered accidentally in the spring of 2003 while living in a Madrid suburb. It concerns surprising properties of a kind of "low-down deal"--in which at least half of the cards in a packet are dealt to a pile and the rest are dropped on top--done three or four times, dealing the same number of cards each time. More recently, in February 2011's </span><a href="http://www.maa.org/community/maa-columns/past-columns-card-colm/low-down-double-dealing-with-the-big-boys" target="_blank">Low-Down Double Dealing With the Big Boys</a><span style="background-color: white;">, we discussed something useful that can be said about only doing it twice, in the case of palindromic (i.e., symmetric) packets.</span></span></div><div style="text-align: left;"><span style="font-family: Times, Times New Roman, serif;"><span style="background-color: white;"><br /></span><span style="background-color: white;">In the October 2008 print incarnation of "Low-Down Triple Dealing" from the Martin Gardner tribute book </span><a href="http://www.crcpress.com/product/isbn/9781568812458"><i>A Lifetime of Puzzles</i></a><span style="background-color: white;"> (A K Peters), we mentioned a generalization first brought to our attention about a year earlier by Martii Siren, then (and now) editor of Finnish magic magazine </span><i>Jokeri</i><span style="background-color: white;">. He wrote about it in that publication in March 2008. Austrian magician Werner Miller also took advantage of this observation in a trick in his 2010 manuscript </span><i>Enigmaths</i><span style="background-color: white;">. Our upcoming </span><a href="http://www.crcpress.com/product/isbn/9781466509764"><i>Mathematical Card Magic: Fifty-Two New Effects</i></a><span style="background-color: white;"> (A K Peters) devotes an entire chapter to this extension of Low-Down Triple Dealing, so it seems like an opportune time to introduce it here. </span></span><br /><span style="font-family: Times, Times New Roman, serif;"><span style="background-color: white;"><br /></span></span><span style="font-family: Times, Times New Roman, serif;"><span style="background-color: white;">Let's start with the basics of the original low-down triple dealing. Imagine a face-down packet which runs Ace-King of Hearts. Fanned face up from left to right it looks like this:</span><span style="background-color: white;"> </span></span><br /><span style="font-family: Times, Times New Roman, serif;"><span style="background-color: white;"><br /></span></span><br /><div class="separator" style="clear: both; text-align: center;"><a href="http://2.bp.blogspot.com/-NOWo2cbnFfw/UYD3vlSljtI/AAAAAAAAHJw/X7E5gaCH6LQ/s1600/cards1.tiff" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="http://2.bp.blogspot.com/-NOWo2cbnFfw/UYD3vlSljtI/AAAAAAAAHJw/X7E5gaCH6LQ/s1600/cards1.tiff" height="121" width="400" /></a></div><div class="separator" style="clear: both; text-align: center;"><br /></div><span style="background-color: white; font-family: Times, 'Times New Roman', serif;">Now fix a number between 7 and 13, perhaps 9. Hold the face-down packet in one hand, and deal 9 cards to a pile, thus reversing their order. Drop the remaining 4 cards on top. Fanned face up from left to right, we now have: </span><br /><span style="background-color: white; font-family: Times, 'Times New Roman', serif;"><br /></span><br /><div class="separator" style="clear: both; text-align: center;"><a href="http://3.bp.blogspot.com/-7JyAdqDRiXA/UYD37EVR6SI/AAAAAAAAHJ4/vbVCu_AK78I/s1600/cards2.tiff" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="http://3.bp.blogspot.com/-7JyAdqDRiXA/UYD37EVR6SI/AAAAAAAAHJ4/vbVCu_AK78I/s1600/cards2.tiff" height="122" width="400" /></a></div><br /><span style="background-color: white; font-family: Times, 'Times New Roman', serif;">A second application of the "deal 9, drop 4" move converts that to this:</span><br /><span style="background-color: white; font-family: Times, 'Times New Roman', serif;"><br /></span><br /><div class="separator" style="clear: both; text-align: center;"><a href="http://2.bp.blogspot.com/-AJ6te8EWpXk/UYD4C4VniMI/AAAAAAAAHKA/uHXiDRlWfto/s1600/cards3.tiff" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="http://2.bp.blogspot.com/-AJ6te8EWpXk/UYD4C4VniMI/AAAAAAAAHKA/uHXiDRlWfto/s1600/cards3.tiff" height="122" width="400" /></a></div><br /><span style="background-color: white; font-family: Times, 'Times New Roman', serif;">A third application of the "deal 9, drop 4" move converts that in turn to:</span><br /><span style="background-color: white; font-family: Times, 'Times New Roman', serif;"><br /></span><br /><div class="separator" style="clear: both; text-align: center;"><a href="http://1.bp.blogspot.com/-NI-S6uEfUSM/UYD4Ibf915I/AAAAAAAAHKI/p2_jMaSu4bE/s1600/cards4.tiff" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="http://1.bp.blogspot.com/-NI-S6uEfUSM/UYD4Ibf915I/AAAAAAAAHKI/p2_jMaSu4bE/s1600/cards4.tiff" height="122" width="400" /></a></div><br /><span style="background-color: white; font-family: Times, 'Times New Roman', serif;">The first surprise is that the original bottom card (the King) is now on the top, in fact many of the original bottom cards are now on top in reversed order. This low-down triple dealing observation is the basic for many magic effects, some of which are explored in </span><a href="http://www.maa.org/community/maa-columns/past-columns-card-colm/low-down-triple-dealing" target="_blank">Low Down Triple Dealing</a><span style="background-color: white; font-family: Times, 'Times New Roman', serif;">. Also discussed there, and in much greater detail in the opening chapter of </span><a href="http://www.crcpress.com/product/isbn/9781466509764" style="color: #330099; font-family: Times, 'Times New Roman', serif;"><i>Mathematical Card Magic: Fifty-Two New Effects</i></a><span style="background-color: white; font-family: Times, 'Times New Roman', serif;"> (A K Peters), is the fact that a fourth application of the "deal 9, drop 4" move restores the packet to its original order, as is easily checked above. The only thing about 9 which makes all of the this work is that it's at least half of the packet size, 13, or, equivalently, 9 + 9 is at least 13.</span></div><span style="font-weight: normal;"></span><br /><h2><span style="font-size: large;">Low-Down Dealing With a Difference</span></h2><span style="font-family: Times, Times New Roman, serif;"><span style="background-color: white;">Let's start once more with a face-down packet which runs Ace-King of Hearts, and this time consider any two numbers </span><i>s</i><span style="background-color: white;"> and </span><i>t</i><span style="background-color: white;"> for which </span><i>s + t</i><span style="background-color: white;"> is at least 13, or to put it another way, two numbers which are at least half of 13, on average. For instance, we might select 5 and 10. Focus on the 5 first: deal 5 cards to a pile, thus reversing their order, and drop the remaining 8 cards on top. Fanned face up from left to right, we now have:</span></span><br /><span style="font-family: Times, Times New Roman, serif;"><span style="background-color: white;"><br /></span></span><br /><div class="separator" style="clear: both; text-align: center;"><a href="http://4.bp.blogspot.com/-MteCd_FwWTc/UYD4PILGVEI/AAAAAAAAHKQ/ypVdofpIxtE/s1600/cards5.tiff" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="http://4.bp.blogspot.com/-MteCd_FwWTc/UYD4PILGVEI/AAAAAAAAHKQ/ypVdofpIxtE/s1600/cards5.tiff" height="121" width="400" /></a></div><div class="separator" style="clear: both; text-align: center;"><br /></div><span style="background-color: white; font-family: Times, 'Times New Roman', serif;">Next, focus on the 10: deal 10 cards to a pile, thus reversing their order, and drop the remaining 3 cards on top. Fanned face up from left to right, we now have: </span><br /><span style="background-color: white; font-family: Times, 'Times New Roman', serif;"><br /></span><br /><div class="separator" style="clear: both; text-align: center;"><a href="http://2.bp.blogspot.com/-DIScER57e-k/UYD4WCrxfEI/AAAAAAAAHKY/uLz-AjY2-_8/s1600/cards6.tiff" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="http://2.bp.blogspot.com/-DIScER57e-k/UYD4WCrxfEI/AAAAAAAAHKY/uLz-AjY2-_8/s1600/cards6.tiff" height="126" width="400" /></a></div><br /><span style="background-color: white; font-family: Times, 'Times New Roman', serif;">Now we return to the 5: deal 5 cards again to a pile, thus reversing their order, and drop the remaining 8 cards on top. Fanned face up from left to right, we now have:</span><br /><span style="background-color: white; font-family: Times, 'Times New Roman', serif;"><br /></span><br /><div class="separator" style="clear: both; text-align: center;"><a href="http://2.bp.blogspot.com/-AFD05IedX9g/UYD4eCzFx5I/AAAAAAAAHKg/Ua9Pkb5zdnQ/s1600/cards7.tiff" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="http://2.bp.blogspot.com/-AFD05IedX9g/UYD4eCzFx5I/AAAAAAAAHKg/Ua9Pkb5zdnQ/s1600/cards7.tiff" height="123" width="400" /></a></div><br /><span style="background-color: white; font-family: Times, 'Times New Roman', serif;">At this point we have done three deals (of sizes 5, 10 and 5, respectively), and 10 of the original bottom cards are now on the top, in reverse order. </span><br /><span style="background-color: white; font-family: Times, 'Times New Roman', serif;"><br /></span><span style="background-color: white; font-family: Times, 'Times New Roman', serif;">Furthermore, it's clear that one more deal of 10 cards to a pile, dropping the remaining 3 cards on top, restores the packet to its original order. All told, dealing 5, 10, 5, and 10 cards, each time dropping the rest on top, restores any packet of size 13 to its original order, just as four deals of 9 cards did.</span><span style="background-color: white; font-family: Times, 'Times New Roman', serif;"> </span><br /><br /><div class="separator" style="clear: both; text-align: left;"><span style="font-family: Times, Times New Roman, serif;"><span style="background-color: white;">Try it dealing 10, 5, 10, and 5 cards, instead, i.e., using the same two numbers but switching the order, once more starting with the same packet of 13 cards as above. It works there too, and after the third deal it will be seen that the bottom 5 cards are on the top, in reverse order. Try it again, dealing 3, 11, 3, and 11 cards, or dealing 6, 9, 6, and 9 cards. </span><br /><br /><span style="background-color: white;">All of the above holds more generally: starting with a packet of size </span><i>n</i><span style="background-color: white;">, and any two numbers </span><i>s</i><span style="background-color: white;"> and </span><i>t</i><span style="background-color: white;"> for which </span><i>s + t</i><span style="background-color: white;"> is at least </span><i>n</i><span style="background-color: white;">, i..e., numbers which are at least half of </span><i>n</i><span style="background-color: white;">, on average, then if we first deal </span><i>s</i><span style="background-color: white;"> cards, dropping the rest on top, then deal </span><i>t</i><span style="background-color: white;"> cards, dropping the rest on top, then deal </span><i>s</i><span style="background-color: white;"> cards again, dropping the rest on top, it turns out that the bottom card appears on the top. Moreover, a final deal of </span><i>t</i><span style="background-color: white;"> cards, dropping the rest on top, restores the packet to its original order. <a href="http://www.maa.org/community/maa-columns/past-columns-card-colm/low-down-triple-dealing" target="_blank">The </a></span><a href="http://www.maa.org/community/maa-columns/past-columns-card-colm/low-down-triple-dealing" target="_blank">Low Down Triple Dealing</a><span style="background-color: white;"> discovery of a decade ago is the special case </span><i>s</i><span style="background-color: white;"> = </span><i>t</i><span style="background-color: white;">. </span><br /><br /><span style="background-color: white;">There is much to explore when </span><i>s</i><span style="background-color: white;"> and </span><i>t</i><span style="background-color: white;"> are different, and Chapter 5 of </span><a href="http://www.crcpress.com/product/isbn/9781466509764" style="color: #330099;"><i>Mathematical Card Magic: Fifty-Two New Effects</i></a><span style="background-color: white;"> (A K Peters) is devoted to such fun. We think of the first two deals and drops, dealing </span><i>s</i><span style="background-color: white;"> and </span><i>t</i><span style="background-color: white;"> cards, respectively, as a kind of double-deal. We close with a spelling application which works for any 9 cards.</span></span></div><h3><span style="background-color: white; font-family: Times, 'Times New Roman', serif;"><br /></span></h3><h2><span style="font-size: large;">Never Forget a Face</span></h2><div><span style="background-color: white; font-family: Times, 'Times New Roman', serif;"><br /></span></div><span style="background-color: white; font-family: Times, 'Times New Roman', serif;">Use any 9 cards from a deck. Have a spectator shuffle them and call out a number between 1 and 9 inclusive, then looking at and showing around the card in that position while you look away. Have the card replaced in that position and take the packet of nine cards, holding them under the table. Claim that you are feeling the face of the card shown around, and that your fingers never forget a face. </span><br /><span style="font-family: Times, Times New Roman, serif;"><br /><span style="background-color: white;">Explain that you want the spectator to do a packet randomization based on the spelling of the name of the card in question, demonstrating with cards from the rest of the deck. For instance, using a packet of around 10 cards, you say, "Suppose your card is the Nine of Diamonds, then first I will spell out the word NINE, dealing one card to the table each time, and after that dropping what is left on top." Matching your words, you deal out 4 cards and drop the remaining ones on top. "We do it again for DIAMONDS." This time, deal out 8 cards and drop the remaining ones on top. Repeat, once for the value and once for the suit. Now set those cards aside, and have the spectator do it, using the nine cards from before and the value and suit of the selected card. Make sure it's done twice, and turn your head while it is done so that you have no knowledge of the number of letters used. </span><br /><br /><span style="background-color: white;">Take back that packet of nine cards, and hold it under the table again. Stress that after the unknown card value and suit was used to mix the cards, twice, you obviously don't know where the selected card is. Bring the cards into view once more, and remind the audience that your fingers never forget a face: place one card face down on the table and ask what the selected card was. When the card is named, have the face-down card turned over, it should match. </span><br /><br /><span style="background-color: white;">Based on the earlier discussion, in the case of Nine of Diamonds, setting </span><i>s</i><span style="background-color: white;"> = 4 and </span><i>t</i><span style="background-color: white;"> = 8, since 4 + 8 > 9, we know that two rounds of double-dealing and dropping as suggested, using the card value and suit for the respective deals each time, restores the packet to its original order. So if the card selected started in position 3, then it's back there after you get the cards back. However, for the shorter words corresponding to cards such as the Ace of Clubs, where </span><i>s</i><span style="background-color: white;"> = 3 and </span><i>t</i><span style="background-color: white;"> = 5, there are no such guarantees. Actually, these are the only values of </span><i>s</i><span style="background-color: white;"> and </span><i>t</i><span style="background-color: white;"> to worry about arising from card values (which have 3, 4 or 5 letters) and suits (5, 6 or 8 letters), so basically it's the just Ace, Two, Six, Ten and Clubs which need separate consideration. </span><br /><br /><span style="background-color: white;">One option is simply to make sure those five cards are not among the nine which the spectator uses, but let's not take the easy way out. Imagine a face-down packet Ace-9 of Diamonds. It is readily checked that dealing 3 cards, and dropping the rest, then dealing 5 cards, and dropping the rest, all done twice to the packet, and fanning the results face up from left to right, yields: </span></span><br /><span style="font-family: Times, Times New Roman, serif;"><span style="background-color: white;"><br /></span></span><br /><div class="separator" style="clear: both; text-align: center;"><a href="http://4.bp.blogspot.com/-q50ai-aARWQ/UYD-SNqZ-SI/AAAAAAAAHK4/dovKvmEBK3U/s1600/cards8.tiff" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="http://4.bp.blogspot.com/-q50ai-aARWQ/UYD-SNqZ-SI/AAAAAAAAHK4/dovKvmEBK3U/s1600/cards8.tiff" height="101" width="320" /></a></div><br /><span style="background-color: white; font-family: Times, 'Times New Roman', serif;">In other words, two application of double-dealing in this case doesn't restore the whole packet to its original order, but the cards in positions 2, 3, 4, 5, 6, 7 and 8 are certainly back where they started! So if the selected card is in any of those positions, you'll know where to find it after the double spelling of value and suit, regardles of what cards in the deck was used to determine the dealings and droppings. If the selected card is in position 1, 4 or 9--admittedly rather square choices--simply move it, under the table, to one of the other six positions, remembering which one. You retrieve it from the same position, also out of sight, after the spectator's spellings and droppings are completed. </span><br /><div class="separator" style="clear: both; text-align: left;"><span style="font-family: Times, Times New Roman, serif;"><br /><span style="background-color: white;">This effect was of course inspired by Jim Steinmeyer's landmark "Nine Card Speller" from twenty years ago (available today in his booklet </span><i>Impuzzibilities</i><span style="background-color: white;"> (2002), as discussed in the February 2009 </span><i>Card Colm</i><span style="background-color: white;">, </span><a href="http://www.maa.org/community/maa-columns/past-columns-card-colm/esteem-synergism" target="_blank">Esteem Synergism</a><span style="background-color: white;">. As in that trick, the card can always be located no matter what its identity, leading to the amusing possibility of a repeat performance where the spectator is encouraged to lie about the card value and suit when spelling. (Lying about the position is not an option, however.) </span><br /><br /><span style="background-color: white;">There is a workaround, if desired, to avoid having to worry about the cards in positions 1, 4 or 9. First, ask for a number </span><i>between</i><span style="background-color: white;"> 1 and 9, and reject 1 or 9 if either is suggested. Second, if 4 is called out, have the packet of 9 cards dealt to a pile, with the card in position 4 being shown around before the rest are dealt on top of it. It's now in position 6 from the top, so all is well. </span></span></div>Mathematical Association of Americahttp://www.blogger.com/profile/10559021045290192742noreply@blogger.com0tag:blogger.com,1999:blog-1124742229498315339.post-27753294326049229132013-02-28T08:00:00.000-05:002013-07-30T10:58:24.898-04:00Flushed with Embarrassment<br /><span style="font-weight: normal;"><span style="background-color: white; font-family: inherit;">Welcome to our second new mathemagical offering for this month. The first one, </span><a href="http://www.huffingtonpost.com/colm-mulcahy/my-heart-of-hearts_b_2641875.html" style="color: #330099; font-family: inherit;">In My Heart of Hearts: Valentine's Day Special</a><span style="background-color: white; font-family: inherit;">, appeared as one of the current author's </span><a href="http://www.huffingtonpost.com/colm-mulcahy/" style="color: #330099; font-family: inherit;"><i>Huffington Post</i> pieces</a><span style="background-color: white; font-family: inherit;">. </span></span><br /><span style="font-weight: normal;"><span style="background-color: white; font-family: inherit;"><br /></span></span><span style="font-family: inherit;"><span style="background-color: white;">Six months ago here, in the August 2012 </span><i>Card Colm</i><span style="background-color: white;"> </span><a href="http://cardcolm-maa.blogspot.com/2012/08/gilbreeath-shuuffling.html" style="color: #330099;">Gilbreeath Shuuffling</a><span style="background-color: white;">, we considered yet another Gilbreath shuffle variation, a topic we revisit from time to time in August, e.g., s</span><span style="background-color: white;">ee </span><a href="http://www.maa.org/community/maa-columns/past-columns-card-colm/the-first-norman-invasion" target="_blank">2005</a><span style="background-color: white;">, </span><a href="http://www.maa.org/community/maa-columns/past-columns-card-colm/the-second-norman-invasion" target="_blank">2006</a><span style="background-color: white;">, and </span><a href="http://www.maa.org/community/maa-columns/past-columns-card-colm/the-bligreath-principle" style="color: #330099;">200</a><a href="http://www.maa.org/community/maa-columns/past-columns-card-colm/the-bligreath-principle" style="color: #330099;">9</a><span style="background-color: white;">. </span></span><br /><span style="background-color: white; font-family: inherit;"><br /></span><span style="background-color: white; font-family: inherit;">In November, magician John Hostler from St. Louis was kind enough to share an exciting discovery of his from last summer which he calls the Triskadequadra Principle (it's pronounced TRISK-a-de-QUA-dra). Below, we present an application of the ideas which just can't wait until next August. While John only develops the principle for four cycling suits such as CHaSeD (Clubs, Hearts, Spades, Diamonds), some version of the key ideas work for cycles of any length. We felt that <i>suitable modifications</i> were appropriate, and came up with an amusing multiple poker hand offering with a kicker at the end.</span><span style="background-color: white; font-family: inherit;"> </span><br /><span style="background-color: white; font-family: inherit;"><br /></span><span style="background-color: white; font-family: inherit;">Thanks to mathematician </span><a href="http://www.math.clemson.edu/~calkin/" style="color: #330099; font-family: inherit;">Neil Calkin</a><span style="background-color: white; font-family: inherit;"> of Clemson University for crucial stack refinement input in December. </span><br /><span style="font-family: inherit;"><span style="background-color: white;"><br /></span></span><span style="font-family: inherit;"><span style="background-color: white;">We leave it to John to explain the Triskadequadra Principle. His recent 24-page booklet </span></span><i style="color: #330099; font-family: inherit;"><a href="http://www.lulu.com/us/en/shop/john-hostler/the-triskadequadra-principle-ebook/ebook/product-20547965.html" style="color: #330099; font-family: inherit;">The Triskadequadra Principle</a></i><span style="font-family: inherit;"><span style="background-color: white;"> </span><span style="background-color: white;">has all the details, along with some great applications to card magic. The nature of the results obtained bears a resemblance to those discussed in </span><a href="http://cardcolm-maa.blogspot.com/2012/08/gilbreeath-shuuffling.html" style="color: #330099;">Gilbreeath Shuuffling</a><span style="background-color: white;">, and the same mathematical method of analysis explains both principles. Magician and prolific author Karl Fulves had written of related explorations, under the name the "Self-Correcting Set Up" principle, for the shuffling of two packets running Ace</span></span><span style="font-family: Calibri, sans-serif; line-height: 107%;">—</span><span style="background-color: white; font-family: inherit;">King, in his rare magic insider book </span><i style="font-family: inherit;">Riffle Shuffle Set Ups</i><span style="background-color: white; font-family: inherit;"> (originally published in 1968).</span><br /><span style="background-color: white; font-family: inherit;"><br /></span><span style="background-color: white; font-family: inherit;">The effect below, as well as an examination of the Triskadequadra Principle for cycles of different lengths, putting it in the context of Gilbreath shuffling and known variations, is in Chapter 8 of the upcoming </span><a href="http://www.crcpress.com/product/isbn/9781466509764" style="color: #330099; font-family: inherit;"><i>Mathematical Card Magic: Fifty-Two New Effects</i></a><span style="background-color: white; font-family: inherit;"> (A.K. Peters), which is due out in time for </span><a href="http://www.maa.org/mathfest/" style="color: #330099; font-family: inherit;">MAA MathFest</a><span style="background-color: white; font-family: inherit;"> in Hartford, CT.</span><br /><span style="font-family: inherit;"><span style="background-color: white; font-size: 13px;"><br /></span></span><br /><h2><span style="font-size: large;">Flushed with Embarrassment</span><span style="font-size: 11pt; line-height: 107%;"><span style="font-family: inherit;">—</span></span><span style="font-size: large;">How It Looks</span></h2><span style="font-family: inherit;"><span style="background-color: white;">Gather together five poker players and a poker novice. Hand the latter a packet of cards, and invite him or her to cut it several times, then split it into two and riffle shuffle those parts together, and finally to give it one more cut. </span><br /><br /><span style="background-color: white;">Deal out five poker hands for the aficionados of the game, and have each person discard their worst card face down. Retain those five cards in a pile in front of you. Then each player gives his or her best card to the novice. </span><br /><br /><span style="background-color: white;">You then hand over the remainder of the deck, face up, so that the five poker enthusiasts may make free choices to replenish their hands, until they each have five cards. </span><br /><br /><span style="background-color: white;">The resulting poker hands are compared, and it will be seen that some players have done quite well. However, when the novice turns over the cards he or she was given, it's seen to beat the rest, having four Aces and a King. </span><br /><br /><span style="background-color: white;">Just when it seems that the show is over, turn face up the discards you were given earlier. They constitute the winning hand: a straight flush.</span></span><br /><span style="font-family: inherit;"><span style="background-color: white; font-size: 13px;"><br /></span></span><br /><h2><span style="font-size: large;">A Little Detail</span></h2><span style="font-family: inherit;"><span style="background-color: white;">There's one little detail we didn't mention above: we're not playing with a full deck here, not at first anyway. </span><br /><br /><span style="background-color: white;">Start by saying, "We'll need just enough cards for some poker hands," as you thumb off or silently count out pre-arranged cards from the top of the deck to form a pile in the other hand. The rest of the deck is set aside for now. "We should shuffle, to be fair," you continue, then address the poker novice. "Would you, please?" Hand that person the packet and have it cut a few times, then split into two roughly equal piles. Have those riffle shuffled and one more cut done. </span><br /><br /><span style="background-color: white;">"You can't ask for fairer than that, can you?" you say, taking the packet back and fanning the card faces, briefly showing the audience, "Completely mixed up." </span><br /><br /><span style="background-color: white;">Now deal them in a circle from left to right, one card at a time per hand, to the poker fans, until you have dealt four hands of five cards. Then look puzzled, and say, "My mistake, there are five of you, not four, sorry." Gather up the cards and deal again, this time into five hands. Comment, "It seems we don't have enough cards here, only four each. I was never very good at numbers. We'll fix that in a moment. First I want each of you to look at the cards you already have. There are probably some good ones, and some bad ones. I'll make you a deal. Get rid of your single worst card you have, just give those ones to me. Please keep all cards face down as you discard them." </span><br /><br /><span style="background-color: white;">Briefly look at the five cards you are given, and comment, "Nothing too high there, oh well," and place them face down on the table in front of you. </span><br /><br /><span style="background-color: white;">Address the poker novice, "Since you're new to the game, we'll give you a break. The rest of you should each donate your best card. Don't worry, you'll have a chance to replace it soon." Have those five cards set in front of the novice, also face down. </span><br /><br /><span style="background-color: white;">"Since the five of you now only have two cards apiece, you may, in turn, go through the rest of the deck here, and find three cards to complement what you have so far. This isn't the way real poker works, I know, but it's fun to do once in a while. Knock yourself out!" </span><br /><br /><span style="background-color: white;">This should generate a buzz of excitement. Hand the remainder of the deck, face up, to the first poker fan, on your left, and in due course to the next one, and so on, until all five of them finally have five cards. </span><br /><br /><span style="background-color: white;">Recap the initial cutting and shuffling of the cards, by the novice, the discarding of low and then high cards, and the complete freedom for each person to pick three cards to add to the two received earlier. </span><br /><br /><span style="background-color: white;">Ask the poker fans, "So, how did each of you fare? It's time to show all!" With any luck, there will be proud displays of full houses, flushes, straights, maybe even a four of a kind. Everyone has at least a pair. </span><br /><br /><span style="background-color: white;">"Amazing, I guess it does help to have free selections for three of your five cards. Let's see how the novice did, purely by chance." The cards in front of the novice are turned over to reveal four Aces and a King. Everyone should be very impressed. </span><br /><br /><span style="background-color: white;">"Incredible!" you exclaim. "You saw the cards cut, shuffled, and cut again. What are the chances that four of you still ended up with an Ace? That's what must have happened, since you each donated your best card." </span><br /><br /><span style="background-color: white;">Here comes the kicker. "I'm not a poker player myself," you add casually. "It's a good thing, too. As mentioned earlier, my cards are all of low value." Turn your cards over, they turn out to be the 2, 3, 4, 5, and 6 of Clubs. "Oh dear, this is rather embarrassing. Isn't that a straight flush?" </span><br /><br /><span style="background-color: white;">Your humble low-valued cards, taken together, do indeed surpass each of the other six poker hands on display. Victory is yours.</span></span><br /><span style="font-family: inherit;"><span style="background-color: white; font-size: 13px;"><br /></span></span><br /><h2><span style="font-size: large;">A Lot More Detail</span></h2><span style="font-family: inherit;"><span style="background-color: white;">The cards you thumb off or count out (the latter action reversing their order) at the start form a stack which you have carefully constructed in advance and planted at the top of the deck. Twenty cards are used, in four interwoven sets of five.</span></span><br /><span style="font-family: inherit;"><span style="background-color: white;"> </span><br /><b>List A:</b><span style="background-color: white;"> 2 of Clubs, 3 of Clubs, 4 of Clubs, 5 of Clubs, 6 of Clubs. </span></span><br /><center><span style="font-family: inherit;"><img src="http://www.maa.org/sites/default/files/images/columns/colm/card14.gif" /> <img src="http://www.maa.org/sites/default/files/images/columns/colm/card15.gif" /> <img src="http://www.maa.org/sites/default/files/images/columns/colm/card16.gif" /> <img src="http://www.maa.org/sites/default/files/images/columns/colm/card17.gif" /> <img src="http://www.maa.org/sites/default/files/images/columns/colm/card18.gif" /></span></center><span style="font-family: inherit;"><br /><br /><b>List B:</b><span style="background-color: white;"> 7 of Clubs, 7 of Spades, Queen of Clubs, Queen of Hearts, Queen of Spades. </span></span><br /><center><span style="font-family: inherit;"><img src="http://www.maa.org/sites/default/files/images/columns/colm/card19.gif" /> <img src="http://www.maa.org/sites/default/files/images/columns/colm/card45.gif" /> <img src="http://www.maa.org/sites/default/files/images/columns/colm/card24.gif" /> <img src="http://www.maa.org/sites/default/files/images/columns/colm/card11.gif" /> <img src="http://www.maa.org/sites/default/files/images/columns/colm/card50.gif" /></span></center><span style="font-family: inherit;"><br /><br /><b>List C:</b><span style="background-color: white;"> Ace of Clubs, Ace of Hearts, Ace of Spades, Ace of Diamonds, King of Hearts. </span></span><br /><center><span style="font-family: inherit;"><img src="http://www.maa.org/sites/default/files/images/columns/colm/card26.gif" /> <img src="http://www.maa.org/sites/default/files/images/columns/colm/card13.gif" /> <img src="http://www.maa.org/sites/default/files/images/columns/colm/card52.gif" /> <img src="http://www.maa.org/sites/default/files/images/columns/colm/card39.gif" /> <img src="http://www.maa.org/sites/default/files/images/columns/colm/card12.gif" /></span></center><span style="font-family: inherit;"><br /><br /><b>List D:</b><span style="background-color: white;"> 7 of Diamonds, 8 of Diamonds, 9 of Diamonds, 10 of Diamonds, Jack of Diamonds. </span></span><br /><center><span style="font-family: inherit;"><img src="http://www.maa.org/sites/default/files/images/columns/colm/card32.gif" /> <img src="http://www.maa.org/sites/default/files/images/columns/colm/card33.gif" /> <img src="http://www.maa.org/sites/default/files/images/columns/colm/card34.gif" /> <img src="http://www.maa.org/sites/default/files/images/columns/colm/card35.gif" /> <img src="http://www.maa.org/sites/default/files/images/columns/colm/card36.gif" /></span></center><span style="font-family: inherit;"><br /><br /><span style="background-color: white;">The precise order within each list is not important. Note that the A list has the cards you want, all Clubs, with 6 being the highest value. The C list is the one destined for the poker novice, the lowest card there being a King. The other two lists consist of cards of "middling" value, between 7 and Queen; while they look tantalizing as possible poker hands, neither of them will be taken alive! </span></span><br /><span style="font-family: inherit;"><br /><span style="background-color: white;">Arrange these 20 cards cyclically as ABCDABCDABCDABCDABCD, by which we mean: start with any card from A, then any card from B, one from C, and finally one from D, then repeat in that pattern four more times. It doesn't really matter if you cut off or count out these from the deck at the outset. Also, they may be cut any number of times, for instance just before or after you hand them to the poker novice. This packet is then cut somewhere near the middle, and the two resulting piles riffled together. One more cut is given to the packet. </span></span><br /><span style="font-family: inherit;"><br /><span style="background-color: white;">When you scan the card faces, you are really looking for an appropriate place to cut, so that when you reassemble the two parts the other way, the packet is then in a highly desirable state. Simply cut it between two adjacent cards neither of which are on lists A or C. Thanks to De Morgan's law this is equivalent to the clumsier "both of which are from lists B or D (considered together)." If no such cut is possible, then no such corrective cut is necessary. </span></span><br /><span style="font-family: inherit;"><br /><span style="background-color: white;">Unsuspected by the audience, the result is five stacked quadlets (sets of four adjacent cards) with a special property, due to the Triskadequadra Principle:</span></span><br /><i><span style="font-family: inherit;"><br /></span></i><i><span style="font-family: inherit;"></span></i><br /><center><i><span style="font-family: inherit;"><b>Every quadlet from the top down is balanced in the following sense: </b></span></i><i><span style="font-family: inherit;"><b>it definitely </b></span></i><i><span style="font-family: inherit;"><b>contains </b></span></i></center><center><i><span style="font-family: inherit;"><b>one card from list A, one card from list C, and two from the other two lists, B or D.</b></span></i></center><center><i><span style="font-family: inherit;"><b><br /></b></span></i></center><span style="font-family: inherit;"><span style="background-color: white;">Of course, some quadlets contain one card from each of the four lists; we call these ones perfect. The key thing is that the non-perfect quadlets contain cards from exactly three of these lists. Another consequence (not needed here) of the Triskadequadra principle is that if a quadlet has two cards from list B, then the next non-perfect quadlet will have two from list D, and this alternating pattern repeats. </span></span><br /><span style="font-family: inherit;"><br /><span style="background-color: white;">Ideally you'd like to dole these quadlets out one at a time, but that's not how poker hands are dealt, so you first deal left to right into four piles of five, then, under the pretext of having made a mistake, collect those piles in the same order and recombine. Dealing once more from left to right, this time into five piles of four, accomplishes your original goal, while seemingly following normal left-to-right dealing conventions. </span></span><br /><span style="font-family: inherit;"><br /><span style="background-color: white;">The upshot is that each of the five poker fans now has a card from the C list, which is the four Aces and one King, and, moreover, all other cards in play at this stage have lower value. More importantly, each of the poker fans also has something from the A list, and these Clubs are the lowest valued cards in hand. As a result, the A list ones will be set aside face down near you, early on, seemingly of no consequence, and then the C list cards will be donated face down to the poker novice, none of these faces being revealed until the end. </span></span><br /><span style="font-family: inherit;"><br /><span style="background-color: white;">That leaves each poker aficionado with two cards from the B and D lists. The best case scenario is that some of them have a pair of 7s or a pair of Queens. Once they are let loose with the rest of the deck, they'll have fun building what they think are strong hands, but it's all in vain. The game has been rigged so that no straight flushes are possible. You will be victorious! </span></span><br /><span style="font-family: inherit;"><br /><span style="background-color: white;">The bogus and somewhat contrived double dealing can be avoided, as John Hostler points out, by simply handing out blocks of four cards to the five poker fans after the shuffle and cut (by the novice) and your own correction cut. </span></span><br /><span style="font-family: inherit;"><br /><span style="background-color: white;">This effect can also be performed as a straight Gilbreath application. In that case, instead of merely splitting the 20-card packet before riffle shuffling, the novice deals about half of the cards to the table, thereby reversing their order. There is extra certainty about the outcome: each of the quadlets is perfect, containing one card from each of the four lists. This may allow for more fun, as there is much flexibility in how lists B and D are chosen. </span></span><br /><br />Mathematical Association of Americahttp://www.blogger.com/profile/10559021045290192742noreply@blogger.com1tag:blogger.com,1999:blog-1124742229498315339.post-57870059784227905972012-12-24T09:00:00.000-05:002013-07-30T11:19:52.322-04:00Predictability Outranks LuckIn this 12th month of '12, on the eve of the start of the 12 days of Christmas, we revisit a topic explored 12 years and 12 weeks ago, which appeared online as part of <a href="http://www.ams.org/samplings/feature-column/fcarc-mulcahy6">AMS's <em>What's New in Mathematics</em></a> (October 2000).<br /><br />It concerns a variation of a surprising convergence result which was discovered by physicist Martin Kruskal in the 1970s, as popularized in card form by Martin Gardner. It can be found on page 274 of the latter's book <i>Penrose Tiles to Trapdoor Ciphers</i> (W.H. Freeman, 1989).<br /><br />It's a fine example of a baffling effect in which a spectator initiates a random process, based on mentally selecting a secret number known only to him or her, yet you can almost certainly correctly predict the ultimate outcome.<br /><br />Let's start by reviewing the classic incarnation. Shuffle a full deck of cards, then decide on a number <em>k</em> between 1 and 10. Slowly deal out the cards into a face-up pile, noting the card in position <em>k</em>, called the first key card, and using its value, counting out to the next key card, whose value is in turn used to count out to the following key card, and so on.<br /><br />For instance, if <em>k</em> = 6, and the sixth card is a 9, then that's the first key card and the second key card would be the fifteenth card. Repeat as often as is possible. Here, it's conventional to agree that the royal cards (Jack, Queen and King) have a common low value, such as 5.<br /><br />Eventually you arrive at a key card---perhaps the last card in the deck---from which you can't go any further, as it's not followed by enough cards to permit the next required count out. This final key card is the one to note; unless it's the final card we can think of it as a sticking point, or road block.<br /><br />Of course its location depends on the particular order of the cards in the deck at the outset, and the choice of <em>k</em>.<br /><br />What is quite unexpected is that, for a given deck order, no matter what value <em>k</em> has, we arrrive at the same final key card. More precisely, averaged over all possible shuffled decks, this occurs with probability about 5/6.<br /><br />A proper analysis of this takes us into Markov chains and stochastic processes, but we'll provide a basic probability estimate later on, for the version we suggest, to convince you that it's not so unreasonable. <br /><br /><h2><span style="font-size: large;">Predictable Road Block</span></h2>Here's a new way to present this as a prediction effect.<br /><br />Take out a deck of cards and carefully demonstrate the counting-out-the-deck principle, based on a randomly chosen number between 1 and 10 which you have an audience member call out. You can spin a yarn about the 52 cards representing a long trip, just making sure that everyone understands the importance of getting as far along the road as possible, either to the very end or until a road block impedes progress.<br /><br />Now have a spectator thoroughly shuffle the deck, and then take the cards back. Rummage through them, face up, announcing that things will go much faster if only the low values are used. Pull these out as you encounter them, dropping them into a face-up pile on the table.<br /><br />Hand the spectator the resulting packet of small-valued cards, now face down, and turn away. Ask for a random number between 1 and 6 inclusive to be decided on, secretly. A die could be rolled to determine this. Have the spectator use that number to initiate the process you demonstrated earlier. The spectator does this, and deals cards from the packet accordingly, until arriving at the sticking point (or the end). Have that card set off to one side face down.<br /><br />Now turn back, and stare intently at the back of that card. Say, "I could be wrong, but my gut feeling is that you got as far as ....", where upon you name a specific card. Have the face-down card exposed, with any luck you nailed it.<br /><br />How do you pull this off?<br /><br />Before you demonstrate the counting procedure, run through the deck and dump the Jacks, Queens and Kings, adding, "to save confusion" (which is true).<br /><br />Be sure to emphasize that when the spectator later deals cards to a pile, it should be done steadily so as to give no hint as to the location of any of the key cards. Say, "I'll be turned away, but I have very sensitive ears." (People do tend to deal noisily and with obvious pauses!)<br /><br />Once you are convinced that the directions are well understood, have the deck shuffled once more. Take it back and say, "To speed things up, let's only use about half of the deck, say the the Aces to sixes." Now start to extract those cards openly.<br /><br />Here's the secret: as you pull those twenty-four face-down cards out, dropping them one by one into a pile, you follow the same instructions that you just gave!<br /><br />Choose your own secret number between 1 and 6 and then, brazenly and on-the-fly, determine your key cards in the growing pile, working from the bottom up. Yes, it requires a quick mind and steady nerves, but it's doable. The mathematics suggests that you'll probably arrive at the same sticking point or road block as the spectator will in due course, or else you'll both make it to the end. (Admittedly, it's best if the last card seen here doesn't end up being the one the spectator gets to.)<br /><br />Actually, forget picking a number between 1 and 6, simply pick a very low valued card among the first few as they emerge from the shuffled deck, say a 2 in the third position from the bottom of the pile you build up, and go from there. Of course, the spectator will probably start from a different card, once you have handed over the 24-card packet face down, but you'll quite likely reach the same destination.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="http://2.bp.blogspot.com/-fksG-Z_4A2c/UNiX4FszBFI/AAAAAAAAGKk/D5dUT9z9SFE/s1600/kruskal1.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="http://2.bp.blogspot.com/-fksG-Z_4A2c/UNiX4FszBFI/AAAAAAAAGKk/D5dUT9z9SFE/s400/kruskal1.jpg" height="327" width="400" /></a></div><br />For instance, imagine that the twenty-four cards in the packet are in the order displayed above, read row by row from left to right. Try using any of the first six cards as the starting point. If the Ace of Hearts is used, then the next image shows the resulting key cards highlighted relative to the rest. Evidently, the road block is the 5 of Diamonds.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="http://1.bp.blogspot.com/-sUR_MkbsEh8/UNiX8iWPlTI/AAAAAAAAGKs/W4vuFj30LQo/s1600/kruskal2.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="http://1.bp.blogspot.com/-sUR_MkbsEh8/UNiX8iWPlTI/AAAAAAAAGKs/W4vuFj30LQo/s400/kruskal2.jpg" height="350" width="400" /></a></div><br />As mentioned above, we recommend making your choice small in value and early in the packet: if possible, favor an early Ace or 3 over a 4 or higher in position four or five or six.<br /><br />As it happens, with the arrangement considered above, all choices of starting point lead to the 5 of Diamonds. It's the common sticking point.<br /><br />In general, you and the spectator float merrily downstream, in different time frames, probably from different starting points, certainly oblivious to each other's progress. Yet, you can be quietly confident that you're on tributaries of the same river with one ultimate destination.<br /><br />Our third picture highlight all possible key cards for various starting cards. More than half of the packet doesn't even get a look in.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="http://1.bp.blogspot.com/-pzgifnyo7HY/UNiYAdwB6TI/AAAAAAAAGK0/qdZWP3vA12M/s1600/kruskal3.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="http://1.bp.blogspot.com/-pzgifnyo7HY/UNiYAdwB6TI/AAAAAAAAGK0/qdZWP3vA12M/s400/kruskal3.jpg" height="361" width="400" /></a></div><br />Of course, had the original array been as above but with the 5 and 4 of Diamonds switched, then all roads would have lead to the very end. <br /><br /><h2><span style="font-size: large;">Why <em>does</em> it work?</span></h2>Here is a heuristic argument----modified from one suggested by Tony Phillips of SUNY, Stony Brook, for a full deck---which sheds some light on the phenomenon.<br /><br />There is a 1/6 chance of you picking the same first card as the spectator.<br /><br />On average, that first card has value (1 + 2 + . . . + 6)/6 = 21/6 = 7/2.<br /><br />That's also the average length of subsequent steps, so the density of the spectator's key cards can be expected to be 2/7.<br /><br />Similarly, you yourself should encounter about 6 key cards on average after the first, since (24 - 3.5)/3.5 = 5.86. Each of these has a 2/7 chance of being one of the spectator's key cards, and hence a 5/7 chance of missing.<br /><br />The probability of you {\em not} hitting one of the spectator's key cards on the first or any later chance is therefore (5/6) x (5/7)6 = 0.11.<br /><br />So, the probability of a win for you, by this rough estimate, is about 89%, which is not shabby.<br /><br />A full mathematical treatment of these ideas can be found in the paper <a href="http://www.cecm.sfu.ca/organics/vault/robins">"On Kruskal's Principle"</a> by Wayne Haga & Sinai Robins, who also provide a great <a href="http://oldweb.cecm.sfu.ca/cgi-bin/organics/carddemo.pl">online simulation</a>.<br /><br />One presentational option is to write down an actual prediction, which is left to one side, right before you hand the spectator the packet of 24 cards to deal. At the end, you can then turn back and say, "Earlier I wrote down the card I thought you'd get to." The spectator's card is now turned face up, and is found to match your written prediction.<br /><br />Magician Gordon Bean, in his article "A Labyrinth in a Labyrinth" from <a href="http://downloads.akpeters.com/product.asp?ProdCode=1217"><em>Puzzlers' Tribute</em></a> (AK Peters, 2002), suggests spelling out one card for the each letter in the name of the value of key cards, so that, for instance, "ten" advances only three cards (T-E-N). This greatly increases the likelihood of reaching the same sticking point. A word of caution, however: spelling values on this scale is risky, as it's so easy for one or both of you to get confused and revert to ordinary counting.<br /><br />Run through a full demonstration of whichever counting procedure you adopt, pausing at each key card for clarity, before you let the spectator loose with the cards. It takes patience and care on the part of two people for this to work out. <br /><br /><h2><span style="font-size: large;">The Final Word(s)</span></h2>Linguistic applications of the Kruskal count principle, leading to a final key word in a piece of text, are entertaining in their own right, and were much loved by Martin Gardner. Author John Allen Paulos, winner of <a href="http://www.maa.org/meetings/jmm2013awards.html">2013 Joint Policy Board for Mathematics (JPBM) Communications Award</a>, has a nice treatment of a Kruskal-inspired biblical hoax in his book <em>Once Upon a Number--The Hidden Mathematical Logic of Stories</em> (Basic Books, 1998). The excerpt in question is <a href="http://math.temple.edu/~paulos/bibhoax" target="hoax">freely available online</a>.<br /><br />(On an tangentially related note, readers may be interested in <a href="http://www.huffingtonpost.com/colm-mulcahy/flipping-miracles-or-bar-bets-to-amaze-your-friends_b_2248388.html" target="hp">a miracle of bibilical proportions</a>—related to card magic—which we recently wrote about elsewhere.)<br /><br />Finally, a word about Persi Diaconis & Ron Graham, whose wonderful writing on de Bruijn sequence card magic we've referenced here in <a href="http://www.maa.org/community/maa-columns/past-columns-card-colm/whats-black-and-red-and-red-all-over">December 2008</a>, and <a href="http://cardcolm-maa.blogspot.com/2011_12_01_archive.html">December 2011</a>. Their beautiful and inspirational book <a href="http://press.princeton.edu/titles/9510.html"><em>Magical Mathematics: The Mathematical Ideas that Animate Great Magic Tricks</em></a> (Princeton University Press, 2011) is winner of the <a href="http://www.maa.org/meetings/jmm2013awards.html">2013 Euler Book Prize</a>.<br /><br />'Tis a season of celebration!<br /><br />Curiously, "Outranks Luck" is an anagram of "Kruskal Count." Mathematical Association of Americahttp://www.blogger.com/profile/10559021045290192742noreply@blogger.com1tag:blogger.com,1999:blog-1124742229498315339.post-50989688943820854182012-10-31T09:00:00.000-04:002013-07-30T11:21:48.476-04:00All or Nothing Trickle Treat<span style="font-family: inherit;"><span style="background-color: white;">Just in time for election season, we present a ternary trickle down principle. First, we note that </span><a href="http://www.maa.org/pubs/gardnertribute.html" style="color: #330099;">Martin Gardner</a><span style="background-color: white;"> (1914-2010), </span><a href="http://m.ajc.com/opinion/in-praise-of-a-686807.html" style="color: #330099;" target="bf">the best friend mathematics ever had</a><span style="background-color: white;">, would have turned 98 on 21 October. There is a Twitter feed in his honor at </span><a href="http://www.twitter.com/wwmgt" style="color: #330099;" target="twitter">WWMGT</a><span style="background-color: white;">, for which suggested contributions (What Would Martin Gardner Tweet?) are welcome. </span></span><br /><span style="font-family: inherit;"><br /><span style="background-color: white;">In the USA, </span><a href="http://www.huffingtonpost.com/colm-mulcahy/martin-gardner-birthday_b_1956287.html" style="color: #330099;" target="HP">Gardner did for recreational mathematics what Julia Child did for recreational cooking</a><span style="background-color: white;">. His influence spread much further afield actually, and like Child, he also inspired quite a few professionals along the way: mathematician and card expert Persi Diaconis has correctly noted, "he has turned thousands of children into mathematicians," playfully adding, "and thousands of mathematicians into children." After the above culinary comparison was made, author and Gardner friend Chris Morgan commented, "I was lucky to have spent time with Julia in the 1980s (I took three cooking classes with her in Boston). She was very much like Martin in many ways." </span><br /><br /><span style="background-color: white;">Last October here, we made available here </span><a href="http://cardcolm-maa.blogspot.com/2011/10/third-selection-of-mathemagical.html" style="color: #330099;">numerous card classics</a><span style="background-color: white;"> that Martin had published in his legendary </span><a href="http://maa-store.hostedbywebstore.com/MARTIN-GARDNERS-MATHEMATICAL-GAMES-Martin/dp/0883855453?field_availability=-1&field_browse=2672826011&field_keywords=martin+gardner&field_product_site_launch_date_utc=-1y&id=MARTIN+GARDNERS+MATHEMATICAL+GAMES+Martin&ie=UTF8&refinementHistory=brandtextbin%2Csubjectbin%2Ccolor_map%2Cprice%2Csize_name&searchKeywords=martin+gardner&searchNodeID=2672826011&searchPage=1&searchRank=salesrank&searchSize=12">"Mathematical Games" columns in <i>Scientific American</i></a><span style="background-color: white;">, following up on the earlier </span><a href="http://www.maa.org/community/maa-columns/past-columns-card-colm/in-his-own-words-mathematical-card-tricks-from-martin-gardner-1914-2010">June 2010</a><span style="background-color: white;"> and </span><a href="http://www.maa.org/community/maa-columns/past-columns-card-colm/also-in-his-own-words-more-mathemagical-games-and-tricks-with-cards-from-martin-gardner" style="color: #330099;">August 2010</a><span style="background-color: white;"> </span><i>Card Colm</i><span style="background-color: white;"><i>s</i>. </span><br /><br /><span style="background-color: white;">October is now well established worldwide as the anchor month for annual </span><a href="http://www.celebrationofmind.org/" style="color: #330099;">Celebration of Mind events</a><span style="background-color: white;">, which promote Martin's wide interests and remarkable and extensive written legacy. These gatherings bring together young and old, trained and untrained, to have fun with logic, puzzles, magic, </span><a href="https://twitter.com/timchartier/status/263707922197012480" style="color: #330099;">optical illusions</a><span style="background-color: white;"> and more, very much in the spirit of the ever-curious Gardner. </span><br /><br /><span style="background-color: white;">This year, in addition to seventy plus Celebration of Mind events listed at the </span><a href="http://www.g4g-com.org/event-map-2012" style="color: #330099;" target="map">event map here</a><span style="background-color: white;">, there are an equal number of </span><a href="http://www.puzzles.com/hexaflexagon" style="color: #330099;" target="fp">Flexagon Parties</a> <span style="background-color: white;">going on all over the globe, inspired by Vi Hart's viral videos on YouTube (don't miss the fourth </span><a href="http://www.youtube.com/watch?v=GTwrVAbV56o&feature=youtu.be" style="color: #330099;">food themed one</a><span style="background-color: white;">, which would have delighted both Child and Gardner). Vi was of course inspired by the </span><a href="http://maa.org/pubs/focus/Gardner_Hexaflexagons12_1956.pdf" style="color: #330099;" target="h">Hexaflexagons article</a><span style="background-color: white;"> which marked the start of Gardner's quarter century tenure at</span><i>Scientific American</i><span style="background-color: white;">. </span><br /><br /><span style="background-color: white;">Incidentally, </span><a href="http://aperiodical.com/2012/10/who-wants-to-host-a-celebration-of-mind-theres-still-time/" style="color: #330099;">it's not too late</a><span style="background-color: white;"> to host or attend events of either type. For instance, this year's MAA </span><a href="http://www.maa.org/news/2012CH-Tanton.html" style="color: #330099;">Celebration of Mind</a><span style="background-color: white;"> event is set for 5th December. Please consider joining or hosting an event, formal or informal, wherever you are. </span><br /><br /><span style="background-color: white;">October is also when </span><a href="http://www.huffingtonpost.com/colm-mulcahy/math-weak-try-math-week_b_2008517.html" style="color: #330099;">the world's most extensive and successful</a><span style="background-color: white;"> mathematics outreach programme </span><a href="http://www.mathsweek.ie/" style="color: #330099;" target="mw">Maths Week Ireland</a><span style="background-color: white;"> is held. This year, over a nine day period ending on Martin's birthday, it exposed over 150,000 people of various ages in both the Republic of Ireland and Northern Ireland to the joys of mathematics and logical thinking, with several </span><a href="http://www.irishskeptics.org/events/2012/2012-10-17" style="color: #330099;" target="is">nods to Gardner</a><span style="background-color: white;"> thrown in for good measure. The </span><a href="http://www.irishtimes.com/newspaper/ireland/2012/1020/1224325505947.html" style="color: #330099;">closing event</a><span style="background-color: white;"> was really a Celebration of Mind show and tell for the whole family, facilitated by a dozen presenters, which over a thousand people attended. I had the pleasure of participating, sometimes alongside notable </span><a href="http://www.g4g.org/" style="color: #330099;" target="g4g">Gathering for Gardner</a><span style="background-color: white;"> regulars such as Fernando Blasco. Top notch speakers included Colin Wright and David Singmaster. </span><br /><br /><span style="background-color: white;">It was while driving towards Sligo a fortnight ago with Maths Week Ireland mainstay </span><a href="http://www.ima.org.uk/viewitem.cfm?cit_id=383387" style="color: #330099;" target="dm">Dr. Maths</a><span style="background-color: white;">, on the way to address hundreds of school children, that I was introduced to a delightful recreation with triangles which forms the basis for this month's offering here. Like the title below, it's hard to resist, and I'm confident that Martin would have found it fascinating.</span></span><br /><br /><span style="color: #0b5394; font-family: inherit; font-size: x-large;"><b>Humble Contribution</b></span><br /><div><span style="font-family: inherit;"><br /></span></div><span style="font-family: inherit;"><span style="background-color: white;">Start with a row of </span><i>n</i><span style="background-color: white;"> items randomly selected from three possible types, say red, blue and white poker chips. Underneath each pair in the row, place a third item to form triangles, according to this rule: </span></span><br /><span style="font-family: inherit;"><span style="background-color: white;"><br /></span></span><br /><center><i><span style="font-family: inherit;">If the two vertices above are the same colour, then the third one matches both, whereas if the two vertices above are different colours, then the third one is different from either. </span></i></center><span style="font-family: inherit;"><br /><span style="background-color: white;">In other words, in each such downward-pointing tiny triangle, one never has only two vertices matching. When it comes to vertex matching, it's an all or nothing situation. </span><br /><br /><span style="background-color: white;">Once the initial row of </span><i>n</i><span style="background-color: white;"> items is processed to yield a second row of </span><i>n - 1</i><span style="background-color: white;"> items below it, process that row in the same way, to get a third row of </span><i>n - 2 </i><span style="background-color: white;">items underneath it. Continue, eventually getting a single item at the very bottom of an </span><i>n</i><span style="background-color: white;">-row triangle. </span><br /><br /><span style="background-color: white;">Here are three examples with poker chips: </span></span><br /><div class="separator" style="clear: both; text-align: center;"><a href="http://2.bp.blogspot.com/-9Ne2XqK-pKc/UJKKLo6xckI/AAAAAAAAFmI/4CLtrzs3qUk/s1600/colm1.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><span style="font-family: inherit;"><img border="0" src="http://2.bp.blogspot.com/-9Ne2XqK-pKc/UJKKLo6xckI/AAAAAAAAFmI/4CLtrzs3qUk/s640/colm1.jpg" height="211" width="640" /></span></a></div><center style="font-size: 12.800000190734863px;"><span style="font-family: inherit;"><br /></span></center><span style="font-family: inherit;"><span style="background-color: white;">Note that in each three-chip downward-pointing triangle</span><span style="background-color: white; color: #222222; line-height: 16px;">—</span><span style="background-color: white;">but not necessarily in their upward-pointing cousins</span><span style="background-color: white; color: #222222; line-height: 16px;">—</span><span style="background-color: white;">any two vertices determine the third according to the All or Nothing rule. Hence, upon reflection, or should we say upon rotation, any completed triangle (of any size) may be turned 120 degrees in either direction to yield an equally valid arrangement. Indeed, the second and third images above are exactly such rotations of the first one! </span><br /><br /><span style="background-color: white;">Here is the main question we wish to ponder: </span></span><br /><span style="font-family: inherit;"><span style="background-color: white;"><br /></span></span><br /><center><i><span style="font-family: inherit;">Given the top row of such a triangle, of any size, can one easily predict what the final bottom vertex will be?</span></i></center><span style="font-family: inherit;"><br /><span style="background-color: white;">Note the pleasing random-seeming arrangements of "solid sub-triangles" of various sizes in red, blue and white, which make up the larger triangles above. It almost suggests a fractal behaviour. </span><br /><br /><span style="background-color: white;">This can all be implemented with cards, for instance, using only three suits (which coincidentally was considered in the </span><a href="http://cardcolm-maa.blogspot.com/2012/08/gilbreeath-shuuffling.html" style="color: #330099;">last Card Colm</a><span style="background-color: white;">). </span><br /><br /><span style="background-color: white;">Alternatively, we could use face-up red and black and face-down cards for the three types, as illustrated below. </span></span><br /><span style="font-family: inherit;"><br style="font-size: 12.800000190734863px;" /></span><br /><div class="separator" style="clear: both; text-align: center;"><a href="http://1.bp.blogspot.com/-ufrqw3hZrrQ/UJKKlE0NajI/AAAAAAAAFmQ/i5GEeiOovFs/s1600/Screen+shot+2012-11-01+at+10.36.01+AM.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><span style="font-family: inherit;"><img border="0" src="http://1.bp.blogspot.com/-ufrqw3hZrrQ/UJKKlE0NajI/AAAAAAAAFmQ/i5GEeiOovFs/s400/Screen+shot+2012-11-01+at+10.36.01+AM.png" height="400" width="383" /></span></a></div><center style="font-size: 12.800000190734863px;"><span style="font-family: inherit;"><br /></span></center><span style="font-family: inherit;"><br style="font-size: 12.800000190734863px;" /><span style="background-color: white;">The secret here is to focus on the fourth row from the bottom: specifically its starting and finishing items. Those two cards alone determine the final bottom card according to the All or Nothing rule! No matter what other two cards are between the face-down blue-backed card and the 7 of Hearts, the final card will always be Black. In fact for every downward pointing "four triangle," consisting of ten cards, any two of the three vertex cards determine the third according to the same rule. </span><br /><br /><span style="background-color: white;">What's so special about four? Here's a hint: it's also true for downward pointing "ten triangles" consisting of 45 cards headed by a row of ten cards. Here's a perfectly reasonable question to also ponder: what is the next number after ten which also works? (You'll need eight decks of cards.) </span><br /><br /><span style="background-color: white;">Now suppose the following five cards are laid out, and our goal it to speedily guess the nature of the last card if the associated fifteen card triangle is completed. </span></span><br /><div class="separator" style="clear: both; text-align: center;"><a href="http://4.bp.blogspot.com/-mdby5Kgn5-0/UJKKsNVYBlI/AAAAAAAAFmY/qn4HGvxf0rQ/s1600/Screen+shot+2012-11-01+at+10.36.05+AM.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><span style="font-family: inherit;"><img border="0" src="http://4.bp.blogspot.com/-mdby5Kgn5-0/UJKKsNVYBlI/AAAAAAAAFmY/qn4HGvxf0rQ/s400/Screen+shot+2012-11-01+at+10.36.05+AM.png" height="117" width="400" /></span></a></div><span style="font-family: inherit;"><br style="font-size: 12.800000190734863px;" /><span style="background-color: white;">It's easy to see that the first card in the next row should be Black. Likewise the last card in this row should be Black, so the final card of the completed triangle should also be Black. </span><br /><br /><span style="background-color: white;">A similar "trickle down" approach can be used to predict the nature of the final card starting with rows of length six or seven. For longer rows, it may be easier to go the other direction, noting that, </span></span><br /><center><i><span style="font-family: inherit;">Given a triangle of any size, it can be extended upwards in exactly 3 distinct ways, by first deciding on the nature of any single card in the row above, and then filling in the rest to be consistent with the All or Nothing rule. Just be sure to always "trickle down" (not up)!</span></i></center><span style="font-family: inherit;"><br /><span style="background-color: white;">It's not hard to do this for a row of nine cards, extending it mentally to a row of ten and then quickly deducing the nature of the final card at the bottom if eight more rows were constructed. </span><br /><span style="background-color: white;"></span><br /><span style="background-color: white;">The principle underlying the above observations may be found in the upcoming paper "Triangle Mysteries" by Erhard Behrends & Steve Humble, which is due to appear in </span><i>The Mathematical Intelligencer</i><span style="background-color: white;"> in June 2013. There, the result hinted at above is generalized, and the connection with Pascal's triangle is explored in depth. Thanks to Steve (Dr. Maths) for the preview! </span><br /><span style="background-color: white;"></span><br /><span style="background-color: white;">Note that from a large downward-pointing triangle</span><span style="background-color: white; color: #222222; line-height: 16px;">—</span><span style="background-color: white;">which is as we noted completely determined by any of its three sides</span><span style="background-color: white; color: #222222; line-height: 16px;">—</span><span style="background-color: white;">one can also carve out Halloween hexagons with interesting properties. Have fun! </span></span>Mathematical Association of Americahttp://www.blogger.com/profile/10559021045290192742noreply@blogger.com0tag:blogger.com,1999:blog-1124742229498315339.post-42236925422377012002012-08-31T16:31:00.005-04:002013-07-30T11:44:33.334-04:00Gilbreeath Shuuffling <div class="separator" style="clear: both; text-align: left;"><span style="background-color: white;"><span style="font-family: inherit;">For many years I drove a car whose audio system had a "source" setting which offered a choice of C (for CD), R (radio) and A (auxiliary, which turned out to work with an mp3 player), only accessible via a one-way loop button. Toggling (troggling?) between them seeking the desired option, while keeping one eye on the road, was not ideal. I could never remember what order they cycled through, until one day it dawned on me that there were only two possibilities, and I also noticed that the manufacturers had thoughtfully arranged them as C-A-R over and over. From then on, I could change the source quickly and accurately while driving without risking life and limb by looking down. </span></span></div><span style="font-family: inherit;"><br /><span style="background-color: white;">This real life manifestation of the fact that (up to rotation) there are </span><i>(n-1)!</i><span style="background-color: white;"> ways to arrange </span><i>n</i><span style="background-color: white;"> things in a circle came to mind when analyzing "ESP + Math" from page 48 of </span><i>More Self-Working Card Tricks</i><span style="background-color: white;"> by </span><a href="http://geniimagazine.com/magicpedia/Karl_Fulves" style="color: #330099;" target="fulves">Karl Fulves</a> <span style="background-color: white;">(Dover, 1984), which we present below in slightly modified form. That tome is one of four from the same author and publisher which are devoted to card tricks many of which have mathematical underpinnings. </span><br /><br /><span style="background-color: white;">Fulves has the reader assemble two packets of 12 cards side by side and then riffle shuffle them together. From the top down, the first packet consists of four rounds of Spades, Hearts, Diamonds in that order (any values). The second packet consists of four rounds of Spades, Diamonds, Hearts, in that order (any values). No Clubs are used, and the card values play no role. </span><br /><br /><span style="background-color: white;">Suppose, for instance, that the first packet is set up as: K♠, 5♥, 9♦, 8♠, J♥, 3♦, 5♠, 8♥, 7♦, A♠, A♥, 5♦, and the second packets is set up as: 3♠, 10♦, Q♥, 7♠, 4♦, 10♥, 9♠, K♦, 6♥, 2♠, 2♦, 7♥. When riffle shuffled, the reader ends up with a packet of 24 cards. The display below shows one possibility from top to bottom, considering the second row of 12 as following on from the first: </span><br /> </span><br /><table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody><tr><td style="text-align: center;"><a href="http://2.bp.blogspot.com/-WJvaPbhjuiw/UEEeYniN14I/AAAAAAAAFAs/nMda7tB-9tQ/s1600/Screen+shot+2012-08-31+at+4.30.05+PM.png" imageanchor="1" style="margin-left: auto; margin-right: auto;"><span style="font-family: inherit;"><img border="0" src="http://2.bp.blogspot.com/-WJvaPbhjuiw/UEEeYniN14I/AAAAAAAAFAs/nMda7tB-9tQ/s640/Screen+shot+2012-08-31+at+4.30.05+PM.png" height="152" width="640" /></span></a></td></tr><tr><td class="tr-caption" style="text-align: center;"><i><span style="font-family: inherit; font-size: x-small;">Click to enlarge</span></i></td></tr></tbody></table><br /><span style="font-family: inherit;"><span style="background-color: white;">If cards are now peeled off three at a time from the resulting face-down packet, then a curious pattern emerges. Of course, in the above example, the shuffling can't have been very even, as the first five cards displayed clearly came as a clump from one of the initial packets of 12 cards. Hence, the first three cards feature one of each suit. </span><br /><br /><span style="background-color: white;">Consider the next three cards: there are two Spades, and one of them is the first card of this triple. There is no Diamond. The next three cards contain two Diamonds, one of them in the first position, and there is no Heart. The fourth group of three cards contains one of each suit, so ignore it. The next group of three, which starts the second line in our display, contains two Hearts, one in the first position, but no Diamond is present. In fact, no matter how the riffle shuffle turns out, a general prediction principle applies: </span></span><br /><center><i><span style="font-family: inherit;">Ignoring consecutive triples in which each of Diamonds, Hearts and Spades are present,<br />there is a cascading sequence of deductions that can be made: the first triple with a suit<br />repeated features two Spades, and one of them is the first card in that triple. Whichever<br />suit is not represented appears twice in the next triple with a suit repeated, and one of them<br />is the first card in that triple. This logic repeats as long as triples with repeated suits show up.</span></i></center><div style="text-align: center;"><span style="font-family: inherit;"><br /></span></div><span style="font-family: inherit;"><span style="background-color: white;">Note that above we are referring to just the eight consecutive triples which arise starting with the first card, not to "running triples." The claims made also hold for any two packets whose sizes are multiples of three, with suit cycling as described. </span><br /><br /><span style="background-color: white;">Why does this work? Before answering, we present a variation which might engage audiences more. It also aims to reduce the likelihood of getting any triples in which all three suits are present. </span><br /><br /><span style="background-color: white;">We then look at the mathematics behind it, and extend from cycles of length three to cycles of length four (or more). It turns out that the case of cycles of length two---which doesn't lead to an interesting effect in our context---derives from the </span><a href="http://www.maa.org/community/maa-columns/past-columns-card-colm/the-first-norman-invasion" style="color: #330099;" target="gilbreath1">original Gilbreath principle of 1958</a><span style="background-color: white;"> Hence, in essence, what we have here is a generalization of that principle. It's related to, but distinct from, the </span><a href="http://www.maa.org/community/maa-columns/past-columns-card-colm/the-second-norman-invasion" style="color: #330099;" target="gilbreath2">broader Gilbreath principle from 1966</a><span style="background-color: white;">.</span></span><br /><span style="font-family: inherit;"><span style="background-color: white;"><br /></span></span><br /><h2 style="color: #330099;"><span style="font-family: inherit; font-size: large;">Guessing Game</span></h2><span style="font-family: inherit;"><span style="background-color: white;">First, let's agree to mix the cards a little differently, using Lennart Green's </span><em>rosette shuffle</em><span style="background-color: white;">. Combinatorially, it's equivalent to the riffle shuffle suggested above: the cards within each packet of 12 remain in their original order when considered within the final packet of size 24. </span><br /><br /><span style="background-color: white;">Here's how to do this. With the two packets side by side, use the fingers to "twirl" the left one into a rosette, repeating for the right one, and then push the rosettes together. The images show the sequence of moves. Finally, square up the resulting packet. </span></span><br /><table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody><tr><td style="text-align: center;"><a href="http://2.bp.blogspot.com/-_dgjFhNorE8/UEEeXuourmI/AAAAAAAAFAc/Uy-jkFw85Io/s1600/Screen+shot+2012-08-31+at+4.29.33+PM.png" imageanchor="1" style="margin-left: auto; margin-right: auto;"><span style="font-family: inherit;"><img border="0" src="http://2.bp.blogspot.com/-_dgjFhNorE8/UEEeXuourmI/AAAAAAAAFAc/Uy-jkFw85Io/s640/Screen+shot+2012-08-31+at+4.29.33+PM.png" height="122" width="640" /></span></a></td></tr><tr><td class="tr-caption" style="text-align: center;"><i><span style="font-family: inherit; font-size: x-small;">Click to enlarge.</span></i></td></tr></tbody></table><span style="font-family: inherit;"><span style="background-color: white;">Applying this to the two original packets of 12 cards above, and taking care to ensure that the top cards of each packet end up together, we may end up this packet of 24 cards: </span></span><br /><table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody><tr><td style="text-align: center;"><a href="http://2.bp.blogspot.com/-N0tIfwSbw9s/UEEeYIcccAI/AAAAAAAAFAk/FQDfvwpGQ-Q/s1600/Screen+shot+2012-08-31+at+4.29.35+PM.png" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" src="http://2.bp.blogspot.com/-N0tIfwSbw9s/UEEeYIcccAI/AAAAAAAAFAk/FQDfvwpGQ-Q/s640/Screen+shot+2012-08-31+at+4.29.35+PM.png" height="155" width="640" /></a></td></tr><tr><td class="tr-caption" style="text-align: center;"><i>Click to enlarge.</i></td></tr></tbody></table><span style="font-family: inherit;"><br /><span style="background-color: white;">As is easily verified, the prediction principle does not let us down, although once again two of the eight triples contain cards of all three suits. (We have found through experimentation that the rosette shuffle very often results in fewer than two such triples.) </span><br /><br /><span style="background-color: white;">Here's a way to take advantage of this principle. Deal the packet of 24 shuffled cards into three piles from left to right. Retain the first one for yourself, and give the others to two spectators. Request that each person deal into a pile on the table to verify that they have eight cards, while doing likewise yourself; this is actually a ruse to reverse the order of each pile. </span><br /><br /><span style="background-color: white;">Next, suggest that a guessing game be played. Have each spectator guess the suit of the top card in their respective piles, before turning them over. You already know that one of them is a Spade, so that if the first person's card turns out to be something different, you can even guess that the next person's is a Spade. In any case, you end up by correctly guessing that yours is a Spade before you turn it over to confirm. Chances are, you'll do much better than the spectators who have absolutely nothing to go on, and don't even realize that there are no Clubs in play! Have those three cards set aside face down, quietly noting which suit you did not just see, and proceed to the guessing and uncovering of the suits of the next three exposed face-down cards. After a few successful rounds say, "Perhaps you think I need to see your card faces to guess mine correctly? This time let's all guess before anyone exposes their cards!" You still come out ahead most of the time, despite the misdirection of the words you just uttered. In the hopefully rare cases where all three cards are of different suits, so that your reasonable guesses are wrong, modestly say, "Nobody's perfect all the time." </span><br /><br /><span style="background-color: white;">Given the visibly shuffled state of the cards, your audience should be baffled (and impressed) by your near-perfect predictive powers.</span></span><br /><span style="font-family: inherit;"><span style="background-color: white;"><br /></span></span><br /><h2 style="color: #330099;"><span style="font-family: inherit; font-size: large;">Mathematical Games</span></h2><span style="font-family: inherit;"><span style="background-color: white;">So what is the mathematics behind all of this? Let Spades, Hearts and Diamonds be represented by 0, 1, 2, respectively, so that the packet of the left, from top to bottom, is 012012012012, and the packet on the right is 021021021021. Here's the key observation: </span></span><br /><center><i><span style="font-family: inherit;">The effect of riffle (or rosette) shuffling these two and then pulling off three cards at a time, is to, (A) line up the left packet in reverse beside the right one to get 210210210210 021021021021, and (B) successively extract three adjacent cards "from the middle", starting by including at least one of the two initially adjacent 0s. Ignoring the undesirable cases where all three cards come from one of the packets, we therefore get as our first triple either two 0s and a 1, with a 0 on top, or two 0s and a 2, with a 0 on top.</span></i></center><span style="font-family: inherit;"><br /><br /><span style="background-color: white;">In the first case, the next triple---again assuming it involves cards from both packets---will be extracted from the middle of 2102102102 21021021021, and hence consist of two 2s (and a either a 0 or a 1). In the second case, the next triple will be extracted from the middle of 21021021021 1021021021, and hence consist of two 1s (and a either a 2 or a 0). Now the pattern which gives rise to the claimed prediction principle should be clear.</span></span><br /><span style="font-family: inherit;"><span style="background-color: white;"><br /></span></span><br /><h2 style="color: #330099;"><span style="font-family: inherit; font-size: large;">Mega Guessing</span></h2><span style="font-family: inherit;"><span style="background-color: white;">For a version with groups of four cards each time, arrange two packets of say 16 cards, one cycling Spades, Hearts, Clubs, Diamonds, from the top down, and the other cycling Spades, Diamonds, Clubs, Hearts. </span><br /><br /><span style="background-color: white;">Mathematically, from top to bottom, we have 0123012301230123 on the left, and 0321032103210321 on the right (the suit/numerical correspondence has changed from what we had above). This time, we can assert: </span></span><br /><center><i><span style="font-family: inherit;">The effect of riffle (or rosette) shuffling these two and then pulling off four cards at a time, is to, (A) line up the left packet in reverse beside the right one to get 3210321032103210 0321032103210321, and (B) successively extract four adjacent cards "from the middle", starting by including at least one of the two initially adjacent 0s. Ignoring the undesirable cases where all four cards come from one of the packets, we therefore get as our first groups of four cards either two 0s, a 2 and a 1, or two 0s, a 1 and a 3, or two 0s, a 3 and a 2. In all three cases there is a 0 on top, and the next (worthy!) group of four contains two cards of the suit not represented in the previous group of four.</span></i></center><span style="font-family: inherit;"><br /><span style="background-color: white;">The same kind of effect as before can be pulled off here: have the 32 cards dealt into four piles of four, then re-dealt to reverse the card order. Now, if you claim the first such pile for yourself, you can correctly predict the suit of most of the those cards provided that you progressively get to see the corresponding cards in the other three piles. The guessing game is a good and distracting way to achieve this. </span><br /><br /><span style="background-color: white;">The principle extends to five or indeed any larger number. Readers may like to try out a version with cycles of length 13.</span></span><br /><span style="font-family: inherit;"><span style="background-color: white;"><br /></span></span><br /><h2 style="color: #330099;"><span style="font-family: inherit; font-size: large;">Clopening Remarks</span></h2><span style="font-family: inherit;"><span style="background-color: white;">Question 1: Is it mandatory to reverse the order of each pile? What if one were to work up from the bottom of the original packets instead of down from the top, perhaps modifying the packet set-up accordingly? </span><br /><br /><span style="background-color: white;">Question 2: Is a there way to take advantage of the card values as well as suits, to improve the accuracy of the predictions made? </span><br /><br /><span style="background-color: white;">Question 3: Are there other such variations on the Gilbreath principle, for cycles of length four or more, of interest? Perhaps shuffling a packet cycling Spades, Hearts, Clubs, Diamonds, from the top down, with one cycling in some order not considered above (or below)? </span><br /><br /><span style="background-color: white;">Question 4: Have we really exhausted the possibilities for cycles of length three, notwithstanding our starting C-A-R comments? After all, there are other arrangements of the two starting packets relative to each other! One of them fits in with the </span><a href="http://www.maa.org/community/maa-columns/past-columns-card-colm/the-bligreath-principle" style="color: #330099;" target="bligreath2">Bligreath Principle</a><span style="background-color: white;"> discussed here in August 2009. </span><br /><br /><span style="background-color: white;">We finish by pointing out a connection between what we have considered and the general Gilbreath shuffle principle. Let's first review the latter, via a standard effect which is to stack a deck with the suits cycling in some fixed order, then deal out about half of the cards to form a pile, before riffle shuffling those into the remainder. Pulling off four at a time, one is guaranteed to have all four suits represented each time, though in what order is anyone's guess. </span><br /><br /><span style="background-color: white;">Mathematically, that's equivalent to starting with something like 301230123...0123 in one pile (those cards retained in the hand) and 2103210...3210 in another on the table. The effect of riffle (or rosette) shuffling these two together and then pulling off four cards at a time is to reverse one of those piles and place it beside the other yielding 3210...321032103 2103210...3210, and then extract four cards at a time, starting "in the middle" with either the 3 or 2 (or both) which abut the visible gap above, along with several adjacent cards. Each time one must get one of each of the four types. </span><br /><br /><span style="background-color: white;">A similar connection exists between the "ESP + Math" effect and the Gilbreath principle for packets consisting of repeated cycles of length three. </span><br /><br /><span style="background-color: white;">When all is said and done, what we have explored above is the case of inserting one additional "repeated" card near the middle, </span><i>beside one of the same type</i><span style="background-color: white;">, in the usual Gilbreath context, and then proceeded to riffle or rosette shuffle. While it changes the nature of one's prediction, predict one certainly can; at least for a quarter (or a third) of the shuffled cards, modulo those annoying cases where all types are represented in the groups pulled off. </span><br /><br /><span style="background-color: white;">Instead of starting with the effect in the Fulves book and extending it from cycles of three cards to cycles of four cards, what happens if we consider cycles of two cards? It turns out that we are basically revisiting familiar Gilbreath terrain. Without loss of generality, we are riffle (or rosette) shuffling together two packets of the same type, each cycling Black Red over and over from the top down. The effect is predictable and well-known (and is covered in the Fulves volume referenced above), as it's just a basic "out of synch" Gilbreath shuffle of the type first published in 1958. It is customary to "restore" such shuffled packets to the usual post-Gilbreath state by splitting between two cards of like colour, after which each pair pulled off definitely consists of one Black and one Red card, in some order. However, if this step is skipped, then each pair which doesn't consist of one card of each colour instead consists of two of the same colour, starting with two Blacks, then two Reds, etc. This is no great surprise, and is hard to make into an engaging effect; for one thing, Black/Red or Black/Red pairs occur here with great frequency. (The only interesting part is the alternation of the colours when two like-cards are paired up. Of course one will never encounter more than two adjacent cards of the same colour; something which characterizes a packet in post-Gilbreath mode.) </span><br /><br /><span style="background-color: white;">In conclusion, inspired by "ESP + Math" from the 1984 Fulves volume, we have suggested a generalization of the </span><a href="http://www.maa.org/community/maa-columns/past-columns-card-colm/the-first-norman-invasion" style="color: #330099;" target="gilbreath1">binary (<i>k = 2</i>) Gilbreath principle</a><span style="background-color: white;"> published in 1958. It's different in spirit from the </span><a href="http://www.maa.org/community/maa-columns/past-columns-card-colm/the-second-norman-invasion" style="color: #330099;" target="gilbreath2">more general (arbitrary <i>k</i>) Gilbreath principle</a><span style="background-color: white;"> published in 1966, though it's closely related to it. </span><br /><br /><span style="background-color: white;">Many other shuffle variations may be found (so to speak) in the hard to find book </span><i>Riffle Shuffle Set-ups</i><span style="background-color: white;">, also by Karl Fulves (1968). </span><br /><br /><span style="background-color: white;">The positioning of repeated cards near the middle of the shuffled packets above prompted our tongue-in-cheek title, Gilbreeath Shuuffling, which we recommend be pronounced gil-BREEATH SHOE-fling to distinguish it from the more normal GILL-br'th shuff-l'ng. </span></span>Mathematical Association of Americahttp://www.blogger.com/profile/10559021045290192742noreply@blogger.com0tag:blogger.com,1999:blog-1124742229498315339.post-71288818287450894622012-06-28T10:51:00.005-04:002013-07-30T11:54:44.898-04:00Something Old, Something True, Something Borrowed, Something New<br /><span style="background-color: white;"><span style="color: #674ea7; font-family: inherit; font-size: x-large;">Something Old</span></span><br /><br /><span style="font-family: inherit;"><span style="font-size: 13px;">There's an old scam in which a victim is offered a free choice of any five of ten face-down cards, to serve as a poker hand, the other five being retained by the person offering the cards. When the resulting poker hands are compared, it turns out that the victim has the losing hand. </span><br style="font-size: 13px;" /><br style="font-size: 13px;" /><span style="font-size: 13px;">This can be repeated as often as is wished. This principle, often referred to as the "Ten Card Poker Deal," goes back at least as far as </span><span style="font-size: 13px;"><i>Card Control</i></span><span style="font-size: 13px;"> (2nd ed., 1947) by Arthur Buckley. </span><br style="font-size: 13px;" /><br style="font-size: 13px;" /><span style="font-size: 13px;">Another version sees the victim being permitted to win a few times at first, in order to instill a false sense of confidence, perhaps before the game is played for money. Then, the winds of fortune mysteriously change. </span><br style="font-size: 13px;" /><br style="font-size: 13px;" /><span style="font-size: 13px;">For one performance only, the cards could be offered openly, face up, one at a time. A high-valued card such as Ace is an early contender for attention, it being assumed that the victim won't be able to resist its fatal charms. </span><br style="font-size: 13px;" /><br style="font-size: 13px;" /><span style="font-size: 13px;">The secret is very simple. As hinted at above, there is a single dud among the ten cards---in isolation it may appear to be valuable---such that whoever gets it loses without a doubt. The other nine cards are carefully planned in advance of course, but the person offering the card choices just has to make sure that the victim gets stuck with the dud. </span><br style="font-size: 13px;" /><br style="font-size: 13px;" /><span style="font-size: 13px;">We've been deliberately vague about how the cards are offered to the victim and then selected; various methods can be used. Perhaps the dud's back is subtly marked, so that it can easily be tracked, and steps are taken to unload it ASAP. </span><br style="font-size: 13px;" /><br style="font-size: 13px;" /><span style="font-size: 13px;">Such not-so-honest approaches are far from the spirit of mathemagical effects, so in what follows we instead offer three ingenious and fair-seeming ways to arrive at the desired card distribution. These methods have been explored in previous </span><i style="font-size: 13px;">Card Colm</i><span style="font-size: 13px;">s, and can be used here to control who wins on each round. </span><br style="font-size: 13px;" /><br style="font-size: 13px;" /><span style="font-size: 13px;">The required ten cards are: three sets of three of a kind, for instance three 3s, three 8s, and three Kings, together with the dud, which is any non-matching card---below we'll settle for a Jack---which is known as the Jonah card. Whoever gets the Jonah card loses, without fail. </span><br style="font-size: 13px;" /><br style="font-size: 13px;" /><span style="font-size: 13px;">The suits here can be arbitrary; for that matter the relative values play no role either, as they are never compared.</span></span><br /><div><span style="font-family: inherit; font-size: x-small;"><br /></span><span style="color: #674ea7; font-family: inherit; font-size: x-large;">Something True</span><br /><br /><span style="font-family: inherit;"><span style="font-size: 13px;">Before we show why success or failure here always boils down to control of the Jonah card, we need to be clear as to the ranking of the various possible poker hands, i.e., selections of five cards from a standard deck. </span><br style="font-size: 13px;" /><br style="font-size: 13px;" /><span style="font-size: 13px;">There are 52!/(5!47!), or roughly 2.6 million such selections, which is so many that even if you were to play enough poker in your life to encounter 100,000 hands, you'd still only have seen less than 5% of them. </span><br style="font-size: 13px;" /><br style="font-size: 13px;" /><span style="font-size: 13px;">The relative scarcity (and hence value) of some of the commonly desired Poker hands is reflected in this chain, starting with the rarer hands: </span></span><br /><span style="font-family: inherit;"><span style="font-size: 13px;"><br /></span></span><br /><br /><center style="font-size: 13px;"><i><span style="font-family: inherit;">Royal flush > straight flush > four of a kind> full house ><br />flush> straight > three of a kind > two pairs > one pair.</span></i></center><span style="font-family: inherit;"><br style="font-size: 13px;" /><br style="font-size: 13px;" /><span style="font-size: 13px;">The rankings are transitive, so that for instance, a flush beats two pairs, but four of a kind beats both. </span><br style="font-size: 13px;" /><br style="font-size: 13px;" /><span style="font-size: 13px;">Returning to the Jonah card issues, let's suppose that the cards in question are: 3♣, 3♠, 3♦, 8♥, 8♣, 8♦, K♥, K♠, K♦ and J♠. </span><br style="font-size: 13px;" /><br style="font-size: 13px;" /><span style="font-size: 13px;">First focus on the hand with the Jonah card; it's not difficult to see that one of the following three cases must hold. </span><br style="font-size: 13px;" /><br style="font-size: 13px;" /><b style="font-size: 13px;">Case 1:</b><span style="font-size: 13px;"> This hand also contains three of a kind, and one other card, as shown in the top row here. The bottom row is the other hand. </span></span><br /><center style="font-size: 13px;"><span style="font-family: inherit;"><img src="http://www.maa.org//sites/default/files/images/columns/colm/card49.gif" height="75" /> <img src="http://www.maa.org//sites/default/files/images/columns/colm/card20.gif" height="75" /> <img src="http://www.maa.org//sites/default/files/images/columns/colm/card07.gif" height="75" /> <img src="http://www.maa.org//sites/default/files/images/columns/colm/card33.gif" height="75" /> <img src="http://www.maa.org//sites/default/files/images/columns/colm/card15.gif" height="75" /><br /><br /><img src="http://www.maa.org//sites/default/files/images/columns/colm/card28.gif" height="75" /> <img src="http://www.maa.org//sites/default/files/images/columns/colm/card41.gif" height="75" /> <img src="http://www.maa.org//sites/default/files/images/columns/colm/card38.gif" height="75" /> <img src="http://www.maa.org//sites/default/files/images/columns/colm/card12.gif" height="75" /> <img src="http://www.maa.org//sites/default/files/images/columns/colm/card51.gif" height="75" /><br /><br />Figure 1: Typical losing and winning hands in Case 1</span></center><span style="font-family: inherit;"><br style="font-size: 13px;" /><br style="font-size: 13px;" /><span style="font-size: 13px;">Then the other hand wins, being a full house containing three of a kind and a matching pair. There are 54,912 five-card hands with just three of a kind, compared to only 3744 full houses. The hands are something like what is shown above. </span><br style="font-size: 13px;" /><br style="font-size: 13px;" /><b style="font-size: 13px;">Case 2:</b><span style="font-size: 13px;"> The hand with the Jonah card also contains two pairs, as shown in the top row here. The bottom row is the other hand. </span></span><br /><center style="font-size: 13px;"><span style="font-family: inherit;"><img src="http://www.maa.org//sites/default/files/images/columns/colm/card49.gif" height="75" /> <img src="http://www.maa.org//sites/default/files/images/columns/colm/card15.gif" height="75" /> <img src="http://www.maa.org//sites/default/files/images/columns/colm/card41.gif" height="75" /> <img src="http://www.maa.org//sites/default/files/images/columns/colm/card12.gif" height="75" /> <img src="http://www.maa.org//sites/default/files/images/columns/colm/card51.gif" height="75" /><br /><br /><img src="http://www.maa.org//sites/default/files/images/columns/colm/card20.gif" height="75" /> <img src="http://www.maa.org//sites/default/files/images/columns/colm/card07.gif" height="75" /> <img src="http://www.maa.org//sites/default/files/images/columns/colm/card33.gif" height="75" /> <img src="http://www.maa.org//sites/default/files/images/columns/colm/card28.gif" height="75" /> <img src="http://www.maa.org//sites/default/files/images/columns/colm/card38.gif" height="75" /><br /><br />Figure 2: Typical losing and winning hands in Case 2</span></center><span style="font-family: inherit;"><br style="font-size: 13px;" /><br style="font-size: 13px;" /><span style="font-size: 13px;">Then the other hand still wins, containing three of a kind and two unmatched cards. There are 123,552 hands with two pairs, compared to only 54912 hands with just three of a kind. The hands look something like what is shown above. </span><br style="font-size: 13px;" /><br style="font-size: 13px;" /><b style="font-size: 13px;">Case 3:</b><span style="font-size: 13px;"> The hand with the Jonah card also contains one pair and two non-matching cards, as shown in the top row here. The bottom row is the other hand. </span></span><br /><center style="font-size: 13px;"><span style="font-family: inherit;"><img src="http://www.maa.org//sites/default/files/images/columns/colm/card49.gif" height="75" /> <img src="http://www.maa.org//sites/default/files/images/columns/colm/card12.gif" height="75" /> <img src="http://www.maa.org//sites/default/files/images/columns/colm/card51.gif" height="75" /> <img src="http://www.maa.org//sites/default/files/images/columns/colm/card15.gif" height="75" /> <img src="http://www.maa.org//sites/default/files/images/columns/colm/card20.gif" height="75" /><br /><br /><img src="http://www.maa.org//sites/default/files/images/columns/colm/card28.gif" height="75" /> <img src="http://www.maa.org//sites/default/files/images/columns/colm/card41.gif" height="75" /> <img src="http://www.maa.org//sites/default/files/images/columns/colm/card07.gif" height="75" /> <img src="http://www.maa.org//sites/default/files/images/columns/colm/card33.gif" height="75" /> <img src="http://www.maa.org//sites/default/files/images/columns/colm/card38.gif" height="75" /><br /><br />Figure 3: Typical losing and winning hands in Case 3</span></center><span style="font-family: inherit;"><br style="font-size: 13px;" /><br style="font-size: 13px;" /><span style="font-size: 13px;">Then the other hand wins one more time, as it contains two pairs. There are 1,098,240 hands with just one pair, compared to 123,552 hands with two pairs. The two hands look something like those above. </span><br style="font-size: 13px;" /><br style="font-size: 13px;" /><span style="font-size: 13px;">In conclusion: the trick, so to speak, is to control who gets the Jonah card.</span></span></div><div><span style="font-size: x-small;"><br /></span><span style="color: #674ea7; font-family: inherit; font-size: x-large;">Something Borrowed</span><br /><br /><span style="font-size: 13px;"><span style="font-family: inherit;">Here are three clever ways to control who gets the Jonah card, while appearing to randomise how the cards are distributed.</span></span><br /><ol style="font-size: 13px;"><li><span style="font-family: inherit;">In the <a href="http://www.maa.org/community/maa-columns/past-columns-card-colm/six-degrees-of-freedom-separation" style="color: #330099; font-weight: bold;" target="200606">April 2006 <i>Card Colm</i></a>, we explained <b>Bill Simon's 64 Principle </b>in general, and two months later applied it to the control of ten cards for two poker hands in <a href="http://www.maa.org/community/maa-columns/past-columns-card-colm/better-poker-hands-guaranteed" style="color: #330099; font-weight: bold;" target="200606">Better Poker Hands Guaranteed</a>, specifically in "Better Poker Hands with Bill Simon." The probabilistic considerations there can be ignored however; we know what we're dealing with here, and there's only one card to control.</span></li><li><span style="font-family: inherit;">It was also in the <a href="http://www.maa.org/community/maa-columns/past-columns-card-colm/better-poker-hands-guaranteed" style="color: #330099; font-weight: bold;" target="200606">June 2006 <i>Card Colm</i></a>, that we introduced a <b>Position Parity</b> method of controlling card distribution for two poker hands, in "Martin Gardner's Coins to Cards Effect," and "Better Poker Hands with Martin Gardner."</span></li><li><span style="font-family: inherit;">In the <a href="http://www.maa.org/community/maa-columns/past-columns-card-colm/monge-shuffle-cliques" style="color: #330099; font-weight: bold;" target="200606">October 2008 <i>Card Colm</i></a>, we explored the <b>Monge Shuffle</b>, which is an in-hand way to mix cards.<br /><br />As seen in "Better Poker Hands With Gaspard Monge" there, it's especially interesting for a packet of ten cards, because the cards in positions two, five and eight just keep cycling around, and the one in position four doesn't move at all. So the ten cards can be subjected to as many Monges as the victim asks for, and assuming the Jonah card started in one of the four key positions just mentioned, it's still in one of those slots. The losing hand can be teased out using a spelling routine as suggested in that 2008 column, but a much easier option is available.</span></li></ol><span style="color: #674ea7; font-family: inherit; font-size: x-large;">Something New</span><br /><ol style="font-size: 13px;"><li><span style="font-family: inherit;">When using <b>Bill Simon's 64 Principle</b>, simply start with the Jonah card in any of positions three to six from the top of the packet of ten cards. Plenty of innocent-looking in-hand shuffling can be done which preserves that key fact, before launching into the "free-choice" phase.</span></li><li><span style="font-family: inherit;">To implement the <b>Position Parity</b> method, pay attention to which end of the row of ten the selections start from, and who picks first. That way, you control everything just by knowing if the Jonah card starts in an even- or odd-numbered position. Additional shuffling of various types can be done which won't change the outcome, for instance, experiment with running off---into a waiting hand---either an even or odd number of cards, and putting them back at the face or behind the remainder. (Start with alternating Black and Red cards to get a feel for the possibilities.)</span></li><li><span style="font-family: inherit;">It's easiest of all to <b>Monge Shuffle</b> repeatedly: arrange it so that the Jonah card is in the position four at the outset. It stays there throughout any number of Monges, so that when the victim is satisfied that the cards are mixed, you can either say, "You take the top five, I'll take the rest, let's see how we did," or deal into two piles, alternating, making sure the victim gets the second one. You could even add more layer of deception in the dealing situation; asking for one of the piles to be indicated, saying, ``You want me to have that pile? Fine," if it's the first one, and "That's the pile you want? Okay," if it's the second one.</span></li></ol><span style="font-family: verdana, arial, helvetica, sans-serif; font-size: x-small;"><br /></span></div>Mathematical Association of Americahttp://www.blogger.com/profile/10559021045290192742noreply@blogger.com0tag:blogger.com,1999:blog-1124742229498315339.post-47004370226273115922012-04-30T16:32:00.001-04:002013-07-30T11:58:01.803-04:00Splitting the Pot<br /><center><i><span style="font-family: inherit;">Dedicated to the memory of <a href="http://mathdl.maa.org/mathDL?pa=mathNews&sa=view&newsId=1301" style="color: #330099;" target="tom">Thomas M. Rodgers (1944-2012)</a></span></i></center><div><br /></div><br /><span style="font-family: inherit;"><span style="background-color: white;">In the February 2012 </span><i>Card Colm</i><span style="background-color: white;">, </span><a href="http://cardcolm-maa.blogspot.com/2012/02/amazon-arrays-large-action.html" style="color: #330099;" target="201202">Amazon Arrays (Large Action)</a><span style="background-color: white;">, we considered 4 by 4 arrays such as, </span></span><br /><div class="separator" style="clear: both; text-align: center;"><a href="http://maa.org/columns/colm/cardcolm201204-1.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><span style="font-family: inherit;"><img border="0" src="http://maa.org/sites/default/files/images/columns/colm/cardcolm201204-1.jpg" height="320" width="252" /></span></a></div><span style="font-family: inherit;"><span style="background-color: white;">Each row (and each column) contains each suit once, and each row (and each column) contains each of the four values Jack, Queen, King & Ace once. Hence we have an example of an orthogonal (or Graeco) Latin square, which can be dealt from a packet of sixteen cards in four columns and rows from left to right. </span><br /><br /><span style="background-color: white;">Gather these cards together, shuffle, and again deal face-up left to right into four rows and columns. (Overlap a bit vertically, to facilitate later top-to-bottom gathering by columns.) It's likely to end up with an array such as the following, devoid of the special characteristics of the last one.</span></span><br /><span style="background-color: white; font-family: inherit;"><br /></span><br /><div class="separator" style="clear: both; text-align: center;"><a href="http://maa.org/columns/colm/cardcolm201204-2.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><span style="font-family: inherit;"><img border="0" src="http://maa.org/sites/default/files/images/columns/colm/cardcolm201204-2.jpg" height="246" width="320" /></span></a></div><span style="font-family: inherit;"><span style="background-color: white;">Yet, some structure remains. Can you see what it is? </span></span><br /><span style="font-family: inherit;"><span style="background-color: white;"><br /></span></span><br /><center><i><span style="font-family: inherit;">No matter how the cards are dealt, it's possible to pick out one from the first column,<br />another from the second, a third from the next one and a final one from the fourth,<br />so that overall we have selected one Jack, Queen, King and Ace, in some order.</span></i></center><span style="font-family: inherit;"><br /><span style="background-color: white;">The same now holds for the remaining columns of three cards on the table, and the columns of two cards that result when those four cards are removed, and so on until we have just one card of each value remaining, in a single left-to-right row. It's instructive to confirm these claims, one by one, for the array above. To understand why it's all true, perhaps work up from 2 by 4 arrays of two Jacks, Queens, Kings and Aces, to 4 by 4 arrays of four of each. </span><br /><br /><span style="background-color: white;">The highlighted claim above is equivalent to saying that it's possible to reorder the cards within each column, so that each resulting row contains one card of each value. </span><br /><br /><span style="background-color: white;">We are not claiming that the first Jack in the last row above can be replaced by a King above it; that would be too much to ask for. However, the second Jack in the last row can be replaced by the King three cards above it, so all is well. </span></span><br /><span style="font-family: inherit;"><br /></span><span style="font-family: inherit;"><span style="background-color: white;">The highlighted claim above is equivalent to saying that it's possible to reorder the cards within each column, so that each resulting row contains one card of each value. </span><span style="background-color: white;">Here is the result of four column reorderings</span><span style="background-color: white;">—</span><span style="background-color: white;">among several possible ones for each column-</span><span style="background-color: white;">—</span><span style="background-color: white;">for the last 4 by 4 array. It utilizes the switch just suggested:</span></span><br /><div class="separator" style="clear: both; text-align: center;"><a href="http://maa.org/columns/colm/cardcolm201204-3.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><span style="font-family: inherit;"><img border="0" src="http://maa.org/sites/default/files/images/columns/colm/cardcolm201204-3.jpg" height="256" width="320" /></span></a></div><div class="separator" style="clear: both; text-align: -webkit-auto;"><span style="font-family: inherit;"><span style="background-color: white;">Of course everything just claimed about random arrangements of these sixteen cards holds true if the words "row" and "column" are interchanged throughout, or if we focus of the four suits rather than the four card values in question. </span><br /><br /><span style="background-color: white;">However, as we move forward, we concentrate on the occurrences of distinct card values from left to right, across columns, there being corresponding observations for suits from top to bottom, across rows. </span><br /><br /><span style="background-color: white;">Is this all a special property of square arrays? To find out, let's pick up the cards, throw in the four 10s too, shuffle the resulting packet of size twenty, and deal out left to right into five face-up columns of four cards. Something like this will be seen: </span></span></div><div class="separator" style="clear: both; text-align: center;"><a href="http://maa.org/columns/colm/cardcolm201204-4.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><span style="font-family: inherit;"><img border="0" src="http://maa.org/sites/default/files/images/columns/colm/cardcolm201204-4.jpg" height="217" width="320" /></span></a></div><span style="font-family: inherit;"><span style="background-color: white;">Once again, some structure is evident. As above, it's possible to pick out one card from each row, to that overall we have one of each suit. Also, extending what we had above, </span></span><br /><br /><br /><br /><center><i><span style="font-family: inherit;">No matter how the cards are dealt, it's possible to pick out one from each column ,<br />so that overall we have selected one 10, Jack, Queen, King and Ace, in some order.</span></i></center><span style="font-family: inherit;"><br /><span style="background-color: white;">The same now holds for the remaining columns of three cards on the table, and the columns of two cards that result when those four cards are removed, and so on. It's worth confirming these claims for the array above. </span><br /><br /><span style="background-color: white;">Of course, it's all equivalent to saying that it's possible to reorder the cards within each column, so that each resulting row contains one card of each value. Can you perform five such column reorderings for the last 5 by 4 array? </span><br /><br /><span style="background-color: white;">Let's not stop there. Shuffle the entire deck, and deal into thirteen columns of four cards. It should not come as a surprise that no matter how the cards are dealt, it's possible to pick out one from each column so that overall we have selected one 2, 3, 4, ..., 10, Jack, Queen, King and Ace, in some order. It's also possible to pick one card from each row to end up with one of each suit. Similar observations apply to the scaled-down arrays resulting as the desired sets of card are removed. </span></span><br /><span style="font-family: inherit;"><br /><span style="background-color: white;">So, what's going on?</span><span style="background-color: white;"> </span><a href="https://twitter.com/#!/search/colinthemathmo" style="color: #330099;" target="colin">Colin Wright</a><span style="background-color: white;"> kindly alerted us to a tie in with Philip </span><a href="http://en.wikipedia.org/wiki/Hall%27s_marriage_theorem#Applications" style="color: #330099;" target="hmt">Hall's Marriage Theorem</a><span style="background-color: white;">. David Leep & Gerry Myerson consider this application in their 1999 </span><i>American Mathematical Monthly</i><span style="background-color: white;"> paper </span><a href="http://www.jstor.org/discover/10.2307/2589146" style="color: #330099;" target="leep">Marriage, Magic & Solitaire</a><span style="background-color: white;">. Most of the proof can also be found online on page 7 of </span><a href="http://www-math.mit.edu/~djk/18.310/Lecture-Notes/MatchingProblem.pdf" style="color: #330099;" target="leep">Notes on Matching</a><span style="background-color: white;"> by Jonathan Hirata. </span><br /><br /><span style="background-color: white;">Can you find a more elementary (or direct) proof in the case of <i>n</i> by <i>m</i> arrays of cards as considered above?</span></span><br /><div><br /><h3> <span style="font-family: inherit; font-size: x-large;">Deal/Ply/Finagle, Live</span></h3><div></div><div><span style="font-family: inherit;"><span style="background-color: white;">Ask for four poker players to step forward. Hand the 10s, Jacks, Queens, Kings and Aces to the first of them, and have that packet of cards shuffled and dealt into five overlapping face-up columns of four cards each. Comment briefly on the arrangement that results, and quickly pick up the columns one by one, gathering from top to bottom, shuffling each in hand before dropping it in a face-down pile. Gather the piles in any order, perhaps asking others for input along the way. </span><br /><br /><span style="background-color: white;">Hand the packet back to the first player and have it dealt again, but this time into </span><i>four overlapping face-down columns of five cards</i><span style="background-color: white;"> each. Pick up one of the columns and hand it to the player, saying, "These cards are destined for you. Please don't look at them yet." </span><br /><br /><span style="background-color: white;">Gather up the remaining fifteen cards and hand them to the second player to shuffle and deal into five overlapping face-up columns of three cards each. Again comment on the arrangement that results, and quickly pick up the columns one by one, gathering from top to bottom, shuffling each in hand before dropping it in a face-down pile. Gather the piles as before. </span><br /><br /><span style="background-color: white;">Hand the packet back to the second player to deal into </span><i>three overlapping face-down columns of five cards each</i><span style="background-color: white;">. Pick up one of the columns and hand it to the second player, saying, "These cards are destined for you. We'll look at them later." </span><br /><br /><span style="background-color: white;">Gather up the remaining ten cards and hand them to the third player to shuffle and deal into five overlapping face-up columns of two cards each. Quickly pick up the columns one by one, gathering from top to bottom, shuffling each in hand before dropping it in a face-down pile. Gather the piles as before. </span><br /><br /><span style="background-color: white;">Hand the packet to the fourth player, saying "Let's get you involved too," and have it dealt into </span><i>two overlapping face-down columns of five cards each</i><span style="background-color: white;">. Say, "There are two poker hands here, you get to pick which one you want." The other one is then given to the third poker player. </span><br /><br /><span style="background-color: white;">Stress the randomness of all than has taken place, the repeated shuffling, the fact that the cards were out of your hands, and so on. The last point is not entirely true of course, but you can point out that you shuffled the piles as you gathered them, and others decided in what order they were collected. </span><br /><br /><span style="background-color: white;">Have the four poker players inspect their cards. They should all have straights: a 10, Jack, Queen, King and Ace, with the suits jumbled randomly. End with some congratulations, and "I guess you'd split the pot if this was a real game." </span><br /><br /><span style="background-color: white;">Should one or more person happen to have straights in just one suit, this is extra reason for celebration; act like it was entirely expected. </span><br /><br /><span style="background-color: white;">How can such order be wrestled from chaos? There are two secrets here: your knowledge of the principle discussed earlier, and some hitherto unmentioned details as to exactly how you shuffle those columns as you gather them up! </span><br /><br /><span style="background-color: white;">Let's suppose that the initial display of cards is the one seen earlier above: </span></span></div><div><span style="background-color: white; font-family: inherit;"><br /></span></div><div class="separator" style="clear: both; text-align: center;"><span style="font-family: inherit; margin-left: 1em; margin-right: 1em;"><a href="http://maa.org/columns/colm/cardcolm201204-5.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="http://maa.org/sites/default/files/images/columns/colm/cardcolm201204-5.jpg" height="213" width="320" /></a></span></div><div class="separator" style="clear: both; text-align: center;"><br /></div><div><span style="font-family: inherit;"><span style="background-color: white;">Quickly scan horizontally, seeking a complete row, namely one of each of the five values, or a relatively complete row, such as the third row above, or maybe just focus on the last row, which has three Queens here. There are three possibilities to consider. </span><br /><br /><span style="background-color: white;">If a complete row is spotted, say the second one, then gather up the columns in any order, and after the cards are dealt again, face down, have the second column of five cards given to the first player as a poker hand. </span><br /><br /><span style="background-color: white;">If a relatively complete row such as the third one above catched your attention, then conspire to have the Queen at the bottom of the third column there switched with the King above it as the columns are gathered up; which results in the third column of five cards dealt being a suitable poker hand for the first player. </span><br /><br /><span style="background-color: white;">Perhaps a more convincing approach, however, is to focus on the final row: if the Queens at the bottom of the second and third rows could respectively be switched for either of the 10s or Kings above them all would be well, allowing for gathering in any order and dealing and finally setting aside the last resulting column of five cards as the poker hand for the first player. The same effect can be achieved as follows: gather up the first column and do some casual in-hand shuffling of these four cards, discretely peeking at the bottom and only stopping when the Ace is back there. Place the cards face down in a pile on the table, and repeat for the second column, this time shuffling until either of the two 10s are spotted at the bottom. For the third column it's a King that needs to end up on the bottom. For the last two columns, either the card already at the bottom, or a card of the same value, needs to end up there. In any event, it's the final column of five cards dealt that forms a suitable poker hand. </span><br /><br /><span style="background-color: white;">Of course the poker players don't know where this is going, and hence don't know what to look out for, so you can probably get away with it. The same strategy is applied in later rounds. The frequent shuffling by the players, and the random order in which the piles are collected by you, seems to add to the fairness, but neither has the slightest impact on the outcome. </span><br /><br /><span style="background-color: white;">Curiously, "A Gatherer Memoir" is an anagram of "Marriage Theorem." Two decades ago, </span><a href="http://mathdl.maa.org/mathDL?pa=mathNews&sa=view&newsId=1301" style="color: #330099;" target="mg">Thomas M. Rodgers</a><span style="background-color: white;"> was the original gatherer for Gardner; of fans of mathematics, magic, puzzles and more. The </span><a href="http://www.g4g.com/" style="color: #330099;" target="g4g">Gathering for Gardner</a><span style="background-color: white;"> conferences he helped to start have grown into tremendously stimulating, innovative, and wide-ranging affairs, bringing together creative like-minded souls in the arts, mathematics and related fields. </span><br /><br /><span style="background-color: white;">The </span><a href="http://www.g4g.com/" style="color: #330099;" target="g4g">Gathering for Gardner</a><span style="background-color: white;"> offshoot concept, </span><a href="http://www.g4g-com.org/" style="color: #330099;" target="com">Celebration of Mind</a><span style="background-color: white;">, another product of Tom's vision and energy, with even more potential to make an impact far into the future, takes place worldwide every October. These events are free and open to all. Please participate by either attending or hosting one yourself! </span><br /><br /><span style="background-color: white;">Thanks to </span><a href="https://twitter.com/#!/search/colinthemathmo" style="color: #330099;" target="colin">Colin Wright</a><span style="background-color: white;"> for the initial inspiration this month. </span><br /><br /><span style="background-color: white;">"Deal/Ply/Finagle, Live" is an anagram of "A Level Playing Field." </span></span></div></div>Mathematical Association of Americahttp://www.blogger.com/profile/10559021045290192742noreply@blogger.com0tag:blogger.com,1999:blog-1124742229498315339.post-85754853487108143652012-02-29T17:17:00.000-05:002014-03-04T07:35:28.710-05:00Amazon Arrays (Large Action)Consider the following 4 by 4 array, which is one solution to an old challenge revived in <a href="http://www.jimwilder.com/2011/05/25/math-square-with-cards" target="wl">Jim Wilder's fun blog</a>.<br /><br /><center> <img src="http://www.maa.org/sites/default/files/images/columns/colm/card24.gif" height="100" /> <img src="http://www.maa.org/sites/default/files/images/columns/colm/card13.gif" height="100" /> <img src="http://www.maa.org/sites/default/files/images/columns/colm/card51.gif" height="100" /> <img src="http://www.maa.org/sites/default/files/images/columns/colm/card36.gif" height="100" /><br /> <img src="http://www.maa.org/sites/default/files/images/columns/colm/card10.gif" height="100" /> <img src="http://www.maa.org/sites/default/files/images/columns/colm/card25.gif" height="100" /> <img src="http://www.maa.org/sites/default/files/images/columns/colm/card39.gif" height="100" /> <img src="http://www.maa.org/sites/default/files/images/columns/colm/card50.gif" height="100" /><br /> <img src="http://www.maa.org/sites/default/files/images/columns/colm/card38.gif" height="100" /> <img src="http://www.maa.org/sites/default/files/images/columns/colm/card49.gif" height="100" /> <img src="http://www.maa.org/sites/default/files/images/columns/colm/card11.gif" height="100" /> <img src="http://www.maa.org/sites/default/files/images/columns/colm/card26.gif" height="100" /><br /> <img src="http://www.maa.org/sites/default/files/images/columns/colm/card52.gif" height="100" /> <img src="http://www.maa.org/sites/default/files/images/columns/colm/card37.gif" height="100" /> <img src="http://www.maa.org/sites/default/files/images/columns/colm/card23.gif" height="100" /> <img src="http://www.maa.org/sites/default/files/images/columns/colm/card12.gif" height="100" /><br /> </center><br /><br />Such "orthogonal Latin squares" have a long history, going back at least as far as Jacques Ozanam in 1725, and were again considered by magician Jean Hugard fifty years ago.<br /><br />The above array can be dealt from a suitable packet of sixteen cards in four rows from left to right, where we suggest that the cards in each column overlap a little to facilitate subsequent gathering by columns.<br /><br />Actually this array was derived from the solution which Jim Wilder gave (<a href="http://jwilder.edublogs.org/files/2011/05/matrixsolution-qc5s46.jpg" target="wl">linked from his blog</a>) by repeated application of these steps: gather up each column of that array, from top to bottom, and re-assemble the packet by collecting the columns in any order, and deal again from left to right, then once more collect the columns in any order, and so on.<br /><br />Further applications of this type of mixing yields the array below:<br /><br /><br /><center> <img src="http://www.maa.org/sites/default/files/images/columns/colm/card26.gif" height="100" /> <img src="http://www.maa.org/sites/default/files/images/columns/colm/card49.gif" height="100" /> <img src="http://www.maa.org/sites/default/files/images/columns/colm/card38.gif" height="100" /> <img src="http://www.maa.org/sites/default/files/images/columns/colm/card11.gif" height="100" /><br /> <img src="http://www.maa.org/sites/default/files/images/columns/colm/card50.gif" height="100" /> <img src="http://www.maa.org/sites/default/files/images/columns/colm/card25.gif" height="100" /> <img src="http://www.maa.org/sites/default/files/images/columns/colm/card10.gif" height="100" /> <img src="http://www.maa.org/sites/default/files/images/columns/colm/card39.gif" height="100" /><br /> <img src="http://www.maa.org/sites/default/files/images/columns/colm/card36.gif" height="100" /> <img src="http://www.maa.org/sites/default/files/images/columns/colm/card13.gif" height="100" /> <img src="http://www.maa.org/sites/default/files/images/columns/colm/card24.gif" height="100" /> <img src="http://www.maa.org/sites/default/files/images/columns/colm/card51.gif" height="100" /><br /> <img src="http://www.maa.org/sites/default/files/images/columns/colm/card12.gif" height="100" /> <img src="http://www.maa.org/sites/default/files/images/columns/colm/card37.gif" height="100" /> <img src="http://www.maa.org/sites/default/files/images/columns/colm/card52.gif" height="100" /> <img src="http://www.maa.org/sites/default/files/images/columns/colm/card23.gif" height="100" /><br /> </center><br /><br />This shares two crucial properties with the first array above and the one at Wilder's link: Each row (and each column) contains each suit once, and each row (and each column) contains each of the four values J, Q, K, A once.<br /><br />Natural questions arise, which we leave interested readers to ponder: <br /><ol><li>Are these properties preserved under <em>all</em> such mixing, independently of the order in which the columns are collected? (Note that collecting the columns in left to right order and dealing left to right again is equivalent to matrix transposition across the diagonal).</li><li>What characterises arrays of four cards of each suit so that they have the desired two properties? How can we construct one? (The September/October 1961 issue of <strong>Hugard's MAGIC Monthly </strong>has a nice answer to the last question on page 11).</li><li>How many different arrays of four cards of each suit are there having the desired two properties? (Say, up to reflection and rotation?)</li><li>Can each possible array be obtained from any other one, such as the first one above, by repeatedly collecting columns in some order and dealing over?</li><li>Are other "four representatives" properties preserved, involving say the middle four cards or the four corners? Or the main diagonals? If not, would they be if we restricted the allowable permutations of the columns pickup to those of even sign?</li></ol><h2><span style="font-size: large;"><br /></span></h2><h2> <span style="font-size: large;"> Tragic Alone</span></h2>Instead of dealing cards face up and using notable values such as J, Q, K and A as above, one could deal face down and use other innocuous values, for instance: 2, 3, 5, 8.<br /><br />Start with an appropriate face-down array, perhaps dealt from the top of a supposedly shuffled deck--mix the rest of the cards all you want while maintaining the top stock. Have the sixteen key cards mixed further by collecting columns and dealing out again as above. Ask a spectator to point at any card, then place a small object such as a glass over it. Have the other three cards in the row (or column) containing the special card pulled to one side, then have them plunged one by one into the rest of the deck. Shuffle again, and then let these thirty-nine cards drop to your side in one hand, and request that the twelve remaining cards on the table (not counting the special one) be gathered up and given to you. Shuffle those in as well, and finally announce that with a quick scan of the card faces you will determine which card is missing.<br /><br />Turn around so nobody can see as you fan the cards. You promptly name the card under the glass. The deck can be handed out for inspection; all the evidence of what went on is gone.<br /><br />All you need to know is the three values and three suits represented among the three other cards in the row (or column) containing the special card. When you offer the deck to have those three cards plunged in, have it face up but with a face-down card at that end to hide that fact. Flip it back over before the other twelve cards are inserted. At the end, you run through the "face-down" deck to locate the three face-up cards, which will reveal all. Finally flip them over again match the orientation of the rest of the cards, before you turn around and announce what the hidden card is.<br /><br />Alternatively, you may wish to skip all the subterfuge and simply ask to see the other three cards in the row (or column) containing the special card; however in this case, gather up the other twelve cards in the array and shuffle them into the rest of the deck, before anyone has a chance to note that only four values are being used. <br /><br /><h2> <span style="font-size: large;"> Genial Actor</span></h2>The card values 2, 3, 5, 8 have another special property explored in <a href="http://www.maa.org/community/maa-columns/past-columns-card-colm/additional-certainties" target="200802">Additional Certainties</a>, the February 2008 <em>Card Colm</em>, and <a href="http://www.maa.org/community/maa-columns/past-columns-card-colm/two-summer-difference-certainties" target="200906">Two Summer Difference Certainties</a>, the June 2009 <em>Card Colm</em>. Namely, if two of them are selected and their sum is reported to you, then you know what both of them are. Can this be exploited in conjunction with the earlier ideas above? <br /><br /><h2> <span style="font-size: large;"> Certain Goal</span></h2>The arrays considered throughout are of course magic squares, and as such can be employed in the usual prediction and forcing stunts, e.g., see <a href="http://www.maa.org/community/maa-columns/past-columns-card-colm/quasi-masked-forcing-kind-of-magic-squares" target="200702">Quasi-Masked Forcing Kind of Magic Squares</a>, the February 2007 <em>Card Colm</em>.<br /><br />"Amazon" is an anagram of "Ozanam;" whereas "Large Action," "Tragic Alone," "Genial Actor," and "Certain Goal," are all anagrams of "Graeco Latin".<br /><br />Thanks to Jim Wilder for the initial inspiration, and also to Alexander Bogomolny of<strong> </strong><a href="http://www.cut-the-knot.org/Curriculum/Algebra/Latin.shtml" target="ctk">Cut-the-Knot</a> for helpful input.<br /><br />Colm Mulcahy (<a href="mailto:colm@spelman.edu">colm@spelman.edu</a>) completed his PhD at Cornell in 1985, under <a href="http://www.spelman.edu/~colm/alexrosenbergobit.html" target="alex">Alex F.T.W. Rosenberg</a>. He has been in the department of mathematics at Spelman College since 1988, and writing <em>Card Colms</em>—the only MAA columns to actively encourage lying on a regular basis—bi-monthly since October 2004. For more on mathematical card tricks, including a guide to topics explored in previous <strong>Card Colm</strong>s, see <a href="http://www.spelman.edu/~colm/cards.html">http://www.spelman.edu/~colm/cards.html</a>.<br /><br />Follow Card Colm on Twitter at <a href="http://twitter.com/cardcolm">@CardColm </a>Mathematical Association of Americahttp://www.blogger.com/profile/10559021045290192742noreply@blogger.com0tag:blogger.com,1999:blog-1124742229498315339.post-8221079553964087332011-12-16T16:38:00.000-05:002013-07-30T12:02:32.278-04:00Magical Mathematics: Recurring Cycles of Ideas of CyclesIn the December 2008 <em>Card Colm</em> <a href="http://www.maa.org/columns/colm/cardcolm200901.html">What's Black and Red and Red All Over?</a>, we borrowed from a chapter by Persi Diaconis & Ron Graham in the Martin Gardner tribute <a href="http://www.crcpress.com/ecommerce_product/product_detail.jsf?isbn=9781568812458" target="akp">A Lifetime of Puzzles</a><strong> </strong>(AK Peters), presenting a simplified version of a <a href="http://wordplay.blogs.nytimes.com/2011/12/05/numberplay-the-math-behind-the-magic" target="nyt">terrific card trick</a> which the first book author has been performing in public lectures for many years.<br /><br />The basic binary de Bruijn sequence material from that book chapter was, in turn, a preview of Chapter Two ("In Cycles") of the new, long-awaited, book <a href="http://press.princeton.edu/titles/9510.html" target="pup">Magical Mathematics: The Mathematical Ideas that Animate Great Magic Tricks</a> (Princeton University Press), a truly stunning exposition by two masters in the field.<br /><br />With the kind permission of the authors, we wrap up 2011 with a stroll through further "de Bruijn sequence" styled card magic, this time from Chapter Four ("Universal Cycles") of the new volume.<br /><br /><h2> <span style="font-size: large;">Invariably Factor</span></h2>The card tricks considered in the <a href="http://www.maa.org/community/maa-columns/past-columns-card-colm/whats-black-and-red-and-red-all-over">December 2008 <em>Card Colm</em></a> concerned circular arrangements of <em>2<sup>k</sup></em> Black and Red cards (or 0s and 1s), half of each, with the property that sliding windows of <em>k</em> adjacent cards (or bits), obtained by starting anywhere in the circle and proceeding around it in one fixed direction, cycle through all possible arrangements of Black and Red (or 0s and 1s), in some order, each of the <i style="background-color: white; font-family: verdana, arial, helvetica, sans-serif; font-size: 13px;">2<sup>k</sup></i> of these occurring exactly once. For example, the circle obtained by joining the ends of 0, 0, 0, 1, 1, 1, 0, 1 has the desired property for sliding windows of length 3.<br /><br />The basic application is to a packet of say, 16 Black and 16 Red cards, suitably arranged, memorised, and then cut (namely, cycled) arbitrarily often. If five adjacent cards are selected from the resulting circle of 32 cards, it's possible to correctly identify all of them merely by finding out which ones are Red. Powers of 2 play a major role here; note that 32 = <span style="background-color: white; font-family: verdana, arial, helvetica, sans-serif; font-size: 13px;">2</span><sup style="background-color: white; font-family: verdana, arial, helvetica, sans-serif;">5</sup> . Such de Bruijn sequences exist for any power of 2, and we also know how many there are. However, extending a trick like that just mentioned to a regular deck of 52 cards, necessarily being told which of <em>six</em> adjacent cards are Red, is a challenge, due to the desire to have the two ends of the deck connect up while preserving the moving window property.<br /><br />In mathemagic, as in mathematics itself, there is a delightful give and take between powers of 2 (counting binary arrangements allowing repetition) and factorials (counting permutations, i.e., arrangements of numerous things without repeats). While it generally holds that <i style="background-color: white; font-family: verdana, arial, helvetica, sans-serif; font-size: 13px;">2<sup>k</sup> < k!</i>, this isn't true for some small <em>k</em>. Indeed, in the February 2005 <em>Card Colm</em> <a href="http://www.maa.org/community/maa-columns/past-columns-card-colm/fitch-four-glory">Fitch Four Glory</a>, we exploited the fact that <i style="background-color: white; font-family: verdana, arial, helvetica, sans-serif; font-size: 13px;">2<sup>3</sup> > 3!</i> to "extend" the classic two person <a href="http://www.maa.org/horizons/Fitch-Cheney-Mulcahy.PDF">Fitch Cheney five card trick</a> from five to four cards. The original trick from the late 1940s took advantage of permutations, applied to the relative ranks within the deck of three of four displayed cards; the four card version from 1999 uses 3-bit arrangements, based on the face-up or face-down state of three displayed cards.<br /><br /><h2> <span style="font-size: large;">Rival Satellite</span></h2>There are occasions in decision making when one has to be very careful with comparisons: witness non-transitive dice or Condorcet paradoxes. Sometimes one makes judgement calls based on very local information, as in the situations now explored.<br /><br />Let's focus on the <em>relative ranks</em> of three adjacent values in a row or circle of numbers. There are six possibilities, namely the rank permutations LMH (representing Low, Medium, High), LMH, MLH, MHL, HLM, and HML. For instance, the circle obtained from 1, 2, 3, 4, 5, 6 (considered wrapped around to 1 again) produced LMH four times, then MHL and finally HLM.<br /><br />There are 5!/2 = 60 different (reversible and spinnable) circles using these six numbers. Of these, consider the one obtained by connecting the ends of <em>1, 4, 6, 2, 5, 3</em>:<br /><br /><br /><br /><br /><br /><br /><br /><center><table border=""> </table><br /><table border="0" colspan="13" style="height: 25px; width: 220px;"> <tbody><tr> <td></td> <td><h2> <span class="Apple-style-span">3</span></h2></td> <td></td> <td></td> <td></td> <td></td> <td></td> <td><h2> <span class="Apple-style-span">1</span></h2></td> <td></td> </tr><tr> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td> </tr><tr> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td> </tr><tr> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td> </tr><tr> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td> </tr><tr> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td> </tr><tr> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td> </tr><tr> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td> </tr><tr> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td> </tr><tr> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td> </tr><tr> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td> </tr><tr> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td> </tr><tr> <td><h2> <span class="Apple-style-span">5</span></h2></td> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td> <td><h2> <span class="Apple-style-span">4</span></h2></td> </tr><tr> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td> </tr><tr> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td> </tr><tr> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td> </tr><tr> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td> </tr><tr> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td> </tr><tr> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td> </tr><tr> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td> </tr><tr> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td> </tr><tr> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td> </tr><tr> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td> </tr><tr> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td> </tr><tr> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td> </tr><tr> <td></td> <td><h2> <span class="Apple-style-span">2</span></h2></td> <td></td> <td></td> <td></td> <td></td> <td></td> <td><h2> <span class="Apple-style-span">6</span></h2></td> <td></td> </tr><tr> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td> </tr><tr> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td> </tr></tbody> </table></center>This is highly desirable as it has real magic potential:<br /><br /><br /><br /><br /><br /><br /><br /><br /><center> <em>Each possible rank permutation of three objects occurs exactly once<br /><br /> considering the adjacent values: </em>{1, 4, 6}, {4, 6, 2}, ..., {3, 1, 4}<em><br /><br /> for the circle obtained by joining the ends of </em>1, 4, 6, 2, 5, 3.</center><br /><br />It follows that if three adjacent values of these six are chosen by different people, then one need only ask who has the largest and who has the smallest to be able to tell exactly which value each person has!<br /><br />Interested readers may wish to investigate if, upon reflection (or rotation), the indicated circle is unique. Incidentally, to remember that circle, we found it helpful to think of the area of a circle of radius 25 (can you see why?).<br /><br />Diaconis & Graham note that they found circles of length 4! = 24 and 5! = 120 for which sliding windows of length 4 and 5, respectively, cycle through all possible rank permutations of that many objects. They then conjectured, and eventually proved with the assistance of Fan Chung, that this could be done for any <em>k</em> in a suitable circle of length <em>k!</em>, although they report that their proof was difficult and non-constructive.<br /><br />The cards in ordinary decks are not naturally numbered up to 24 or 120 however, instead consisting of four suits of thirteen repeated values. Now imagine a deck with five suits, from which we assemble a packet of all five Aces, 2s, 3s and 4s, but only four 5s, having 24 cards total. Ignoring suits, one can also pull this off with cards from two ordinary decks. Then the circle obtained by connecting the ends of<br /><br /><br /><br /><br /><br /><br /><br /><center> <em>1, 2, 3, 4, 1, 2, 5, 3, 4, 1, 5, 3, 2, 1, 4, 5, 3, 2, 4, 1, 3, 2, 5, 4</em>,</center><br />has the following property:<br /><br /><br /><br /><br /><br /><br /><center><br /><em>Each possible rank permutation of four objects occurs exactly once<br /><br /> considering the adjacent values: </em>{1, 2, 3, 4}, {2, 3, 4, 1}, ..., {4, 1, 2, 3}.</center><br />(Notice that no ties are encountered above; however that possibility is also considered by Diaconis & Graham, a few pages later.)<br /><br />It follows that if four adjacent cards of these 24 are chosen by different people, then one need only ask who has the largest, who has the second largest and who has the third largest, to be able to tell exactly which value each person has!<br /><br />There is a reason Diaconis & Graham needed five copies of each card value above: a recent result of Robert Johnson establishes an earlier conjecture that <em>k + 1</em> is the smallest number of distinct values that can be assembled into a circular deck of <em>k!</em> cards so that the relative order of each group of <em>k</em> adjacent cards is distinct.<br /><br /><h2> <span style="font-size: large;">Warmed Linens</span></h2>There is much more fascinating material, both mathematical and magical, in the chapter "Universal Cycles" of the <a href="http://press.princeton.edu/titles/9510.html" target="pup">Magical Mathematics: The Mathematical Ideas that Animate Great Magic Tricks</a>; in truth we've only skimmed the surface. There are many other wonderful chapters in that book too.<br /><br />We'd be remiss if we didn't mention the Chapter Four opener, one of the superb co-creations with prolific magic inventor Ronald Wohl, which is presented there as motivation for the rank permutation explorations above. It uses the values in an ordinary deck. Here it is, stripped of all magic coating:<br /><br /><br /><br /><br /><br /><br /><br /><center><br /><em>From a pre-arranged and cut deck of 52 cards, five adjacent ones are selected by five people.<br /><br /> One is able to identify all five cards based only on the knowledge of who holds the top three in rank.</em></center><br /><div><br /></div>For instance, after much cutting, and some blather about how "well-mixed" the cards are, have five consecutive ones selected by as many people. Say something like, "Those are your scores, ladies and gentlemen. The highest one gets Gold, the next highest Silver, the third highest Bronze. I'm afraid that's it, the other ones don't get anything." Then hand out mock medals. As soon as you know who gets which one, and assuming you have somehow internalised or memorised the initial deck set-up, you can then name the exact card (not just the value) which each of the five people has.<br /><br />Why is there hope of pulling off such an effect? Basically because given any five adjacent cards, the number of Gold/Silver/Bronze arrangements of some three of them is 5x4x3 = 60, which is greater than 52, the number of cards (or possible positions) in a deck.<br /><br />How does one actually come up with such an arrangement in the first place? Very carefully. Good luck! Feel free to post solutions below, along with tips for remembering the resulting decks.<br /><br /><h2> <span style="font-size: large;">Critical Chum Runs</span></h2>It's interesting to note that Diaconis & Graham's <em>1, 4, 6, 2, 5, 3</em> also yields a <em>sum-rich circulant for triples</em> in the sense of <a href="http://www.maa.org/community/maa-columns/past-columns-card-colm/sum-rich-circulants">June 2008's <em>Card Colm</em></a>.<br /><br /><br /><br /><br /><br /><br /><br /><center><br /><table border=""> </table><br /><table border="0" colspan="13" style="height: 25px; width: 220px;"> <tbody><tr> <td></td> <td><h2> <span class="Apple-style-span">3</span></h2></td> <td></td> <td></td> <td></td> <td></td> <td></td> <td><h2> <span class="Apple-style-span">1</span></h2></td> <td></td> </tr><tr> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td> </tr><tr> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td> </tr><tr> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td> </tr><tr> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td> </tr><tr> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td> </tr><tr> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td> </tr><tr> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td> </tr><tr> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td> </tr><tr> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td> </tr><tr> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td> </tr><tr> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td> </tr><tr> <td><h2> <span class="Apple-style-span">5</span></h2></td> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td> <td><h2> <span class="Apple-style-span">4</span></h2></td> </tr><tr> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td> </tr><tr> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td> </tr><tr> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td> </tr><tr> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td> </tr><tr> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td> </tr><tr> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td> </tr><tr> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td> </tr><tr> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td> </tr><tr> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td> </tr><tr> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td> </tr><tr> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td> </tr><tr> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td> </tr><tr> <td></td> <td><h2> <span class="Apple-style-span">2</span></h2></td> <td></td> <td></td> <td></td> <td></td> <td></td> <td><h2> <span class="Apple-style-span">6</span></h2></td> <td></td> </tr><tr> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td> <td></td><td style="text-align: left;"><br /></td></tr></tbody></table></center>What we mean here is that the six possible sums of three adjacent values are distinct. In fact, we get sums 8, 9, 10, 13, 12, 11, as we go around the circle, based on the central element of each sum, so that 8 = 4 + 1 + 3 is listed first, followed by 9 = 1 + 3 + 5, etc. Notice that these sums are the six consecutive numbers 8, 9, 10, 11, 12, 13 in a very easy to remember order. Hence, given the sum, it's not hard to backtrack and deduce the identity of the three cards which gave rise to it.<br /><div><br /><h2> <span style="font-size: large;">Prominent Ace Proofs</span></h2>We suggest loading the top of a deck with six cards of the desired values, in any mixed suits you can remember, and maintaining them there throughout several fair-seeming shuffles. Alternatively, one could use the same six cards from two decks and maintain a top stack twice as large, one sequence of six card following the other. In any case, deal out six (or twelve) cards into a face-down circle and invite somebody to pick one card. A second person picks one of the cards beside it, and finally a third picks either of the two "exposed" cards in the broken circle. Have them compare cards and <em>either</em> report who has the highest and who has the lowest (or the Gold and the Silver), <em>or</em> announce the total of all three values.<br /><br />For that matter, you can throw in the option of being told "the mode, median or mean"! (Of course, the first case cannot occur, but only you know that.) As long as nobody says "Two" or "Four," all is well; you should be able to say who had which card. If "two" or "four" is called out, you need to fish to determine if it's a median or mean, before successfully concluding the trick.<br /><br />For the record, the circle of six numbers considered above is also product-rich for triples, so you could also request just the product. Only 12 turns up as both a sum and a product. <br /><br />"Invariably factor" is an anagram of "binary v. factorial," "rival satellite" is an anagram of "it's all relative," "warmed linens" is an anagram of "medal winners," "critical chum runs" is an anagram of "sum-rich circulant," and "prominent ace proofs" is an anagram of "performance options." We feel compelled to mention that "laden priors" is an anagram of "Persi Ronald" and "magicians hoard" is an anagram of "Diaconis Graham." </div>Mathematical Association of Americahttp://www.blogger.com/profile/10559021045290192742noreply@blogger.com0tag:blogger.com,1999:blog-1124742229498315339.post-35251834098952093832011-10-28T03:00:00.000-04:002013-07-30T12:03:31.233-04:00A Third Selection of Mathemagical Amusements with Cards in Martin Gardner's Own Words<div style="text-align: left;">Around this time of the year—his birthday was 21st October—people gather at various locations around the world for a <a href="http://www.celebrationofmind.org/">Celebration of Mind</a>, to enjoy the legacy and interests of renowned man of letters and numbers <a href="http://maa.org/pubs/gardnertribute.html">Martin Gardner</a> (1914-2010). There is still time to <a href="http://www.g4g-com.org/event-map-2011">attend</a> or <a href="http://www.g4g-com.org/g4g_com_hosting">host</a> one this year!</div>For a quarter of a century, from 1956 to 1983, Gardner wrote an extremely popular and influential monthly column called "Mathematical Games" for <em>Scientific American</em>. Last year here, we marked the passing of this intellectual giant and prolific writer with two selections of mathematical card tricks and entertainments—in his own words—from books <a href="http://www.maa.org/columns/colm/cardcolm201006.html">1-4</a> and <a href="http://www.maa.org/columns/colm/cardcolm201008.html">7 & 10</a> of the resulting 15 collections. This time, we sample further expositions on the topic from books 5, 11 & 12 of the series.<br />Incidentally, these books can be enjoyed in full, text searchable form on a CD-ROM available from the MAA called Martin Gardner's <a href="https://www.maa.org/EbusPPRO/DynamicSearch/ProductDetailsAdvancedSearch/tabid/176/ProductId/1585/Default.aspx">Mathematical Games</a>. Some of Martin's more famous columns from those years are accessible now at <a href="http://maa.org/pubs/focus/mg.html">MAA Online</a>. Personal reminiscences of the man (and more) can be found <a href="http://www.spelman.edu/~colm/mg.html">here</a>.<br />The crystal clear<em> words in italics</em> below are all Martin's, but the section headings are our own.<br /><h1>Facing Up</h1><div><br /></div>Chapter 14 of <strong><i>The 6th Book of Mathematical Diversions from Scientific American </i></strong>(1971) is called "Mathematical Magic Tricks." After describing a trick with pennies devised by Jack Yates, Martin writes:<br /><em>The following, contributed by the British magician Norman MacCleod to a magic magazine in the United States,</em> The New Phoenix<em> (No. 328, August, 1955), is one of the best. While someone deals the deck into four bridge hands the performer writes on a slip of paper: "There will be 22 face-up cards." This prediction is folded and placed aside. The spectator takes two of the piles, the magician takes the other two.</em><br /><em>"I have selected a number from one to ten," says the performer. "I shall turn that number of cards face up in each of my piles." He proceeds to turn some cards face up but without letting anyone see how many.</em><br /><em>The spectator is asked to do the same with his two piles: choose a number from one to tell and reverse that number of cards in each pile. The four piles are assembled, the deck spread and the face-up cards counted. There are 22. The prediction is unfolded and found to be correct.</em><br /><em>To perform this trick you must cheat a bit. Any even number between 13 and 30 can be written in your prediction. This number, minus 13, tells you the total number of cards to leave face down in your two packets. In this case 22 minus 13 is 9, so you reverse, say, all but 5 cards in one pile and all but 4 in the other. Put your two piles together and one of the spectator's piles on top. Hold this large packet in your left hand and ask the spectator to cut his remaining pile into two parts. While attention is focused on the cutting casually turn over your left hand, thus secretly reversing all its cards. This large pile is sandwiched between the two halves of the cut pile.</em><br /><em>All the cards are now together again and presumably no one knows how many of them are face up. Do you see why there must be 22? The procedure reverses 13 cards in the spectator's two piles for the same reason that Yates's coin trick works. The 9 cards you left face down are now face up, making 22 in all. The trick can be repeated using other even numbers in the prediction. Odd numbers should be avoided because the procedure, if it is done legitimately, could not produce an odd number of face-up cards.</em><br /><h1>Hard to Miss</h1><div><br /></div>In his book <strong><i>Knotted Doughnuts and Other Mathematical Entertainments</i></strong> (1986), following a discussion of the Birthday Paradox and variations, Martin writes:<br /><em>Another simple demonstration of an event that seems improbable but actually is not can be given with a deck of playing cards. Shuffle the cards, then deal them while you recite their names in a predetermined order, say ace to king of spades followed by the same sequence for hearts, clubs and diamonds. The probability that a card named in advance, such as the queen of hearts, will be dealt when it is named is 1/52, but the probability that at least one card will be dealt when named is almost 2/3. If you name only the values, the probability of a "hit" rises to 98 percent, or very close to certain.</em><br />(Another Martin Gardner inspired 98% likely "hit"—which is also related to the Birthday Paradox—can be found in <a href="http://www.maa.org/community/maa-columns/past-columns-card-colm/better-poker-hands-guaranteed">Better Poker Hands Guaranteed</a>, the June 2006 <strong>Card Colm</strong>.)<br /><h1>Non-Transitive Authority</h1><div><br /></div>In his book <strong><i>Time Travel and Other Mathematical Bewilderments</i></strong> (1988), Martin has a terrific chapter on non-transitive paradoxes. In this exposition of an amazing and counter-intuitive phenomenon, he included this card implementation:<br /><em>Many paradoxes of this type were jointly investigated by Leo Moser and J. W. Moon. Some of the Moser-Moon paradoxes underlie striking and little- known sucker bets. For example, let each row (or each column) of an order-3 magic-square matrix be a set of playing cards, say the ace, 6, and 8 of hearts for set A, the 3, 5, and 7 of spades for set B, and the 2, 4, and 9 of clubs for C. Each set is randomized and placed face down on a table. The sucker is allowed to draw a card from any set, then you draw a card from a different set.</em><br /><a href="http://1.bp.blogspot.com/-Ljx62-N3dW8/TqrQ0Ue34SI/AAAAAAAADdA/r4EiuGnL3gY/s1600/card%2Bfans.jpg" onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}"><img alt="" border="0" src="http://1.bp.blogspot.com/-Ljx62-N3dW8/TqrQ0Ue34SI/AAAAAAAADdA/r4EiuGnL3gY/s400/card%2Bfans.jpg" id="BLOGGER_PHOTO_ID_5668572678269165858" style="cursor: pointer; display: block; height: 400px; margin-bottom: 10px; margin-left: auto; margin-right: auto; margin-top: 0px; text-align: center; width: 205px;" /></a><br /><div><div style="text-align: center;"><span class="Apple-style-span"><u><br /></u></span></div><em>The high card wins. It is easy to prove that no matter what set the sucker draws from, you can pick a set that gives you winning odds of five to four. Set A beats B, B beats C, and C beats A. The victim may even be allowed to decide each time whether the high or the low card wins. If you play low card wins, simply pick the winning pile with respect to a nontransitive circle that goes the other way. A good way to play the game is to use sets of cards from three decks with backs of different colors. The packet of nine cards is shuffled each time, then separated by the backs into three sets.</em><br /><h1>Be There and Be Square</h1><div><br /></div>The "Combinatorial Card Problems" chapter from the same book contains a wealth of material to be explored with a deck of cards. As Martin observes,<br /><em>There is no end to the making of mathematical tricks, puzzles, and other recreations that employ playing cards. In this chapter we look at some new card problems and games, with emphasis on how they lead into significant areas of combinatorial theory.</em><br /><em>Consider the following combinatorial way of dramatizing an important number theorem. Remove all the cards of one suit (say, spades) from a deck and arrange them in serial order from ace to king. (The jack, queen, and king, respectively, represent 11, 12, and 13.) Place them face down in a row with the ace at the left. The following turning procedure is now applied, starting at the left at each step and proceeding to the right:</em><br /><ol><em><li>Turn over every card.</li><br /><li>Turn over every second card. (Cards 2, 4, 6, 8, 10, and Q are turned face down.)</li><br /><li>Turn over every third card.</li><br /><li>Continue in this manner, turning every fourth card, every fifth card, and so on until you turn over only the last card.</li></em></ol><a href="http://1.bp.blogspot.com/-cMR6xz_OO4I/TqrQ_q2OVsI/AAAAAAAADdM/naeQbJhXarc/s1600/card%2Brows.jpg" onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}"><img alt="" border="0" src="http://1.bp.blogspot.com/-cMR6xz_OO4I/TqrQ_q2OVsI/AAAAAAAADdM/naeQbJhXarc/s400/card%2Brows.jpg" id="BLOGGER_PHOTO_ID_5668572873251247810" style="cursor: pointer; display: block; height: 148px; margin-bottom: 10px; margin-left: auto; margin-right: auto; margin-top: 0px; text-align: center; width: 400px;" /></a></div><div><div style="text-align: left;"><em></em><br /><div style="display: inline !important;"><em>The high card wins. It is easy to prove that no matter what set the sucker draws Inspect the row. Note that all the cards except the ace, the 4, and the 9 are face down. These values happen to be square numbers. Is this an accident? Or is it an authentic hint of a general rule? A good classroom exercise is to prepare 100 small cards bearing numbers 1 through 100, stand them with their backs out in serial order on a blackboard ledge and apply the turning procedure. Sure enough, at the finish the only visible numbers will be the squares: 1, 4, 9, 16, 25, 36, 49, 64, 81, and 100. That is too large a sampling to be coincidental. The next step is to prove that no matter how large the deck, only squares survive the turning procedure.</em></div></div><em></em><br /><em>A simple proof introduces one of the oldest and most fundamental of number theorems: A positive integer has an odd number of divisors (the divisors include 1 and the number itself), if and only if the number is a square. This is easy to see. Most divisors of a number come in pairs. Consider 72. The smallest divisor, 1, goes into the number 72 times, giving the pair 1 and 72. The next-larger divisor, 2, goes into the number 36 times, giving the pair 2 and 36. Similarly, 72 = 3 x 24 = 4 x 18 = 6 x 12 = 8 x 9. The only divisor of a number that is not paired with a different number is a divisor that is a square root. Consequently, all nonsquares have an even number of divisors, and all squares have an odd number of divisors.</em><br /><br /><em>How does this apply to the row of cards? Consider the eight of spades in the first card-turning example. Since 8 is not a square, it has an even number of divisors: 1, 2, 4 , 8 . It will be turned four times: when you turn each card, each second card, each fourth card, and each eighth card. An even number of turns applied to a face-down card will leave that card face down. Since every nonsquare card will be turned an even number of times, it will be face down at the finish. The only cards that are turned an odd number of times and left face up are those with an odd number of divisors, namely the squares. Is there a better way to teach this basic number theorem in the memory of a high-school student than to have him witness such a demonstration?</em><br />Don't forget there is still time to <a href="http://www.celebrationofmind.org/">Celebrate the Mind</a>—<em>his and yours!</em>—in 2011, with card or other entertainments. Have fun!</div>Mathematical Association of Americahttp://www.blogger.com/profile/10559021045290192742noreply@blogger.com0tag:blogger.com,1999:blog-1124742229498315339.post-14193848135078845612011-08-31T15:59:00.000-04:002013-07-30T12:05:26.950-04:00A Call For A New Shuffle Principle (Need Rot Sextet?)<div style="text-align: left;">On this August occasion, to mark the completion of seven years of <em>Card Colm</em>s, we break with tradition and pose a question, rather than presenting some fresh mathematically based entertainments with cards.</div><span class="Apple-style-span">It's a question that's been on our mind for a long time, and we'd really like to know the answer.<br /></span><span class="Apple-style-span">By a happy coincidence, this month's offering also marks our first foray into the new blog format for MAA columns, so that readers with ideas to contribute have the option of responding publically in comments below.</span><br /><div><div><div><span class="Apple-style-span"><br /></span></div><div><span class="Apple-style-span"><span class="Apple-style-span" style="font-weight: bold;">One, Two, Many</span></span></div><div><span class="Apple-style-span"><br /></span></div><div><span class="Apple-style-span">Humans reading this column may have noticed that for some in our tribe there are essentially three counting numbers: One, Two, Many. The last is certainly the most confusing–perhaps our inability to track three things at the same time when rushed is why we do poorly at Three Card Monte (including those versions with minimal sleight of hand).<br /><br />In fact, it doesn't take much for us to lose track of even fewer objects, as tricksters of various shades have known for a long time. <em>Paddle moves</em> play with the brains of those of us foolish enough to think we know the difference between the two sides of an issue, and basic <em>misdirection</em> is all about getting people to take their eye of a single thing just long enough for the magician (or politician) to pull a fast one. There is rarely any need for smoke and mirrors.<br /><br />This month's <em>Card Colm</em></span><span class="Apple-style-span"> asks a challenging question concerning the shuffling of more than two piles of cards. We may be asking too much.</span></div><div><span class="Apple-style-span"><br /></span></div><div><span class="Apple-style-span"><span class="Apple-style-span" style="font-weight: bold;">Shove Integer</span></span></div><div><span class="Apple-style-span"><br /></span></div><div><span class="Apple-style-span">For those with a little knowledge of card shuffling, the following hypothetical exchange between two alphabetical sounding mathematicians, Aodh and Bea, may amuse:<br /><br />Aodh: <em>I've heard that seven shuffles is enough to randomize a standard deck of 52 cards.</em><br /><br />Bea: <em>I've heard that eight shuffles restores a standard deck of 52 cards to its original order.</em><br /><br />This raises a tantalizing question: what magical thing happens between the seventh and eighth shuffle to restore total order from sheer chaos? That would be a very impressive effect in itself!<br /><br />In fact, Aodh and Bea above are talking about rather different kinds of shuffles, though one generalizes the other.<br /><br />The first statement has some validity when it refers to an irregular riffle shuffle, subject to some strong assumptions.<br /><br />The second statement refers to a perfect shuffle, also known as "Faro" or "weave" shuffle, in which the deck is split in two at the middle, and the cards from the two halves are interlaced completely regularly, with the original top and bottom cards remaining in those positions (this is the so-called Out-Faro).<br /><br /><a href="http://en.wikipedia.org/wiki/Shuffling">Riffle shuffling</a>, in which the deck is split roughly in the middle, and the two resulting "halves" are interwoven by releasing cards from both thumbs at the same time, with no particular regularity, is a common way of mixing cards, being relatively easy to master.<br /><br />A famous 1992 paper by Dave Bayer and Persi Diaconis called <a href="http://projecteuclid.org/DPubS?service=UI&version=1.0&verb=Display&handle=euclid.aoap/1177005705">"Trailing the Dovetail Shuffle to its Lair"</a> concluded that seven riffle shuffles is sufficient to randomize a standard deck. A specific measure of randomness was used, and assumptions were made about the probabilistic distribution of how the cards are split, and how the two resulting packets are "released."<br /><br />Later on, others revisited this topic, with different measures of randomness and different probabilistic assumptions, reaching different conclusions. The topic continues to attract the attention of researchers, and today some argue that in fact eleven shuffles are required to really randomize a deck. This is not our concern here, so we leave it to the interested reader to pursue further, if desired.<br /><br />Let's return to the idea of a single riffle shuffle, making no assumptions whatsoever about how likely the deck is to be split at or near the middle, or how regularly the cards from the two parts are dropped. All we assume is that the shuffle preserves the order of the cards within each "half": for instance, if one packet of red cards in a specific order is shuffled into another packet of black cards in a specific order, then both the red and black subsequences of the resulting shuffled deck should preserve their original orders.<br /><br />Note that Lennart Green's rosette shuffle as depicted below is certainly a riffle shuffle, as we've mentioned here before. We should admit that this kind of shuffle has physical limitations governing the card mixing, so that not every possible riffle shuffle is actually achievable in this way.</span><br /><div><span class="Apple-style-span"><br /></span></div><div><span class="Apple-style-span" style="-webkit-text-decorations-in-effect: underline; color: #0000ee;"><img alt="" border="0" src="http://2.bp.blogspot.com/-7Dk3LHDLkPk/Tl6T5MclrtI/AAAAAAAADPk/7Q5T_V3GcbU/s400/card-aug1.gif" id="BLOGGER_PHOTO_ID_5647113593572142802" style="cursor: pointer; display: block; margin-bottom: 10px; margin-left: auto; margin-right: auto; margin-top: 0px; text-align: center; width: 600px;" /></span></div><div><div style="text-align: center;"><span class="Apple-style-span"><br /></span></div><span class="Apple-style-span">[Start with two piles side by side, as shown in the first image, then use the fingers to "twirl" the left pile into a rosette; the second image shows the result. Repeat for the right pile, and then push the rosettes together. Square up the packet: it has effectively been riffle shuffled.]<br /><br />It's a delightful surprise to learn that if we have a deck which</span><br /><ol><li><span class="Apple-style-span">Starts out with the cards alternating red and black, and</span></li><li><span class="Apple-style-span">Is split into two parts (of any size) one of which had a red card on the bottom, the other having a black card at the bottom,</span></li></ol><span class="Apple-style-span">then, if we subject it to a single riffle shuffle, it will end up with the property that every pair taken off the top (or bottom) will consist of one red and one black card, in some order. This is the so-called <a href="http://www.maa.org/community/maa-columns/past-columns-card-colm/the-first-norman-invasion">First Gilbreath Principle</a> from 1958.<br /><br />It's not hard to see that condition 2 above can be replaced with either of two alternatives: (2A) First dealing out some cards from the deck into a pile to form the second packet, instead of splitting as before, before shuffling, or, (2B) Splitting anywhere and shuffling, but then peeking at the card faces and cutting between two cards of like colour before peeling off pairs of cards.<br /><br />This generalizes from cycles of length <em>2</em> to arbitrary <em>n</em> general as follows:<br /><br />Start out with a deck of cards cycling in some regular fashion, for instance for <em>n = 13</em> we might have 4 stacked repeats of these cards in (alphabetical) order: Ace, 8, 5, 4, Jack, King, 9, Queen, 7, 6, 10, 3, 2 (ignoring suits).<br /><br />If some of the cards are dealt into a pile, thus reversing their order, and the resulting two packets are riffle (or rosette) shuffled together, then, we end with a deck with the property that the top (or bottom) 13 cards contain one of each value. This is the so-called <a href="http://www.maa.org/community/maa-columns/past-columns-card-colm/the-second-norman-invasion">Second Gilbreath Principle</a></span><span class="Apple-style-span"> from 1966.</span></div><div><span class="Apple-style-span"><br /></span></div><div><span class="Apple-style-span"><span class="Apple-style-span" style="font-weight: bold;">For Auto</span></span></div><div><br /></div><div><span class="Apple-style-span"><a href="http://en.wikipedia.org/wiki/Faro_shuffle">Faro shuffling</a>, in which the deck is split exactly in the middle, and the resulting half packets are perfected interlaced, is much, much harder to do in practice. [The key word here is <em>practice</em>–having once been shown for a solid hour "how to do it", by magician Mark Setteducati, a month's worth of frustrating and seemingly pointless practice suddenly led to an irreversible breakthrough.] If the top and bottom cards always remain in position—so that we are doing an Out Faro—it is well known that exactly eight such perfect shuffles restores a deck of 52 cards to its original order.<br /><br />A great deal of impressive card magic has been developed by those who've mastered Faro shuffling, some of which can be adapted to the easy-to-handle inverse operation of dealing cards into two piles alternately. A great deal indeed!<br /><br />S. Brent Morris has a terrific book <a href="https://www.maa.org/ebusppro/Bookstore/ProductDetail/tabid/170/Default.aspx?ProductId=557"><em>Magic Tricks, Card Shuffling, and Dynamic Computer Memories</em></a> from 1998 which not only surveys all of the key mathematics of such Faro shuffles, but also explores the mathematics resulting from <em>three</em> packets being perfectly interlaced (and he gives advice on how to do that in practice).<br /></span><span class="Apple-style-span">There is a question begging to be asked here.</span></div><div><span class="Apple-style-span"><br /></span></div><div><span class="Apple-style-span"><span class="Apple-style-span" style="font-weight: bold;">Restores Teeth</span></span></div><div><span class="Apple-style-span"><br /></span></div><div><span class="Apple-style-span">Since a Faro shuffle is a special case of a riffle shuffle—the neatest possible type—it follows that anything promised by the Gilbreath principles will also hold for a deck which has been Faro shuffled, with bells on.<br /><br />This brings us to our burning question (<em>brusque intoning</em>):</span><br /><center><span class="Apple-style-span"><br /><em>Is there a way to pre-arrange a deck and split it into three (or more) parts<br />so that some structure remains when they are "riffle shuffled" together?</em></span></center><span class="Apple-style-span"><br />Perhaps, following Lennart Green, a triple rosette shuffle of some sort can be executed on three parts of a deck so that the result is not totally chaotic? What kind of pre-arrangement would be required?<br /><br />Bear in mind that card reversal of one packet is not required when riffle shuffling a pre-arranged deck in the usual way, in order ro retain some predictability, as we saw here two years ago in <a href="http://www.maa.org/community/maa-columns/past-columns-card-colm/the-bligreath-principle">The Bligreath Principle</a>.<br /><br />If periodic cycling of some sort is appropriate—as it is in the case of splitting the deck into two packets before riffling—w<span class="Apple-style-span">ould the cycle length need to be a multiple of six? It seems that we must cover the case where two of the parts are riffled in the usual way and the third is merely appended at the top or bottom, <span style="font-size: 12pt;">which leads us to suspect that the cycle length must include factors of 2 and 3. </span></span><br /><br />Most importantly, is there any hope of finding an application to card magic?<br /><br />Or is it simply a case of <em>one too many</em> packets to shuffle?<br /><br />We'd love to hear from readers with ideas on this topic. Please feel free to use the comment option below.<br /><br />"Need rot sextet" is an anagram for "extend rosette," "shove integer" is an anagram for "seven or eight," "for auto" is an anagram for "out faro," "restores teeth" is an anagram for "three rosettes," and "brusque intoning" is an anagram for "burning question."</span></div></div></div></div>Mathematical Association of Americahttp://www.blogger.com/profile/10559021045290192742noreply@blogger.com1