Vores nyere puslespil indeholdt den ydmyge dobbelt-pan balance skala, historisk set et symbol på handel og regering, kunst og videnskab. Balanceskalaer er også populære i rekreativ matematik. Balancepuslespil kræver klare, logiske ræsonnementer og egner sig godt til matematisk generalisering. Lad os se hvordan Quanta læserne balancerede disse kvaliteter i gåderne nedenfor.
Puslespil 1
Du har otte identiske mønter. Den ene er falsk og lettere end de andre, som har samme vægt. Find den dårlige mønt i to vejninger. Find den generelle formel for det maksimale antal mønter, som du kan finde den falske i x vejninger.
At tackle en simpel version af et problem afslører ofte nøglen til løsningen. I dette tilfælde skal du forestille dig, at du kun har tre mønter, hvor en er lettere end de to andre. Hvis du vejer en af dem mod en af de to andre, vil de enten balancere, eller også vil de ikke. Hvis de ikke gør det, ved du, hvilken der er lettere. Hvis de balancerer, så er den tredje den lette. Du behøver kun en enkelt vejning.
Så i dette puslespil, hvis du kan isolere en gruppe på tre (eller færre), der indeholder den lette mønt i den første vejning, skal du blot bruge en vejning mere. Du kan gøre dette ved at afbalancere alle tre mod andre tre. Hvis de to grupper er ubalancerede, har du fundet gruppen, der indeholder den lette, og kan fortsætte som ovenfor for den anden vejning. Hvis de balancerer, skal du bare veje de resterende to mønter mod hinanden, og du finder den lette.
Bemærk, at dette også virker, hvis der er tre i den uvejede gruppe, så vi kunne have startet med ni mønter. Ved at følge denne logik, og begyndende med tre mønter, kan vi for hver ekstra vejning finde den lette mønt i tre gange det antal mønter, vi tidligere havde. Formlen giver os det maksimale antal mønter n in w vejninger er derfor n = 3w.
Puslespil 2
Du har 12 identiske mønter. Den ene er enten tungere eller lettere end de andre, som har samme vægt.
-
Find den dårlige mønt i tre vejninger.
-
Hvad er det maksimale antal mønter, som du kan finde den dårlige for ud af fire vejninger? Beskriv, hvordan du ville finde den falske mønt.
Løsningen på dette puslespil var godt beskrevet af Ted, som også viste, at man faktisk kan opdage den dårlige mønt blandt 13 mønter i tre vejninger. Her er Teds løsning (med fordybninger for at adskille de tre vejninger i hvert tilfælde):
Start med at veje 4 mønter vs. 4 mønter.
Tilfælde 1: Hvis ubalanceret, til den anden vejning lægges 2 hver af de tungere sider på begge sider af vægten sammen med 1 hver af den lettere side.
1a: Hvis den er ubalanceret, er den dårlige mønt enten de 2 mønter, der stadig er på den tunge side, eller den enkelte mønt, der stadig er på den lette side.
Vej de 2 mulige tunge mønter, den dårlige er enten den tungere af de to, eller den enkelte lette, hvis de er afbalanceret.
1b: Hvis anden vejning er afbalanceret, er den dårlige mønt en af de 2 ubrugte fra den lettere side af den første vejning.
Vej dem mod hinanden, den lettere er dårlig.
Tilfælde 2: Hvis den er balanceret, er den dårlige mønt en af de 5 tilbageværende. Vej 3 af dem mod 3 allerede vejede (som er kendt for at være gode).
Case 2a: Hvis den er ubalanceret, ved du, at den dårlige mønt er en af disse 3, og om den er let eller tung.
Den tredje vejning er en hvilken som helst 2 af dem mod hinanden - hvis ubalanceret, identificerer det den dårlige mønt, hvis den er afbalanceret er det den sidste af de tre.
Tilfælde 2b: Hvis den anden vejning er afbalanceret, er den dårlige mønt en af de resterende 2.
Vej en af dem mod en kendt god mønt. Hvis dette resultat er ubalanceret, er denne nye mønt dårlig, og du ved, om den er tung eller let. Hvis dette resultat er afbalanceret, er den 13. mønt dårlig, men det er uvist, om den er tung eller let (hvilket vi ikke behøver at vide, så vi er færdige).
Ted fortsatte også med at vise, at det maksimale antal mønter for fire vejninger er 40. Formlen for dette puslespil er: n = (3w − 1)/2.
For de resterende gåder er de generaliserede formler stadig under undersøgelse af professionelle matematikere og er genstand for publicerede artikler, hvoraf nogle er blevet citeret af Rainer fra foråret. Jeg vil begrænse mig til løsninger for det lille antal mønter, vi overvejer i gåderne, og vil kun nævne generaliseringer, der følger naturligt af de metoder, der anvendes i disse tilfælde.
Puslespil 3
Dette er en variation af puslespil 1. Du har igen otte identiske mønter, hvoraf den ene er lettere end de andre. Men nu har du tre skalaer. To af skalaerne virker, men den tredje er knækket og giver tilfældige resultater (det er nogle gange rigtigt og nogle gange forkert). Du ved ikke, hvilken skala der er brudt. Hvor mange vejninger skal der til for at finde den lette mønt?
Som vi så i opgave 1, tager dette kun to vejninger med en god balance. Vi ved også, at de to gode vægte altid vil stemme overens, så hvis vi bare gentager hver vejning på alle tre vægte, får vi svaret i seks vejninger, som en læser har foreslået. Hvis vi forsøger at gøre det i et mindre antal vejninger, bliver det lidt tricky. Vi kan ikke identificere en god vægt bare ved at veje de samme mønter på to vægte, for selvom de er enige, kan en af de to stadig være en dårlig vægt. (Dette viser også, hvor let misinformation eller tilfældig information kan tilsløre sandheden.)
Faktisk kan dette problem løses, meget smart, på kun fire vejninger! Rainer fra foråret postede løsningen ved hjælp af en nymodens notation, der ser ud til at være blevet skabt til dette puslespil. Men før du tager dertil, vil jeg have dig til at forestille dig et scenarie, som jeg håber vil gøre tingene mere intuitive.
Forestil dig, at du er en detektiv, der efterforsker en påkørsel i et lillebitte land, hvis biler har tocifrede nummerplader, der kun bruger cifrene 0, 1 og 2. Tre personer, A, B og C, har observeret hændelsen. To af dem svarer altid rigtigt på et trevalgsspørgsmål, og en giver helt tilfældige svar. Du ved ikke, hvem den tilfældige besvarer er. Du skal stille hver af dem et enkelt tre-valgs-spørgsmål og derefter vælge den, der helt sikkert taler sandt for at få mere information.
Sådan gør du det. Spørg A, om det første ciffer er 0, 1 eller 2. Lad os sige, at A siger 2. Spørg B, om det andet ciffer er 0, 1 eller 2. Lad os sige, at B siger 1. Bed derefter C om at vælge mellem disse tre udsagn:
- Kun A taler sandt.
- Kun B taler sandt.
- Begge taler sandt.
Du kan tro på den, som C fortæller dig til og udspørge den person om det andet ciffer. For at se hvorfor, overvej, at hvis A lyver, så er C pålidelig og vil sige, at B taler sandt. Det andet ciffer vil faktisk være 1, og du kan derefter spørge B om det første ciffer. På samme måde, hvis B lyver, så er C igen pålidelig og vil sige, at A taler sandt. Så er det første ciffer i virkeligheden 2, og du kan spørge A om det andet ciffer. Endelig, hvis C lyver, så er både A og B pålidelige, så du kan stadig tro og vælge hvem C siger til. (Og hvis C siger, at både A og B taler sandt, så skal de begge være det.) Nøglen her er, at dit valg af spørgsmål ikke tillader C at lyve på en sådan måde, at det sår tvivl om både A og B. Da mindst én af A og B skal være pålidelig, kan du altid vælge den, som C er enig i, selvom det blot er et tilfældigt svar. Hvis alle tre er enige, så har du allerede begge cifre på nummerpladen.
Sådan oversætter du denne fortælling tilbage til vores puslespil. Skalaerne er A, B og C. Du kan oversætte de to cifre på nummerpladen til mønterne som følger: 01 er mønt 1, 02 er mønt 2, 10 er mønt 3, 11 er mønt 4, 12 er mønt 5, 20 er mønt 6, 21 er mønt 7 og 22 er mønt 8. Kloge læsere vil erkende, at dette er basis 3 (eller ternære) talsystem. Bemærk også, at der er et yderligere muligt tal 00, som du kan bruge til en niende mønt, som denne teknik også vil fungere for, som i puslespil 1.
Ved den første vejning dividerer du mønterne med deres første (grundlag 3) ciffer, så dine tre grupper bliver mønter [1, 2], [3, 4, 5] og [6, 7, 8]. Vej [3, 4, 5] mod [6, 7, 8] på skala A. Hvis A fungerer godt, vil du have den korrekte første ciffergruppe som i puslespil 1. På samme måde, for den anden vejning på skala B dine grupper vil være dem med det samme andet ciffer: [1, 4, 7], [2, 5, 8] og [3, 6]. Hvis B fungerer godt, har du det korrekte andet ciffer. Til den tredje vejning, på skala C, vejer du den gruppe, som A identificerede, mod den gruppe, som B gjorde. Efter vores eksempel, for 21, vil grupperne være [6, 7, 8] og [1, 4, 7]. Mønt 7 kan ikke lægges på begge sider på samme tid, så vi udelader den og vejer [6, 8] og [1, 4] mod hinanden. Bemærk, at hvis A og B begge er pålidelige, så er 7 i virkeligheden det rigtige svar, og det er lige meget, hvilken side der kommer lysere ud på C. Hvis vejningen på C tilfældigvis er afbalanceret, så er alle tre vægte enige, og du har dit svar (mønt 7) på kun tre vejninger. Hvis A er pålidelig og B ikke er den lettere mønt i [6, 8], hvilket skala C vil bekræfte, og hvis B er pålidelig og A ikke er det, er den lettere mønt i [1, 4], hvilken skala C vil også bekræfte.
Så i tre vejninger har vi enten identificeret den lette mønt eller indsnævret den til en gruppe på to, og vi har også identificeret en arbejdsskala. Den fjerde vejning på enten vægt A eller skala B (afhængig af hvilken en vægt C stemte med) vil klare resten.
Denne løsning synes jeg er fantastisk smuk!
Denne metode kan generaliseres til at finde den lette mønt blandt 32x mønter i 3x + 1 vejninger med det givne sæt vægte. Du skal altså bruge syv vejninger til 81 mønter. For større antal mønter (>~1,000), en endnu stærkere løsning eksisterer.
Puslespil 4
Du har 16 mønter, hvoraf otte er tunge og af samme vægt. De øvrige otte er lette og af samme vægt. Du ved ikke, hvilke mønter der er tunge eller lette. Mønterne ser identiske ud bortset fra en, der har specielle markeringer. Kan du med én god vægt finde ud af, om den særlige mønt er let eller tung i tre vejninger? Hvad er det maksimale antal mønter, du kan starte med og med succes løse dette problem i fire vejninger?
Ved første øjekast virker dette puslespil næsten umuligt at udføre i tre vejninger, som en af vores læsere konkluderede. Ikke desto mindre kan det gøres med en vis klogskab, og begge dele Ted , Rainer fra foråret leverede rigtige løsninger. Ted gav nogle uvurderlige generelle principper, som er værd at være opmærksomme på.
For det første, indtil du får et ubalanceret resultat fra en vejning, har du ikke nok information til at afgøre, om den specielle mønt er tung eller let. Så du skal prøve at fremtvinge et ubalanceret resultat.
For det andet, hvis du får et afbalanceret resultat (f.eks. den specielle mønt A balancerer mønt B), kan du kombinere de mønter, der er balancerede og veje dem mod yderligere to mønter, C og D. Hvis de er ubalancerede, har du svaret; ellers har du nu fordoblet antallet af mønter, der ligner hinanden, hvilket kan hjælpe dig med at få et ubalanceret svar ved næste vejning. Du kan også udføre denne proces omvendt med antallet af mønter, der er to potenser (4, 8, osv.), hvis du har et indledende ubalanceret resultat som ses i følgende løsning.
Nedenfor er hele proceduren, der kan identificere typen af den særlige mønt A i alle tilfælde i tre vejninger. (B, C og D er tre mønter placeret på samme side som A i vejning 1 (W1); X og Y er de to mønter, der ikke bruges i W1.)
Dette puslespil blev opfundet af den russiske matematiker Konstantin Knop, en verdensautoritet om møntvejende puslespil. Mange af hans papirer er på russisk, men du kan finde flere møntpuslespil (blandt andre interessante puslespil) på blog af hans samarbejdspartner Tanya Khovanova.
Med hensyn til generalisering, vil jeg overlade det til dig at se, om den samme metode virker til at finde typen af en speciel mønt blandt 32 mønter, hvoraf 16 er tunge og 16 er lette.
Puslespil 5
Du har n identisk udseende mønter, hvoraf nogle er falske og lettere end de andre. Alt du ved er, at der er mindst én falsk mønt, og at der er flere normale mønter end falske. Dit job er at opdage alle de falske mønter.
Det faktum, at der er mindst én let mønt, og at der er flere normale mønter end lette, gør dette puslespil mindre komplekst, end det først ser ud til, i det mindste for små tal. Lad os se på antallet af vejninger for en til otte mønter.
For en og to mønter kan der ikke være lette mønter i den anden tilstand, så der kræves ingen vejninger.
Tre mønter: Kun én let mønt. Én vejning påkrævet pr. puslespil 1.
Fire mønter: Kun én let mønt. En ekstra vejning påkrævet, så w = 2.
Fem mønter: En til to lette mønter. Dette er den første interessante sag. Spørgsmålet er: Skal vi veje én mønt mod én, eller to mønter mod to?
Hvis vi vejer én mod én, så kan vi have:
- To ubalancerede vejninger: To mønter opdaget; vi er færdige.
- En afbalanceret vejning ud af to: De afbalancerede mønter skal være normale, så den sidste mønt skal vejes igen, w = 3.
- To afbalancerede vejninger: I den tredje vejning, vej en mønt fra hver tidligere vejning mod en anden. Hvis de er afbalancerede, er alle fire normale, og mønt 5 er den lette. Vi er færdige; w = 3 igen. Hvis de er ubalancerede, har vi fundet de to lette mønter, og vi er færdige med tre vejninger.
Hvis vi i stedet vejer to mod to, kræver vi stadig tre vejninger, fordi vi skal skelne mellem mulighederne for, at mønterne kan være uens eller lignende på hver side. Vejninger med et lille antal mønter samlet synes ikke at have nogen fordel i forhold til vejninger med enkelte mønter.
Dette er bekræftet for:
Seks mønter: En til to lette mønter; w = 4.
Syv mønter: En til tre lette mønter; w = 5.
Otte mønter: En til tre lette mønter; w = 6. Denne løsning har en simpel struktur:
- Lav først fire vejninger af en mønt mod den næste. Alle mønter er brugt.
- Worst case: Alle fire vejninger er afbalancerede (der er to lette mønter, der balancerer hinanden).
- Næste to vejninger: Vej en mønt fra at veje 1 mod en mønt fra at veje 2; på samme måde vejer en mønt fra at veje 3 mod en mønt fra at veje 4.
- En af disse vejninger vil være ubalanceret, hvilket identificerer de to lette mønter. Vi er færdige i seks vejninger.
Beklager, vores sekvens af 0, 0, 1, 2, 3, 4, 5, 6 er bestemt ikke interessant nok til at underkaste sig On-Line Encyclopedia of Integer Sequences!
As Jonas Tøgersen Kjellstadli påpeget, synes løsningen at være w = n − 2 for små tal, men vi har ikke bevist, at dette ikke vil ændre sig for større tal. Hos nogle n, kan brug af flere møntvejninger begynde at klare sig bedre, eller flere vejninger end n − 2 kan være påkrævet. Vi kan simpelthen generalisere løsningen for otte mønter til alle potenser af 2, give n − 2 som den øvre grænse for antallet af vejninger for alle potenser af 2.
Mark Pearson diskuterede ligheden mellem dette problem og fejlkorrigerende koder og foreslog at bruge en informationsteoretisk tilgang baseret på antallet af mulige udfald. Ved at bruge en sådan tilgang, Mike Roberts lagde en nedre grænse for den mere generelle sag, som Rainer fra foråret udledt en tilnærmelse for. Rainer har også skrevet en øvre grænse fra et offentliggjort papir, men bemærkede, at grænserne ikke er skarpe for lav n og derfor ikke nyttigt for de små tal, vi har overvejet ovenfor. For syv mønter giver de citerede grænser således et interval på 4 til 16, som vores svar, 5, falder mellem. J. Payette giver yderligere matematiske referencer og grænser for alle gåderne.
Tak til alle der deltog. Insights-prisen for denne måned går i fællesskab til Ted og Rainer aus dem Spring. Tillykke!
Vi ses næste gang for nyt Insights.
