Michael Kleber - The Best Card Trick.pdf

(111 KB) Pobierz
230915918 UNPDF
THEBESTCARDTRICK
MICHAELKLEBER
InMathematicalIntelligencer24#1(Winter2002)
You,myfriend,areabouttowitnessthebestcardtrickthereis.Here,take
thisordinarydeckofcards,anddrawahandoffivecardsfromit.Choosethem
deliberatelyorrandomly,whicheveryouprefer—butdonotshowthemtome!
Showtheminsteadtomylovelyassistant,whowillnowgivemefourofthem,one
atatime:the7,thentheQ~,the8|,the3}.Thereisonecardleftinyour
hand,knownonlytoyouandmyassistant.Andthehiddencard,myfriend,isthe
K.
Surelythisisimpossible.Mylovelyassistantpassedmefourcards,whichmeans
thereare48cardsleftthatcouldbethehiddenone.Ididreceivealittleinformation:
thefourcardscametomeoneatatime,andbyvaryingthatordermyassistant
couldsignaloneof4!=24messages.Itseemsthebandwidthisobyafactorof
two.Maybewearepassingoneextrabitofinformationillicitly?No,Iassureyou:
theonlyinformationIhaveisasequenceoffourofthecardsyouchose,andIcan
namethefifthone.
TheStory
Ifyouhaven’tseenthistrickbefore,theeectreallyisremarkable;readingitin
printdoesnotdoitjustice.(Iamforeverindebtedtoagraduatestudentinone
audiencewhoblurtedout“Noway!”justbeforeInamedthehiddencard.)Please
takeamomenttoponderhowthetrickcouldwork,whileIrelatesomehistoryand
delaygivingawaytheanswerforapageortwo.Fullyappreciatingthetrickwill
involvealittleinformationtheoryandapplicationsoftheBirkho–vonNeumann
theoremandHall’sMarriagetheorem.Onecaveat,though:fullyappreciatingthis
articleinvolvestakingitstitleasabitofshowmanship,perhapsapersonalopinion,
butcertainlynotapronouncementoffact!
ThetrickappearedinprintinWallaceLee’sbookMathMiracles, 1 inwhich
hecreditsitsinventiontoWilliamFitchCheney,Jr.,a.k.a.“Fitch.”Fitchwas
borninSanFranciscoin1894,sonofaprofessorofmedicineatCooperMedical
College,whichlaterbecametheStanfordMedicalSchool.AfterreceivinghisB.A.
andM.A.fromtheUniversityofCaliforniain1916and1917,Fitchspenteight
yearsworkingfortheFirstNationalBankofSanFranciscoandthenasstatistician
fortheBankofItaly.In1927heearnedthefirstmathPh.D.everawardedby
MIT;itwassupervisedbyC.L.E.Mooreandentitled“Infinitesimaldeformation
ofsurfacesinRiemannianspace.”Fitchwasaninstructorandassistantprofessor
inmathematicsatTuftsfrom1927until1930,andthereafterafullprofessorand
sometimesdepartmenthead,firstattheUniversityofConnecticutuntil1955and
1 PublishedbySeemanPrintery,Durham,N.C.,1950;WallaceLee’sMagicStudio,Durham,
N.C.,1960;MickeyHadesInternational,Calgary,1976.
1
2 MICHAELKLEBER
thenattheUniversityofHartford(HillyerCollegebefore1957)untilhisretirement
in1971;heremainedanadjunctuntilhisdeathin1974.
Foralookathisextra-mathematicalactivities,IamindebtedtohissonBill
Cheney,whowrites:
Myfather,WilliamFitchCheney,Jr.,stage-name“FitchtheMa-
gician,”firstbecameinterestedintheartofmagicwhenattending
vaudevilleshowswithhisparentsinSanFranciscointheearly
1900s.Hedevotedcountlesshourstolearningslight-of-handskills
andother“pocketmagic”eectswithwhichtoentertainfriends
andfamily.Fromthetimeofhisinitialteachingassignmentsat
TuftsCollegeinthe1920s,heenjoyedintroducingmagiceects
intotheclassroom,bothtoillustratepointsandtoassurehisstu-
dents’attentiveness.Healsotrainedhimselftobeambidextrous
(althoughnaturallyleft-handed),andamazedhisclasseswithhis
abilitytowriteequationssimultaneouslywithbothhands,meeting
inthecenteratthe“equals”sign.
EachmonththemagazineM-U-M,ocialpublicationoftheSocietyofAmerican
Magicians,includesasectionofneweectscreatedbysocietymembers,and“Fitch
Cheney”wasaregularby-line.Anumberofhiscontributionshaveamathematical
feel.Hisseriesofseven“MentalDiceEects”(beginningDec.1963)willappeal
toanyonewhothinksitimportanttorememberwhetherthenumbers1,2,3are
orientedclockwiseorcounterclockwiseabouttheircommonvertexonastandard
die.“CardScense”(Oct.1961)encodestherankofacard(possiblyajoker)using
thefourteenequivalenceclassesofpermutationsofabcdwhichremaindistinctif
youdeclareac=caandbd=dbassubstrings:thecardisplacedonapieceof
paperwhosefouredgesarefoldedover(bythemagician)tocoverit,andexamining
thecreasesgivespreciselythatmuchinformationabouttheorderinwhichthey
werefolded. 2
WhileFitchwasamathematician,thefivecardtrickwaspasseddownviaWal-
laceLee’sbookandthemagiccommunity.(Idon’tknowwhetheritappeared
earlierinM-U-Mornot.)Thetrickseemstobemakingtheroundsofthecurrent
mathcommunityandbeyondthankstomathematicianandmagicianArtBen-
jamin,whoranacrossacopyofLee’sbookatamagicshow,thentaughtthe
trickattheHampshireCollegeSummerStudiesinMathematicsprogram 3 in1986.
Sincethenithasturnedupregularlyin“brainteaser”puzzle-friendlyforums;on
therec.puzzlesnewsgroup,Ionceheardthatitwasposedtoacandidateatajob
interview.Itmadearecentappearanceinprintinthe“ProblemCorner”sectionof
theJanuary2001Emissary,thenewsletteroftheMathematicalSciencesResearch
Institute,andasaresultofwritingthiscolumnIamlearningaboutaslewofpapers
inpreparationthatdiscussitaswell.Itisacardtrickwhosetimehascome.
2 Thissortof‘PurloinedLetter’-stylehidingofinformationinplainsightisacornerstoneof
magic.Fromthatpointofview,the“real”versionofthefive-cardtricksecretlycommunicates
themissingbitofinformation;PersiDiaconistellsmetherewasadiscussionofwaystodothis
inthelate1950s.Forourpurposeswe’llignorethesecleverbutnon-mathematicalruses.
3 Unpaidadvertisement:formoreinformationonthisoutstanding,intense,andenlightening
introductiontomathematicalthinkingfortalentedhighschoolstudents,contactDavidKelly,
NaturalScienceDepartment,HampshireCollege,Amherst,MA01002,ordkelly@hampshire.edu.
THEBESTCARDTRICK 3
TheWorkings
Nowtobusiness.Our“proof”ofimpossibilityignoredtheotherchoicemylovely
assistantgetstomake:whichofthefivecardsremainshidden.Wecanputthat
choicetogooduse.Withfivecardsinyourhand,therearecertainlytwoofthe
samesuit;weadoptthestrategythatthefirstcardmyassistantshowsmeisof
thesamesuitasthecardthatstayshidden.OnceIseethefirstcard,thereare
onlytwelvechoicesforthehiddencard.Butabitmoreclevernessisrequired:by
permutingthethreeremainingcardsmyassistantcansendmeoneofonly3!=6
messages,andagainweareonebitshort.
Theremainingchoicemyassistantmakesiswhichcardfromthesame-suitpair
isdisplayedandwhichishidden.Considertheranksofthesecardstobetwoofthe
numbersfrom1to13,arrangedinacircle.Itisalwayspossibletoaddanumber
between1and6toonecard(modulo13)andobtaintheother;thisamountsto
goingaroundthecircle“theshortway.”Insummary,myassistantcanshowme
onecardandtransmitanumberfrom1to6;Iincrementtherankofthecardby
thenumber,andleavethesuitunchanged,toidentifythehiddencard.
Itremainsonlyformeandmyassistanttopickaconventionforrepresenting
thenumbersfrom1to6.Firsttotallyorderadeckofcards:sayinitiallybyrank,
A23...JQK,andbreaktiesbyorderingthesuitsinbridge(=alphabetical)order,
|}~.Thenthethreecardscanbethoughtofassmallest,middle,andlargest,
andthesixpermutationscanbeordered,e.g.,lexicographically. 4
Nowgooutandamaze(andilluminate 5 )yourfriends.Butplease:justmake
surethatyouandyourownlovelyassistantagreeonconventionsandcannamethe
hiddencardflawlessly,say20timesinarow,beforeyoutrythisinpublic.Aswe
sawabove,it’snothardtonamethehiddencardhalfthetime—andit’stoughto
winbackyouraudienceifyouhappentogetthefirstonewrong.(Ispeak,sadly,
fromexperience.)
TheBigTime
Ourschemeworksbeautifullywithastandarddeck,almostasiffoursuitsof
thirteencardseachwerechosenjustforthisreason.WhilethissatisfiedWallace
Lee,wewouldliketoknowmore.Canwedothiswithalargerdeckofcards?And
ifwereplacethehandsizeoffivewithn,whathappens?
Firstweneedabetteranalysisoftheinformationpassing.Myassistantissending
meamessageconsistingofanorderedsetoffourcards;thereare52×51×50×49
suchmessages.SinceIseefourofyourcardsandnamethefifth,theinformationI
ultimatelyextractisanunorderedsetoffivecards,ofwhichthereare 52 5
48 =2.5timesaslargeasthesetofsituations.
Indeed,wecanseesomeofthatslopspaceinouralgorithm:somehandsareencoded
4 ForsomereasonIpersonallyfinditeasiertoencodeanddecodebyscanningfortheposition
ofagivencard:placethesmallestcardintheleft/middle/rightpositiontoencode12/34/56
respectively,placingmediumbeforeorafterlargetoindicatethefirstorsecondnumberineach
pair.Theresultingordersml,slm,msl,lsm,mls,lmsisjustthelexorderontheinverseofthe
permutation.
5 Ifyourgoalistoconfoundinstead,itistootransparentalwaystoputthesuit-indicatingcard
first.Fitchrecommendedplacingit(imod4)thfortheithperformancetothesameaudience.
,which
forcomparisonweshouldwriteas52×51×50×49×48/5!.Sothereisplentyof
extraspace:thesetofmessagesis 120
 
