Meie hiljutine mõistatuste komplekt sellel oli tagasihoidlik kahepanniline tasakaaluskaala, mis on ajalooliselt olnud kaubanduse ja valitsuse, kunsti ja teaduse sümbol. Tasakaalusalud on populaarsed ka meelelahutusmatemaatikas. Tasakaalumõistatused nõuavad selget, loogilist arutluskäiku ja sobivad hästi matemaatiliseks üldistamiseks. Vaatame, kuidas Quanta lugejad tasakaalustasid neid omadusi allolevates mõistatustes.
Mõistatus 1
Teil on kaheksa ühesuguse välimusega münti. Üks on võltsitud ja kergem kui teised, millel on identne kaal. Otsige kahest kaalust üles halb münt. Leidke üldine valem müntide maksimaalse arvu kohta, millest leiate võltsitud müntide x kaalumised.
Probleemi lihtsa versiooniga tegelemine paljastab sageli lahenduse võtme. Sel juhul kujutage ette, et teil on ainult kolm münti, millest üks on heledam kui ülejäänud kaks. Kui kaalute mõnda neist ühe teise kahe vastu, kas nad tasakaalustavad või mitte. Kui nad seda ei tee, teate, kumb on kergem. Kui nad tasakaalustavad, siis kolmas on kerge. Teil on vaja ainult ühte kaalumist.
Seega, kui suudate selles mõistatuses eraldada kolmeliikmelise (või vähema) rühma, mis sisaldab kerget münti esimesel kaalumisel, on teil vaja veel üks kaalumine. Seda saate teha tasakaalustades mis tahes kolme ja mis tahes ülejäänud kolm. Kui kaks rühma on tasakaalust väljas, olete leidnud heledat rühma sisaldava rühma ja võite teise kaalumise puhul jätkata ülaltoodud viisil. Kui need on tasakaalus, lihtsalt kaaluge ülejäänud kaks münti üksteise vastu ja leiate kerge.
Pange tähele, et see toimib ka siis, kui kaalumata rühmas on kolm, nii et oleksime võinud alustada üheksa mündiga. Järgides seda loogikat ja alustades kolmest mündist, leiame iga täiendava kaalumise korral heleda mündi kolmekordselt varem olnud müntide arvust. Valem, mis annab meile maksimaalse arvu münte n in w kaalumised on seega n = 3w.
Mõistatus 2
Teil on 12 ühesuguse välimusega münti. Üks on kas raskem või kergem kui teised, millel on identne kaal.
-
Otsige üles halb münt kolmest kaalust.
-
Kui suur on maksimaalne müntide arv, mille puhul leiad nelja kaalumise käigus halva? Kirjeldage, kuidas leiate võltsmündi.
Selle mõistatuse lahendust kirjeldas hästi Ted, kes näitas ka, et tegelikult saab kolme kaalumise käigus tuvastada halva mündi 13 mündi hulgast. Siin on Tedi lahendus (koos taandega, et eraldada kolm kaalumist igal juhul):
Alustuseks kaaluge 4 münti vs 4 münti.
Juhtum 1: kui see on tasakaalustamata, asetage teiseks kaalumiseks 2 kaalu mõlemale poole raskemat külge ja 1 kergemat külge.
1a: kui see on tasakaalustamata, on halb münt kas kaks münti, mis on endiselt raskel küljel, või üks münt, mis on endiselt heledal küljel.
Kaaluge 2 võimalikku rasket münti, halb on neist kahest raskem või üks kerge, kui need on tasakaalus.
1b: kui teine kaalumine on tasakaalustatud, on vigane münt üks kahest kasutamata esimese kaalumise heledamast küljest.
Kaaluge neid üksteise vastu, heledam on halb.
2. juhtum: kui see on tasakaalus, on halb münt üks viiest järelejäänud mündist. Kaaluge 5 neist juba kaalutud kolme vastu (mis on teadaolevalt head).
Juhtum 2a: kui see on tasakaalustamata, siis teate, et halb münt on üks neist kolmest ja kas see on kerge või raske.
Kolmas kaalumine on mis tahes 2 nendest üksteise vastu – kui see on tasakaalustamata, tuvastab see halva mündi, tasakaalus on see kolmest viimane.
Juhtum 2b: kui teine kaalumine on tasakaalustatud, on halb münt üks ülejäänud kahest.
Kaaluge kumbagi neist tuntud hea mündi vastu. Kui see tulemus on tasakaalust väljas, on see uus münt halb ja teate, kas see on raske või kerge. Kui see tulemus on tasakaalus, on 13. münt halb, kuid pole teada, kas see on raske või kerge (mida me ei pea teadma, nii et oleme valmis).
Ted näitas ka, et nelja kaalumise puhul on maksimaalne müntide arv 40. Selle pusle valem on järgmine: n = (3w − 1)/2.
Ülejäänud mõistatuste jaoks on üldistatud valemid endiselt professionaalsete matemaatikute uurimisel ja need on avaldatud paberite teemaks, millest mõnda on viidanud Rainer aus dem Spring. Ma piirdun lahendustega väikese arvu müntide kohta, mida mõistatustes käsitleme, ja mainin ainult üldistusi, mis tulenevad loomulikult nendel juhtudel kasutatud meetoditest.
Mõistatus 3
See on 1. pusle variatsioon. Sul on jälle kaheksa ühesuguse välimusega münti, millest üks on teistest heledam. Nüüd on teil aga kolm skaalat. Kaks skaalat töötavad, kuid kolmas on katki ja annab juhuslikke tulemusi (see on mõnikord õige ja mõnikord vale). Sa ei tea, milline kaal on katki. Mitu kaalumist tuleb valguse mündi leidmiseks?
Nagu nägime ülesandes 1, kulub selleks vaid kaks hea kaaluga kaalumist. Teame ka, et kaks head kaalu langevad alati kokku, nii et kui kordame iga kaalumist kõigil kolmel kaalul, saame vastuse kuue kaaluga, nagu lugeja soovitas. Kui proovime seda teha väiksema arvu kaalumistega, läheb see veidi keeruliseks. Me ei saa tuvastada head kaalu, kui kaalume samu münte kahel kaalul, sest isegi kui nad nõustuvad, võib kumbki neist kahest olla halb. (See näitab ka, kui kergesti võib desinformatsioon või juhuslik teave tõde hägustada.)
Tegelikult saab selle probleemi väga nutikalt lahendada vaid nelja kaalumisega! Rainer aus dem Spring postitas lahenduse, kasutades uut tähistust, mis näib olevat selle mõistatuse jaoks loodud. Kuid enne sinna minekut tahan, et kujutaksite ette stsenaariumi, mis loodetavasti muudab asjad intuitiivsemaks.
Kujutage ette, et olete detektiiv, kes uurib otsasõitu väikeses riigis, mille autodel on kahekohalised numbrimärgid, kasutades ainult numbreid 0, 1 ja 2. Juhtumit on jälginud kolm inimest, A, B ja C. Kaks neist vastavad kolme valikuga küsimusele alati õigesti ja üks annab täiesti juhuslikud vastused. Sa ei tea, kes on juhuslik vastaja. Lisateabe saamiseks peate igaühelt küsima ühe kolme valikuga küsimuse ja seejärel valima selle, kes kindlasti tõtt räägib.
Siin on, kuidas seda teha. Küsige A-lt, kas esimene number on 0, 1 või 2. Oletame, et A ütleb 2. Küsige B-lt, kas teine number on 0, 1 või 2. Oletame, et B ütleb, et 1. Seejärel paluge C-l teha valik nende kolme väite vahel:
- Ainult A räägib tõtt.
- Ainult B räägib tõtt.
- Mõlemad räägivad tõtt.
Võite uskuda seda, mida C teile ütleb, ja küsida sellelt inimeselt teise numbri kohta. Et mõista, miks, mõelge, et kui A valetab, siis C on usaldusväärne ja ütleb, et B räägib tõtt. Teine number on tegelikult 1 ja seejärel saate esimese numbri kohta B-le küsimuse esitada. Samamoodi, kui B valetab, on C jällegi usaldusväärne ja ütleb, et A räägib tõtt. Siis on esimene number tegelikult 2 ja teise numbri kohta saate küsida A-t. Lõpuks, kui C valetab, on nii A kui ka B usaldusväärsed, nii et võite ikkagi uskuda ja valida, kellele C ütleb. (Ja kui C ütleb, et nii A kui ka B räägivad tõtt, siis peavad nad nii olema.) Siin on võti selles, et teie küsimuste valik ei lase C-l valetada nii, et see seab kahtluse alla nii A kui ka B. Kuna vähemalt üks A-st ja B-st peab olema usaldusväärne, saate alati valida selle, millega C nõustub, isegi kui see on lihtsalt juhuslik vastus. Kui kõik kolm nõustuvad, on teil juba mõlemad numbrimärgi numbrid.
Siit saate teada, kuidas see lugu meie mõistatuseks tagasi tõlkida. Kaalud on A, B ja C. Numbrimärgi kaks numbrit saate müntideks tõlkida järgmiselt: 01 on münt 1, 02 on münt 2, 10 on münt 3, 11 on münt 4, 12 on münt 5, 20 on münt 6, 21 on münt 7 ja 22 on münt 8. Vilunud lugejad mõistavad, et see on 3. põhinumbrite süsteem. Samuti pange tähele, et on võimalik täiendav arv 00, mida saate kasutada üheksanda mündi jaoks, mille puhul see tehnika samuti töötab, nagu 1. mõistatuses.
Esimesel kaalumisel jagate mündid nende esimese (alus 3) numbriga, nii et teie kolm rühma on mündid [1, 2], [3, 4, 5] ja [6, 7, 8]. Kaaluge [3, 4, 5] vastu [6, 7, 8] skaalal A. Kui A töötab hästi, on teil õige esimese numbri rühm nagu mõistatuses 1. Samamoodi on teie rühmad teise kaalumise jaoks skaalal B on need, millel on sama teine number: [1, 4, 7], [2, 5, 8] ja [3, 6]. Kui B töötab hästi, on teil õige teine number. Kolmandaks kaalumiseks, skaalal C, kaalute rühma, mille A tuvastas, võrreldes rühmaga, mille B tegi. Meie eeskuju järgides on 21 jaoks rühmad [6, 7, 8] ja [1, 4, 7]. Münti 7 ei saa korraga mõlemale küljele panna, seega jätame selle välja ja kaalume [6, 8] ja [1, 4] üksteise vastu. Pange tähele, et kui A ja B on mõlemad usaldusväärsed, siis 7 on tegelikult õige vastus ja pole vahet, kumb pool C-l heledamalt välja tuleb. Kui juhuslikult on C kaalumine tasakaalus, siis kõik kolm kaalu on nõus ja teil on vastus (münt 7) vaid kolmes kaalumises. Kui A on usaldusväärne ja B mitte, on heledam münt [6, 8], mis skaalal C kinnitab, ja kui B on usaldusväärne ja A mitte, on heledam münt [1, 4], mis skaalal C kinnitab ka.
Nii oleme kolme kaalumise käigus tuvastanud heleda mündi või vähendanud selle kaheliikmeliseks rühmaks ja tuvastanud ka töökaalu. Neljas kaalumine kas kaalul A või kaalul B (olenevalt sellest, millise kaaluga C nõustus) teeb ülejäänu.
See lahendus tundub mulle hämmastavalt ilus!
Seda meetodit saab üldistada, et leida hele münt 3 hulgast2x mündid 3-sx + 1 kaalumine antud kaalude komplektiga. Seega on 81 mündi jaoks vaja seitset kaalu. Suurema hulga müntide puhul (>~1,000) veelgi tugevam lahendus olemas.
Mõistatus 4
Teil on 16 münti, millest kaheksa on rasked ja sama kaaluga. Ülejäänud kaheksa on kerged ja sama kaaluga. Te ei tea, millised mündid on rasked või kerged. Mündid näevad välja identsed, välja arvatud üks, millel on erimärgistused. Kas ühe hea kaaluga saate kolme kaaluga aru, kas erimünt on kerge või raske? Kui suur on maksimaalne müntide arv, millest saate alustada ja selle probleemi nelja kaalumisega edukalt lahendada?
Nagu üks meie lugejatest järeldas, tundub esmapilgul seda puslet kolme kaalumisega peaaegu võimatu teha. Sellegipoolest saab seda teatud nutikusega teha ja mõlemat Ted ja Rainer aus dem Spring andis õigeid lahendusi. Ted esitas mõned hindamatud üldpõhimõtted, millele tasub tähelepanu pöörata.
Esiteks, kuni te ei saa kaalumisel tasakaalustamata tulemuse, ei ole teil piisavalt teavet, et teha kindlaks, kas spetsiaalne münt on raske või kerge. Nii et sa pead proovima ja sundida tasakaalustamata tulemust.
Teiseks, kui saate tasakaalustatud tulemuse (ütleme, et spetsiaalne münt A tasakaalustab mündi B), võite kombineerida tasakaalustatud münte ja kaaluda neid veel kahe mündi C ja D vastu. Kui need on tasakaalustamata, on teil vastus olemas; muidu olete nüüd kahekordistanud sarnaste müntide arvu, mis võib aidata teil järgmisel kaalumisel saada tasakaalustamata vastuse. Saate seda protsessi läbi viia ka vastupidises järjekorras müntide arvuga, mis on kahe astmega (4, 8 jne), kui teil on esialgne tasakaalustamata tulemus, nagu on näha järgmises lahenduses.
Allpool on kogu protseduur, mille abil saab kolmel kaalumisel igal juhul tuvastada erimündi A tüübi. (B, C ja D on kolm münti, mis on paigutatud A-ga samale küljele kaaluga 1 (W1); X ja Y on kaks münti, mida W1-s ei kasutata.)
Selle mõistatuse leiutas vene matemaatik Konstantin Knop, maailma autoriteet müntide kaalumise mõistatuste alal. Paljud tema paberid on venekeelsed, kuid mitu mündimõistatust (muude huvitavate mõistatuste hulgas) leiate blogi tema kaastöötaja Tanya Khovanova.
Mis puudutab üldistust, siis jätan teie otsustada, kas see sama meetod töötab spetsiaalse mündi tüübi leidmisel 32 mündi hulgast, millest 16 on rasked ja 16 kerged.
Mõistatus 5
Sul on n identse välimusega mündid, millest mõned on võltsitud ja teistest kergemad. Teate vaid seda, et on vähemalt üks võltsmünt ja tavalisi münte on rohkem kui võltsitud. Teie ülesanne on tuvastada kõik võltsitud mündid.
Asjaolu, et on olemas vähemalt üks hele münt ja et tavalisi münte on rohkem kui heledaid, muudab selle mõistatuse vähem keeruliseks, kui esmapilgul paistab, vähemalt väikeste arvude puhul. Vaatame ühe kuni kaheksa mündi kaalumise numbreid.
Ühe ja kahe mündi puhul ei saa teises tingimuses olla heledaid münte, seega ei ole vaja kaaluda.
Kolm münti: Ainult üks kerge münt. Üks pusle kaalumine 1.
Neli münti: Ainult üks kerge münt. Vaja on veel üks kaalumine, seega w = 2.
Viis münti: üks kuni kaks kerget münti. See on esimene huvitav juhtum. Küsimus on: kas kaaluda ühte münti ühe või kahte münti kahe vastu?
Kui me kaalume ühe vastu, siis saame:
- Kaks tasakaalustamata kaalumist: Avastati kaks münti; me saime valmis.
- Üks tasakaalustatud kaalumine kahest: tasakaalustatud mündid peavad olema tavalised, nii et viimane münt vajab teist kaalumist, w = 3.
- Kaks tasakaalustatud kaalumist: kolmandal kaalumisel kaaluge igast eelnevast kaalumisest üks münt teise vastu. Kui need on tasakaalus, on kõik neli normaalsed ja münt 5 on kerge. Me saime valmis; w = jälle 3. Kui need on tasakaalust väljas, oleme leidnud kaks heledat münti ja oleme kaalunud kolm.
Kui selle asemel kaalume kaks kahe vastu, on meil siiski vaja kolme kaalumist, sest peame eristama võimalusi, et mündid võivad mõlemal küljel olla erinevad või sarnased. Väikese arvu münte rühmitatud kaalumisel ei paista olevat eeliseid üksikute müntide kaalumise ees.
See on põhjendatud:
Kuus münti: Üks kuni kaks heledat münti; w = 4.
Seitse münti: Üks kuni kolm kerget münti; w = 5.
Kaheksa münti: Üks kuni kolm kerget münti; w = 6. Sellel lahendusel on lihtne struktuur:
- Esmalt kaaluge neli münti järgmise vastu. Kõik mündid on kasutatud.
- Halvim juhtum: Kõik neli kaalumist on tasakaalus (seal on kaks heledat münti, mis tasakaalustavad üksteist).
- Järgmised kaks kaalumist: kaaluge mündi kaalust 1 ja mündi kaalust 2; samamoodi kaaluge 3 kaaluga münti 4 kaaluva mündi vastu.
- Üks nendest kaalumistest on tasakaalustamata, tuvastades kaks kerget münti. Meil on kuus kaalumist.
Vabandust, meie jada 0, 0, 1, 2, 3, 4, 5, 6 ei ole kindlasti piisavalt huvitav, et esitada On-line entsüklopeedia täisarvuliste järjestuste kohta!
As Jonas Tøgersen Kjellstadli märkis, et lahendus näib olevat w = n − 2 väikeste arvude puhul, kuid me pole tõestanud, et see ei muutu suuremate arvude puhul. Mõnel n, võib mitme mündi kaalumise kasutamine hakata paremini või rohkem kaaluma kui n − 2 võib olla vajalik. Me võime lihtsalt üldistada kaheksa mündi lahenduse 2 kõigi astmetega, andes n − 2 kui kaalumiste arvu ülemine piir 2 kõigi astmete korral.
Mark Pearson arutles selle probleemi sarnasuse üle veaparanduskoodidega ja soovitas kasutada võimalike tulemuste arvul põhinevat infoteooriat. Sellist lähenemist kasutades Mike Roberts postitas üldisema juhtumi jaoks alampiiri, mis Rainer aus dem Spring tuletanud ligikaudse väärtuse. Rainer postitas ka an ülemine piir avaldatud artiklist, kuid märkis, et madalate piiride piir ei ole terav n ja seepärast pole sellest abi ülalpool käsitletud väikeste arvude puhul. Seega annavad seitsme mündi puhul viidatud piirid vahemiku 4–16, mille vahele jääb meie vastus 5. J. Payette annab kõigi mõistatuste jaoks täiendavaid matemaatilisi viiteid ja piire.
Aitäh kõigile, kes osalesid. Selle kuu Insightsi auhinna saavad ühiselt Ted ja Rainer aus dem Spring. Palju õnne!
Kohtumiseni uuel korral Insights.
