Transcription
Mathematics MagazineA Single Diagram That Generalizes the Gergonne 27-Card Trick--Manuscript Draft-Manuscript Number:MATHMAG-D-20-00137Full Title:A Single Diagram That Generalizes the Gergonne 27-Card TrickArticle Type:ArticleKeywords:card trick; base b arithmetic; recreational mathematicsManuscript Classifications:00: General; 11: Number theory; 97: Mathematics educationAbstract:We present a generalization of Gergonne's 200-year old 27-card trickin a single, two-step diagram (2.4). The original trick, using a 9 x 3 or(3 2 x 3 1) array of cards, is generalized to any card array withdimension (b r \times\ b c) where b, r, and c are any positive integers.Repeated creation (passes) of the array forces a pre-chosen card, [X], to finallyoccupy any desired positions in the array. Each pass relies on the placement of arraycolumns into specific Designated Columns. In our graphic generalization, theseDesignated Columns are easily determined. Moreover, the number of passes (hence,the number of Designated Columns) does not necessarily increase even as thenumber of cards becomes arbitrarily large.Powered by Editorial Manager and ProduXion Manager from Aries Systems Corporation
July 2020A Single Diagram That Generalizes the Gergonne 27-Card TrickAbstract:We present a generalization of Gergonne’s 200-year old 27-card trick in a single, two-step diagram(2.4). The original trick, using a (9 3) or (32 31 ) array of cards, is generalized to any cardarray with dimension (br bc ) where b, r, and c are any positive integers. Repeated creation(passes) of the array forces a pre-chosen card [X] to finally occupy any desired positions in thearray. Each pass relies on the placement of array columns into specific Designated Columns. Inour generalization, these Designated Columns are easily determined. Moreover, the number ofpasses (hence, the number of Designated Columns) does not necessarily increase even as thenumber of cards becomes arbitrarily large.1 THE GERGONNE 27-CARD TRICKPrevious papers on the 27-card Gergonne trick can be found in the works of Martin Gardner [4],chapter 3, Konstatin Tamarov [10], Rouse Ball, and Coxeter p. 328-32 [9]. In 1813-1814 J.D. Gergonne [5] proved a generalization with N N cards arranged in N columns of NN-1 cardseach. Bolker [1] develops a theory using multiple number bases and varying numbers of pilesduring the trick. Also note [7] and Kelly Chizek [3]. There is a recent survey by Chang [2] anda continuous theory developed by Hashimoto [6]. Quintero [8] provides several extensions byrelating the spectator’s chosen card to a fixed point that depends on the number of cards.Page 1 of 14
July 2020Performing the Classic Gergonne No-Setup Trick with 27 Ordinary Playing Cards:(0) A spectator secretly selects a card[X] from 27 cards and announces herchoice of integer N, where 1 N 27.(1.1) One Pass of the 27-Card Trick.(1) From the 27-card stack of (1.1)(B),create the 9 by 3 array of (1.1)(A) bydealing left to right and top to bottom.(2) Spectator indicates the column thatcontains her secret card [X]. Pile thesethree (possibly permuted) columns intothe single 27-card stack of (1.1)(B).(3) Repeat Steps (1) and (2) two moretimes.(4a) The Reveal: From the 27-cardstack (1.1)(B), count out the top cardsuntil you reach the target position N.Show that the Nth card is exactly thesecretly pre-chosen card [X].TOP col no. 0 ,MIDDLE col no. 1 ,BOTTOM col no. 2(4b) Alternate Reveal: Instead of Spectator choosing random number N as the target positionin Step (0), integer N may be chosen by the Performer to be number of letters in the Spectator’sname. At the end of the performance, Performer counts out cards corresponding to each letter inSpectator’s name. For example, if Spectator’s name is “RoseMary,” then the N 8 cards, R-OS-E-M-A-R-Y, are counted out and the last (8th) card counted out will, indeed, be the pre-chosencard [X].(1.2) HOW the TRICK WORKS. For br c cards forming (b r b c ) arrays, we provide(1.3) DEFINITION: The Target Position for card [X] is its final position number N, where 1 N br cin the pile shown in (1.1). (The top card is in position 1.) A Designated Columns is the number of the column in which the pre-chosen card[X] must be found. The b c columns are numbered {0, 1, 2, . . . , (b c 1)}. Each passof the Gergonne trick determines a well-defined Designated Column (number).With Definition (1.3) in hand, we use Target Position N 8 to illustrate how the Gergonne27-card trick works.Step I: Establish the Target Position N {1, 2, 3, . . . , 26, 27}, then write (N-1) in base-3notationPage 2 of 14
July 2020(N-1) a 32 b 31 c a b c 3 , Target Numberminus 1(1.4) which, for integer N 8, becomes(8-1) 7 0 32 2 3 1 0 2 13 Designated ColumnNumbers(in reverse order)The “Target Number minus 1” above refers to the single integer a b c 3, while theno no“Designated Column Numbers” refers to three individual integers, a , b , c 0 , 2 , 1 .Note:Step II: Find the ordered Designated Column number sequence. The three digits of (1.4)nomust be reversed to establish the ordered sequence 1 , 2 , 0 of Designated Columns.This reverse sequence will now be used, in three consecutive passes, to replace the DesignatedColumns with whichever column contains the secret card [X].Pass 1, Column with [X] becomes Designated Column 1 : From the 3-column array of(1.1)(A), stack the three columns on top of each other, with the Spectator’s column in De Column1 (middle) position. Deal this stack in horizontal rows, creating a 3-column array.Pass 2, Column with [X] becomes Designated Column 2 : From the 3-column array of(1.1)(A), stack the three columns on top of each other, with the Spectator’s column in DesignatedColumn 2 (bottom) position. Deal this stack in horizontal rows, creating a 3-column array.Pass 3, Column with [X] becomes Designated Column 0 : From the 3-column array of(1.1)(A), stack the three columns on top of each other, with the Spectator’s column in DesignatedColumn 0 (top) position. Use this stack for the reveal. The Reveal. Starting from the top of the stack of 27 cards, count off N cards, showing theNth card to be the Spectator’s chosen card, [X].Page 3 of 14
July 20202 The GENERALIZING DIAGRAM, BASE-b NOTATION(2.1) ARRAY NOTATION: The Gergonne Trickassumes a 32 31 9 3 array of 27 cards (1.1)which we generalize to the(b r b c ) array of b(r c) of cards.To fix ideas, consider a (br bc ) array of cards wherebase-b 6. Since integers r 2 and, c 3, eacharray coordinate (i, j) is written as a pair of integersof widths 2 and 3, i.e., as a 2-digit and a 3-digitinteger, respectively. In sum,(2.2) The br 62 36 rows i are indexed by base-6 integer pairs {00, 01, 02, . . . , 54, 55}, The bc 63 216 columns j are indexed by base-6 integer triples {000, 001, 002, . . . , 554, 555}.Example (2.2) above brings us to the well-known(2.3) PROPERTY: Any integer, 0 N (bq 1), when expressed in base-b notation, canbe written as a q-digit (width q) integer — leading zeros are allowed — which we denote in thefollowing forms:N N{zq n1 n2 . . . nq b}bwhere each integer n1 , n2 , . . . , nq takes one of the b values {0, 1, 2, . . . , (b 2), (b 1)}.EXAMPLE: In base-10, any of the 103 integers, 0 N 999, can be written as a width-3(three-digit) integer abc 10 where each a,b,c, takes one of the 10 values {0, 1, 2, . . . , 9}INTERPRETING DIAGRAM (2.4)We generalize the Gergonne 32 31 card trick to (br bc ) arrays of cards, where 0 b, r, c arepositive integers. (From (2.2), in base-b notation, c is the number of digits used to label eachof the bc columns of our array of cards.) Once the Target position N is known, we have onlytoN-1b into adjacent c-length digits in order to reveal the full sequence of DesignatedColumns. Here are the details:Step I: Choose card [X] from (br bc ) cards. Then choose Target position N where card [X]will be found in the final third-pass stack (See (1.1)(B)).Step II: Partition the base-b notation,N-1b, into k adjacent, c-width sets N1 , N2 , . . . , Nkof digits, starting from the leftmost position. These k sets must cover all (r c) digits ofPage 4 of 14
July 2020N-1b. If the final c-width set, Nk , extends rightward beyondto cover the vertical middle “seam” of the adjoined pairN-1the c digits of Nk now consists of the tail end ofN-1N-1N-1b, then use set Nkb as shown inb followed by some of its first digits.Finally, here is the single diagram that generalizes the 27-card Gergonne card trick:(2.4) FIGURE:Sequence of k Designated Columns, Nk,Nk-1,.,,N3,N2,N1.(2.5) DEFINITION: For any real number x, the ceiling function dxe is equal to x if x isalready an integer. Otherwise, dxe is the next integer. More precisely, dxe is defined be thesmallest integer N greater than or equal to x. For example, d3.37e 4 and d3.0e 3. With thisterminology, we have(2.6) The PASS-COUNT THEOREM: The Gergonne trick may be performed on any (b r b c)array of cards with k passes wherek d1 (r/c)e.PROOF: Inspection of Step II of Figure (2.4) shows that the number of passes is the number kof Designated Column numbers which is also the integer number of tiles of length c that cover atile of length (c r). That is, k d(c r)/ce d1 (r/c)e.(2.7) COROLLARY: The Gergonne trick may be performed on any (b r b c) with only twopasses if c r, that is, if the number of columns is greater than or equal to the number of rows.EXAMPLES: The following new examples use only 32 cards which is a reasonable numberof cards that the reader may use to personally confirm the results of this generalized Gergonnemethod.Page 5 of 14
July 2020(2.8) FIGURE:Designated Columns for a 22 x 23 32-card Array:Target Position 20Step I: Since Target Position N 20, write192 1 0 0 1 1 2.Step II: Since column indices are 3-width digits,from left to right, mark off 3-digit integers until allof 1 0 0 1 1 is covered. This requires another copy of 1 0 0 1 1 to be appended. Accordingly, the consecutive sets of 3-digit integers extracted from 1 0 0 1 1 1 0 0 1 1are the two integers, 1 0 0 2 4 and 1 1 1 2 7. We reverse the order of thesetwo integers to obtain the Designated Column sequence { 7, 4 }.The 32-card Gergonne card trick (1.2) proceeds with two passes.(2.9) FIGURE:Designated Columns for a 23 x 22 32-card Array:Target Position 20Step I: Since Target Position N 20, write192 1 0 0 1 1 2.Page 6 of 14
July 2020Step II: Since column indices are 2-width digits,from left to right, mark off 2-digit integers untilall of 1 0 0 1 1 is covered. This requires another copy of 1 0 0 1 1 to be appended.Accordingly, the 2-digit integers extracted from 1 0 0 1 1 1 0 0 1 1 are the threeintegers, 1 0 2 2, 0 1 2 1, and 1 1 2 3. We reverse the order of these threeintegers to obtain the Designated Column sequence { 3, 1, 2 }.The 32-card Gergonne card trick (1.2) proceeds with three passes.(2.10) NOTE: The mechanism for revealing the Designated Column number sequence for the32 cards of Figures (2.8) and (2.9), using base-2 notation for row and column indices, can extend,virtually verbatim, for any base. The simplicity of the analysis and the number of passes neededfor the trick does not change.For example, instead of the 23 22 array of cards of Figure (2.9), consider the 100,000 cardsforming a 103 102 array with Target Position N 12,345 1 2 3 4 5 10. (We will henceforth suppress the subscript “10”.) Since the columns are indexed with width-2 integers, wepartition N 1 1 2 3 4 4 1 2 3 4 4 into adjacent width-2 integers to obtain the sequence,1 2 , 3 4 , 4 1 , which when reversed, gives us the 3-pass Designated Column sequence,{ 4 1 , 3 4 , 1 2 }. Yes, only three passes are necessary to perform the Gergonne trick ona 1,000 100 array of 100,000 cards. (See Theorem (2.6).)3 ORDERINGS of MATRIX ARRAYSIn (3.1) following, we define two other integers, H(i, j) and V (i, j), which are the number ofsteps necessary to travel on a matrix from the upper lefthand corner (0, 0) to entry (i, j).(3.1) DEFINITION: Horizontal and Vertical Step-Counts for Arrays. Given any m narray (m rows, n columns). For each (i, j)th entry, 0 i m, 0 j n, we define the integers(3.1)(a) H(i, j) ni j: the number of horizontal steps from upper lefthand corner(0, 0) to (i, j), See (1.1)(A).(3.1)(b) V (i, j) mj i: the number of vertical steps from upper lefthand corner(0, 0) to (i, j) See (1.1)(B).Page 7 of 14
July 2020(3.2) FIGURE: Two Passes of the Gergonne Trick: Pass p-1 and Pass p.NOTATION: We abbreviate horizontal and vertical step-counts for sub-scripted coordinates(ip , jp ) as follows:(3.3)Hp H(ip , jp )Horizontal Step-CountVp V (ip , jp )Vertical Step-CountPass p-1 of (3.2)(A) assumes card [X] is located at entry (ip 1 , jp 1 ) of the m n array. Vertical travel from(0, 0) to (ip 1 , jp 1 ) requires Vp 1 V (ip 1 , jp 1 ) steps (3.1)(b).(B) shows the single column or pile of mn cards created from the n collected columns of them n rectangular array (A). Card [X] has moved from the end of (red) vertical path of array(A) to the end of the (red) vertical path of pile (B).Pass p of (3.2)(A’) The m n array is created by dealing cards from the top of pile (B). The cards are dealtfrom left to right and from top to bottom.(B’) shows the second pile of mn cards created from the (green) columns of the m n arraysown in (A’).NOTE: The (red) vertical path of pile (B) becomes the (red) horizontal path in array (A’) wherecard [X] is now at entry (ip , jp ). Thus, their step-counts are equal, orPage 8 of 14
July 2020(3.4)Vp 1 Hp[an abbreviation for V (ip 1 , jp 1 ) H(ip , jp )]which justifies the equation in (the upper section of) Figure (3.2).Also, card [X] at entry (ip , jp )of array (A’) defines a new (red) horizontal step-count Hp and a new (green) vertical step-countVp .4 BASE-b NOTATIONAn integer N in the set of integers Z is written in base-b notation as follows:Integer(4.1)N r 1Xui bi i 0Base-b NotationAlso Denotedur 1 ur 2 . . . ui . . . u1 u0br digits ukN Zr {z } brwhere the r coefficient integers ui {0, 1, 2, . . . b 1}.Leading and Trailing Zeros. From the summation form in (4.1), we see that k leading zeros, say,may be pre-pended without changing value and to post-pend k zeros is the result of multiplicationby b k . That is,Leading and Trailing Zeros(4.2)N {z } b b k N {z } b rr0{z kN {z } rN} {z } br0{z}bkLeading zeros do not affect thenumerical valuek additional trailing zeros resultafter multiplication by b kDisplay (4.2) suggests that we should think of integer representations in terms of partitions whichwe do in the following(4.3) DEFINITION: For any integer N we define Nb with (p q) digits in its base-b notation,π p,q (N), the Partition Function that partitions any integer N into a lefthand p-lengthtile and a righthand q-length tile. τ p,q (N), the Transpose Function that transposes — or interchanges — two partitiontiles with a resulting lefthand tile of length p and a righthand tile of length q.Page 9 of 14
July 2020π p,q :N{z p qτ p,q :N2{z π}b N2{zN1{z } pN1 {z } b } q qN2{zN1{z } tions p,q and p,q of (4.3), provide an especially convenient relation (4.5) among integersi, j, and step-counts, H(i, j), V (i, j) of (3.1)(a) and (3.1)(b). Here is that relationship:THEOREM: Given base integer b and positive integers c and r. Given b r b c array with rowand column indices written in base-b notation,(4.4)i i{z, and j jb, respectively.}b {z }rcwhere 0 i (br 1), and 0 j (bc 1). Then horizontal step-count H(i, j) and verticalstep-count V (i, j) are produced by adjoining these b-base notations tiles or partitions (4.4) Also,H(i, j) and V (i, j) are related to each other by transposing these tiles. Specifically,(A)(B)(C)(4.5)τ r,c (V (i, j))V (i, j) τ c,r (H(i, j))H(i, j) PROOF:V (i, j) m ”b r j j {z } bi i{z}b0 {z } i{z}bc” j {z } 0{zc(4.6)V (i, j) }brji c}b{zc rfrom Def. (3.1)(b)rrsince m b rfrom (4.2)Addition of integers.The reasoning that produced the four equations (4.6), gives us the equality(4.7)H(i, j) i j{zr c}The fourth equation for V (i, j) in (4.6) along with the equation for H(i, j)in (4.7) provesPage 10 of 14
July 2020(4.5)(A),(B) of our hypothesis.Comparing the partitioned forms for V (i, j) (4.6) and and H(i, j) (4.7), we see that the transposeof the tiles of H(i, j) produces V (i, j) and vice versa. That is,τ r,c(V (i, j))H(i, j) andτ c,r (H(i, j))V (i, j) which validates (4.5)(C) and ends the proof.(4.8) EXAMPLE: In (4.5), consider base-b 10 and a 10 100 array with 1-digit row indexi {0, 1, 2, . . . , 9}and 2-digit column indexj {00, 01, 03, . . . , 98, 99}.If a point has coordinates (i, j) (2, 03)thenH(2, 03) 2 03 10 203 andV (2, 03) 03 2 10 032 32.Point (2, 03) is the fourth point in the thirdrow (row 2) and has two full 100-element rows above, the horizontal step count is, indeed, 203.Similarly, (2, 03), the third element in its column, has three full 10-element columns to its left,the vertical step count is V (2, 03) 03 210 32.5 VALIDATION of DIAGRAM (2.4)Our generalized Gergonne trick applies to a (br bc ) array of cards so that at the final, k-thpass, (3.2), card [X] finds itself in the pre-chosen N-th ordinal position of the column. (The N-thordinal position corresponds to the (N-1)-st cardinal position, i.e., the 1st card is cardinal number0 , the 2nd card is cardinal number 1 , etc.)At the p-th pass:First, we deal out a (br bc ) array of cards where card [X] is located at coordinates (ip , jp ) which,in turn, has vertical step-count Vp (3.3).Next, we create a single pile from the bc columns of the array maintaining the column order. Card[X] preserves its vertical step-count Vp as it passes from the array to the pile. That is, Vp is thevertical step-count of both the array (3.2)(A),(A’), and the cardinal number position of card [X]in the pile (3.2)(B),(B’), assuming column order is preserved as we scoop up the columns of thearray to form the single br c -card pile.LINKING: Figure (3.2)(B),(B’) shows that integers Vp : 1 p k, reveal the cardinal positionnumber of card [X] in the pile of each pass. The following theorem specifies the full chain ofvertical step-counts Vk , Vk 1 , Vk 2 , ., V2 , V1 .Page 11 of 14
July 2020THEOREM: Given (br bc ) array for which vertical step-counts, Vp , 1 p k (3.3), aredefined for each of the k passes (3.2). For partition function c,r and transpose function r,c(4.3). Then for {p : p k 2},πτφ(Vp ) Vp 1 which extends to the full backward chainφφφVk Vk 1 . Vp Vp 1 . V2 V1(5.1)where functionPROOF:Vp 1 Hpφ π c,r τ r,c.Upper section of (3.2) (no partitioning)π c,r (Hp) π c,r (τ r,c (Vp )) π c,r τ r,c (Vp )Gives Vp 1 a c-r partition (4.3) φ(Vp )Definition of function φ in (5.1)Vp 1 From (3.2)Definition of composition operator This completes the proof of (5.1).π τEXAMPLE: A Simplifying Visual: The composite function c,r r,c is easily visualized. Forany c-r partitioned number, the function c,r r,c simply shifts (or cycles) each individual digitc places leftward while preserving the c-r partition.π τFor example, if we give the 5-digit number, 12345 , a 2-3 partition, then2-digit leftward shift (or cycling) as follows:(5.2)π 2,3 τ 3,2 produces aπ 2,3 τ 3,2 : {z}12 345 34 512 {z } {z} {z }2323STRATEGY: Suppose card [X] has coordinates (i, j) in the br bc array which then implies [X]has vertical step-count(5.3)V (i, j) col. j {z } crow i{zr}bThe structure for vertical step-count V (i, j) in base b notation (5.3) was stated earlier in (4.5)and (4.6). which shows the first tile with c-digits always gives us the column number j (in baseb notation) in which card [X] is (or should be) located.Since we know that on our final and k-th pass, card [X] should be in the N-th cardinal place— the Vk (N-1)-st ordinal place — in the final pile (3.2), write (N-1) (N-1) b in base bnotation and partition this representation into adjacent c-digit tiles to create the (r c)-digitrepresentationPage 12 of 14
July 2020(N-1) Vk N 1 N 2 N 3 . N k-2 N k-1 n . {z } {z } {z } {z } {z } {z}(5.4)cc ccr{zc c }(5.5) The Working Diagram:Step I: Vk . Write Vk (N-1) in base bnotation as shown in (5.4) which is thefinal k-th vertical step-count of card [X]in both the array (3.2)(A’) and the pile(3.2)(B’). (The 1st (top) card is in cardinal position 0, the 2nd card is position 1, etc).Step II: Complete the full backward chain of vertical step-countsvia successive applications of function φ c,r r,c (4.3) to finallycreate the “rungs in the ladder”(N-1) Vk , Vk 1 , ., V3 , V2 , V1 (5.1).Building each “rung,”, Vp , is achievedby shifting (or cycling) each tileπ τN1 ,., N2 , Nk , n (5.4). one tile(c digits) leftward (Example (5.2)) .FINALLY, We can control the column coordinate (but not the row coordinate) of card [X] ateach pass. We do this when we scoop up the columns of the array and then place the columncontaining [X] where it “belongs” — in the column listed in the vertical list Designated ColumnIndex of the figure above.Since we use only the column labeled Designated Column Index in Figure (5.5), we ignore allother information of Step II and re-write the vertical entries, N1 , N2 , ., Nk 1 , Nk , horizontally.This re-writing, plus Step I, gives us Figure (2.4).References[1] Bolker, E. Gergonne’s Card Trick Positional Notation, and Radix Sort. Mathematics Magazine, 83:46–49, 2010.[2] Chang, Peter. Mathematical Card Tricks. http://Scholar.harvard.edu, Spring 2015.[3] Chizek, Kelly. Gergonne’s Pile Problem. Creative Components, https://lib.dr.iastate.edu/creativecomponents/151, May 2019.[4] Gardner, Martin. Relativity Simply Explained. Dover, New York, New York, 1997.Page 13 of 14
July 2020[5] Gergonnee, Joseph Diez,. Recherches Sur un Tour de Cartes. Annales de MathḿatiquesPures et Appliquées, IV:276–283, 1814.[6] Yukihiro Hashimoto. Generalized gergonne’s trick and its continuous approximation. Bulletinof Aichi University of Education Natural Sciences, 65:9–17, 03 2016.[7] J. Harrison, T. Brennan, S. Gapinski. The Gergonne p-pile Problem and the Dynamics ofthe Function x 7 b(x r)/pc. Amer. Jl. Physics, 44:1–14, March 1976.[8] Quintero, Roy. On a Mathematical Model for an Old Card Trick. Recreational MathematicsMagazine, 7:65–77, 2017.[9] W. W. Ball Rouse and H. S. M. Coxeter. Mathematical Recreations and Essays. 13th ed.,Dover, 1987.[10] Taranov, Konstatin. Understanding Gergonne’s Card Trick. https://taranovk.github.io/CardTrick/, May 2018.Page 14 of 14
Mathematics Magazine A Single Diagram That Generalizes the Gergonne 27-Card Trick--Manuscript Draft--Manuscript Number: MATHMAG-D-20-00137 . 00: General; 11: Number theory; 97: Mathematics education Abstract: We present a generalization of Gergonne's 200-year old 27-card trick in a single, two-step diagram (2.4). The original trick, using a 9 .