4 MICHAELKLEBER
bymorethanonemessage(anyhandwithmoretwocardsofthesamesuit),and
somemessagesnevergetused(anymessagewhichcontainsthecarditencodes).
Generalizenowtoadeckwithdcards,fromwhichyoudrawahandofn.
Calculatingasabove,thereared(d−1)···(d−n+2)possiblemessages,and d n
possiblehands.Thetrickreallyisimpossible(withoutsubterfuge)iftherearemore
handsthanmessages,i.e.unlessdn!+n−1.
Theremarkabletheoremisthatthisupperboundondisalwaysattainable.
Whilewecalculatedthatthereareenoughmessagestoencodeallthehands,itis
farfromobviousthatwecanmatchthemupsoeachhandisencodedbyamessage
usingonlythencardsavailable!Butwecan;then=5trick,whichwecandowith
52cards,canbedonewithadeckof124.Iwillgiveanalgorithminamoment,
butfirstaninterestingnonconstructiveproof.
TheBirkho–vonNeumanntheoremstatesthattheconvexhullofthepermu-
tationmatricesispreciselythesetofdoublystochasticmatrices:matriceswith
entriesin[0,1]witheachrowandcolumnsummingto1.Wewillusetheequiva-
lentdiscretestatementthatanymatrixofnonnegativeintegerswithconstantrow
andcolumnsumscanbewrittenasasumofpermutationmatrices. 6 Toprovethis
byinduction(ontheconstantsum)oneneedonlyshowthatanysuchmatrixis
entrywisegreaterthansomepermutationmatrix.ThisisanapplicationofHall’s
Marriagetheorem,whichstatesthatitispossibletoarrangesuitablemarriages
betweennmenandnwomenaslongasanycollectionofkwomencanconcocta
listofatleastkmenthatsomeoneamongthemconsidersaneligiblebachelor.To
applythistoournonnegativeintegermatrix,saythatwecanmarryarowtoa
columnonlyiftheircommonentryisnonzero.Theconstantrowandcolumnsums
ensurethatanykrowshaveatleastkcolumnstheyconsidereligible.
Nowconsiderthe(verylarge)0–1matrixwithrowsindexedbythe d n
Perfection
Technicallytheaboveproofisconstructive,inthattheproofofHall’sMarriage
theoremisitselfaconstruction.Butwithn=5theabovematrixhas225,150,024
rowsandcolumns,sothereisroomforimprovement.Moreover,wewouldlike
aworkablestrategy,onethatwehaveachanceatperformingwithoutconsulting
acheatsheetorscribblingonscrappaper.TheperfectstrategybelowIlearned
fromElwynBerlekamp,andI’vebeentoldthatSteinKulsethandGadielSeroussi
cameupwithessentiallythesameoneindependently;likelyothershavedoneso
too.Sadly,IhavenoinformationonwhetherFitchCheneythoughtaboutthis
generalizationatall.
Supposeforsimplicityofexpositionthatn=5.Numberthecardsinthedeck0
through123.Givenahandoffivecardsc 0 <c 1 <c 2 <c 3 <c 4 ,myassistantwill
choosec i toremainhidden,wherei=c 0 +c 1 +c 2 +c 3 +c 4 mod5.
6 Exercise:dosoforyourfavoritemagicsquare.
hands,
columnsindexedbythed!/(d−n+1)!messages,andentriesequalto1indicating
thatthecardsusedinthemessageallappearinthehand.Whenwetakedtobe
ourupperboundofn!+n−1,thisisasquarematrix,andhasexactlyn!1’sineach
rowandcolumn.Weconcludethatsomesubsetofthese1’sformapermutation
matrix.Butthisispreciselyastrategyformeandmylovelyassistant—abijection
betweenhandsandmessageswhichcanbeusedtorepresentthem.Indeed,bythe
aboveparagraph,thereisnotjustonestrategy,butatleastn!.
THEBESTCARDTRICK 5
Toseehowthisworks,supposethemessageconsistsoffourcardswhichsum
tosmod5.Thenthehiddencardiscongruentto−s+imod5ifitisc i .Thisis
preciselythesameassayingthatifwerenumberthecardsfrom0to119bydeleting
thefourcardsusedinthemessage,thehiddencard’snewnumberiscongruentto
−smod5.Nowitisclearthatthereareexactly24possibilities,andthepermuta-
tionofthefourdisplayedcardscommunicatesanumberpfrom0to23,in“base
factorial:”p=d 1 1!+d 2 2!+d 3 3!,whereforlexorder,d i icountshowmany
cardstotherightofthen−itharesmallerthanit. 7 Decodingthehiddencardis
straightforward:letsbethesumofthefourvisiblecardsandcalculatepasabove
basedontheirpermutation,thentake5p+(−smod5)andcarefullyadd0,1,2,
3,or4toaccountforskippingthecardsthatappearinthemessage. 8
Havingperformedthe124-cardversion,Icanreportthatwithonlyalittleprac-
ticeitflowsquitenicely.Berlekampmentionsthathehasalsoperformedthetrick
withadeckofonly64cards,wheretheaudiencealsoflipsacoin:afterseeingfour
cardshebothnamesthefifthandstateswhetherthecoincameupheadsortails.
Encodinganddecodingworkjustasbefore,onlynowwhenwedeletethefourcards
usedtotransmitthemessage,thedeckhas60cardsleft,not120,andtheextrabit
encodestheflipofthecoin.Ifthe52-cardversionbecomestoowellknown,Imay
needtoresorttothisvarianttostayaheadofthecrowd.
AndfinallyacombinatorialquestiontowhichIhavenoanswer:howmanystrate-
giesexist?Weprobablyoughttocountequivalenceclassesmodulorenumbering
theunderlyingdeckofcards.Perhapsweshouldalsoignorecomposingastrategy
witharbitrarypermutationsofthemessage—sotwostrategiesareequivalentif,
oneveryhand,theyalwayschoosethesamecardtoremainhidden.Calculating
thepermanentoftheaforementioned225,150,024-rowmatrixseemslikeabadway
tobegin.Isthereagoodone?
Acknowledgments:MuchcreditgoestoArtBenjaminforpopularizingthe
trick;Ithankhim,PersiDiaconis,andBillCheneyforsharingwhattheyknewof
itshistory.InhelpingtrackFitchCheneyfromhisPh.D.throughhismathemati-
calcareer,IowethankstoMarleneMano,NoraMurphy,GregoryColati,Betsy
Pittman,andEthelBacon,collectionmanagersandarchivistsatMIT,MITagain,
Tufts,Connecticut,andHartford,respectively.Finally,youcan’tperformthistrick
alone.Thankstomylovelyassistants:JessicaPolito(mywife,whoworkedoutthe
solutiontotheoriginaltrickwithmeonalongwinter’swalk),BenjaminKleber,
TaraHolm,DanielBiss,andSaraBilley.
7 Or,mypreference(cf.footnote4),d i countshawmanycardslargerthantheithsmallest
appeartotheleftofit.Eitherway,theconversionfeelsnaturalafterpracticingafewtimes.
8 Exercise:verifythatifyourlovelyassistantshowsyouthesequenceofcards37,7,94,61
thenthehiddencard’snumberisarootofx 3 − 18x 2 − 748x − 456.

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin