naše nedavna zbirka ugank predstavljala skromno dvojno tehtnico, zgodovinsko simbol trgovine in vlade, umetnosti in znanosti. Ravnotežne tehtnice so priljubljene tudi v rekreativni matematiki. Uganke o ravnotežju zahtevajo jasno, logično sklepanje in so primerne za matematično posploševanje. Poglejmo, kako Quanta bralci so te lastnosti uravnotežili v spodnjih ugankah.
Uganka 1
Imate osem enakih kovancev. Ena je ponarejena in lažja od drugih, ki imajo enako težo. Poiščite slab kovanec v dveh tehtanjih. Poiščite splošno formulo za največje število kovancev, v katerih lahko najdete ponarejenega x tehtanja.
Obravnavanje preproste različice problema pogosto razkrije ključ do rešitve. V tem primeru si predstavljajte, da imate samo tri kovance, pri čemer je eden lažji od ostalih dveh. Če enega od njiju stehtate z enim od drugih dveh, se bosta uravnotežila ali pa ne. Če ne, veste, kateri je lažji. Če se uravnovesita, potem je tretja lahka. Potrebujete samo eno tehtanje.
Torej, če lahko v tej uganki pri prvem tehtanju izolirate skupino treh (ali manj), ki vsebuje lahek kovanec, boste potrebovali samo še eno tehtanje. To lahko storite tako, da uravnotežite katere koli tri s katerimi koli drugimi tremi. Če sta obe skupini neuravnoteženi, ste našli skupino, ki vsebuje lažjo, in lahko nadaljujete kot zgoraj za drugo tehtanje. Če sta v ravnovesju, samo stehtajte preostala dva kovanca enega proti drugemu in našli boste lahkega.
Upoštevajte, da to deluje tudi, če so trije v netehtani skupini, tako da bi lahko začeli z devetimi kovanci. Po tej logiki in začenši s tremi kovanci lahko za vsako dodatno tehtanje najdemo lahki kovanec v trikratnem številu kovancev, ki smo ga imeli prej. Formula, ki nam daje največje število kovancev n in w tehtanja je torej n = 3w.
Uganka 2
Imate 12 enakih kovancev. Ena je težja ali lažja od drugih, ki imajo enako težo.
-
Poiščite slab kovanec v treh tehtanjih.
-
Kakšno je največje število kovancev, za katere lahko v štirih tehtanjih najdete slabega? Opišite, kako bi našli lažni kovanec.
Rešitev te uganke je dobro opisal Ted, ki je tudi pokazal, da med 13 kovanci v treh tehtanjih dejansko odkriješ slab kovanec. Tukaj je Tedova rešitev (z vdolbinami za ločevanje treh tehtanj v vsakem primeru):
Začnite s tehtanjem 4 kovancev proti 4 kovancem.
Primer 1: Če ni uravnotežen, pri drugem tehtanju položite po 2 na težjo stran na obe strani tehtnice in po 1 na lažjo stran.
1a: Če je neuravnotežen, sta slab kovanec dva kovanca, ki sta še vedno na težki strani, ali en kovanec, ki je še vedno na lažji strani.
Stehtajte 2 možna težka kovanca, slab je težji od obeh ali pa en sam lahek, če sta uravnotežena.
1b: Če je drugo tehtanje uravnoteženo, je slab kovanec eden od 2 neuporabljenih z lažje strani prvega tehtanja.
Obtežite ju enega proti drugemu, lažji je slab.
2. primer: če je uravnotežen, je slab kovanec eden od 5 preostalih. Stehtajte 3 od teh proti katerim koli 3 že stehtanim (za katere je znano, da so dobri).
Primer 2a: če je neuravnotežen, veste, da je slab kovanec eden od teh treh in ali je lahek ali težak.
Tretje tehtanje je katera koli 2 tehtanja drug proti drugemu — če nista uravnotežena, to identificira slab kovanec, če je uravnoteženo, je zadnji od treh.
Primer 2b: Če je drugo tehtanje uravnoteženo, je slab kovanec eden od preostalih 2.
Enega od njiju stehtajte z znanim dobrim kovancem. Če je ta rezultat neuravnotežen, je ta novi kovanec slab in veste, ali je težak ali lahek. Če je ta rezultat uravnotežen, je 13. kovanec slab, ni pa znano, ali je težak ali lahek (česar nam ni treba vedeti, tako da smo končali).
Ted je tudi pokazal, da je največje število kovancev za štiri tehtanja 40. Formula za to uganko je: n = (3w − 1)/2.
Za preostale uganke posplošene formule še vedno preiskujejo profesionalni matematiki in so predmet objavljenih člankov, od katerih jih je nekaj citiral Rainer aus dem Spring. Omejil se bom na rešitve za majhno število kovancev, ki jih obravnavamo v ugankah, in omenil bom samo posplošitve, ki naravno sledijo metodam, uporabljenim v teh primerih.
Uganka 3
To je različica uganke 1. Ponovno imate osem enakih kovancev, od katerih je eden lažji od ostalih. Vendar imate zdaj tri lestvice. Dve tehtnici delujeta, tretja pa je pokvarjena in daje naključne rezultate (včasih je pravilna in včasih napačna). Ne veš, katera tehtnica je pokvarjena. Koliko tehtanj bo potrebnih, da se najde lahki kovanec?
Kot smo videli pri problemu 1, sta potrebni samo dve tehtanji z dobro tehtnico. Vemo tudi, da se bosta dve dobri tehtnici vedno ujemali, tako da če samo ponovimo vsako tehtanje na vseh treh tehtnicah, bomo dobili odgovor v šestih tehtanjih, kot je predlagal bralec. Če poskušamo to narediti v manjšem številu tehtanj, postane malo zapleteno. Ne moremo prepoznati dobre tehtnice samo s tehtanjem istih kovancev na dveh tehtnicah, kajti tudi če se ujemata, je lahko eden od obeh še vedno slaba tehtnica. (To tudi kaže, kako zlahka lahko dezinformacije ali naključne informacije zameglijo resnico.)
Pravzaprav je to težavo mogoče zelo pametno rešiti v samo štirih tehtanjih! Rainer aus dem Spring objavil rešitev z uporabo novodobnega zapisa, za katerega se zdi, da je bil ustvarjen za to uganko. Toda preden greste tja, želim, da si zamislite scenarij, za katerega upam, da bo stvari naredil bolj intuitivne.
Predstavljajte si, da ste detektiv, ki preiskuje nesrečo s pobegom v majhni državi, katere avtomobili imajo dvomestne registrske tablice, ki uporabljajo samo številke 0, 1 in 2. Trije ljudje, A, B in C, so opazovali incident. Dva izmed njih vedno pravilno odgovorita na vprašanje s tremi odgovori, eden pa daje povsem naključne odgovore. Ne veste, kdo je naključni odgovarjalec. Vsakemu od njih morate postaviti eno vprašanje s tremi možnostmi in nato izbrati tistega, ki zagotovo govori resnico, da dobite več informacij.
Evo, kako to storite. Vprašajte A, če je prva številka 0, 1 ali 2. Recimo, da A reče 2. Vprašajte B, če je druga številka 0, 1 ali 2. Recimo, da B reče 1. Nato prosite C, naj izbere med temi tremi izjavami:
- Samo A govori resnico.
- Samo B govori resnico.
- Oba govorita resnico.
Lahko verjamete tistemu, ki vam ga pove C, in to osebo vprašate o drugi števki. Če želite razumeti, zakaj, upoštevajte, da če A laže, potem je C zanesljiv in bo rekel, da B govori resnico. Druga številka bo v resnici 1 in nato lahko vprašate B o prvi števki. Podobno, če B laže, potem je C spet zanesljiv in bo rekel, da A govori resnico. Potem je prva številka v resnici 2 in A lahko vprašate o drugi števki. Nazadnje, če C laže, sta tako A kot B zanesljiva, tako da lahko še vedno verjamete in izberete kogar koli C reče. (In če C pravi, da tako A kot B govorita resnico, potem morata biti oba.) Ključno pri tem je, da vaša izbira vprašanj ne dovoli C-ju, da bi lagal tako, da bi dvomil o A-ju in B-ju. Ker mora biti vsaj eden od A in B zanesljiv, lahko vedno izberete tistega, s katerim se C strinja, tudi če je le naključen odgovor. Če se vsi trije strinjajo, potem že imate obe števki registrske tablice.
Evo, kako prevesti to zgodbo nazaj v našo uganko. Lestvice so A, B in C. Dve števki registrske tablice lahko prevedete v kovance na naslednji način: 01 je kovanec 1, 02 je kovanec 2, 10 je kovanec 3, 11 je kovanec 4, 12 je kovanec 5, 20 je kovanec 6, 21 je kovanec 7 in 22 je kovanec 8. Pronicljivi bralci bodo prepoznali, da je to osnovni 3 (ali trojni) številski sistem. Upoštevajte tudi, da obstaja dodatna možna številka 00, ki jo lahko uporabite za deveti kovanec, za katerega bo ta tehnika tudi delovala, kot v uganki 1.
Pri prvem tehtanju kovance delite z njihovo prvo števko (osnova 3), tako da bodo vaše tri skupine kovanci [1, 2], [3, 4, 5] in [6, 7, 8]. Stehtajte [3, 4, 5] proti [6, 7, 8] na lestvici A. Če A deluje dobro, boste imeli pravilno prvo skupino števk kot v uganki 1. Podobno velja za drugo tehtanje na lestvici B v vaših skupinah. bodo tisti z isto drugo števko: [1, 4, 7], [2, 5, 8] in [3, 6]. Če B deluje dobro, boste imeli pravilno drugo števko. Pri tretjem tehtanju na tehtnici C stehtate skupino, ki jo je identificiral A, proti skupini, ki jo je B. Po našem primeru bodo za 21 skupine [6, 7, 8] in [1, 4, 7]. Kovanca 7 ni mogoče dati na obe strani hkrati, zato ga izpustimo in stehtamo [6, 8] in [1, 4] drug proti drugemu. Upoštevajte, da če sta A in B zanesljiva, potem je 7 pravzaprav pravilen odgovor in ni pomembno, katera stran C je lažja. Če je po naključju tehtanje C uravnoteženo, potem se vse tri tehtnice strinjajo in svoj odgovor (kovanec 7) dobite v samo treh tehtanjih. Če je A zanesljiv in B ni, je lažji kovanec v [6, 8], kar bo potrdila lestvica C, in če je B zanesljiv in A ni, je lažji kovanec v [1, 4], kar lestvica C bo tudi potrdil.
Tako smo v treh tehtanjih bodisi identificirali lahki kovanec ali pa smo ga zožili na skupino dveh, prav tako pa smo identificirali delovno tehtnico. Četrto tehtanje na tehtnici A ali tehtnici B (katera tehtnica C se strinja) bo naredilo ostalo.
Ta rešitev se mi zdi neverjetno lepa!
To metodo je mogoče posplošiti za iskanje lahkega kovanca med 32x kovanci v 3x + 1 tehtanje z danim kompletom tehtnic. Tako potrebujete sedem tehtanj za 81 kovancev. Za večje število kovancev (>~1,000), še močnejša rešitev obstaja.
Uganka 4
Imate 16 kovancev, od katerih jih je osem težkih in enake teže. Ostalih osem je lahkih in enako težkih. Ne veste, kateri kovanci so težki ali lahki. Kovanci so videti enaki, razen enega, ki ima posebne oznake. Ali lahko z eno dobro tehtnico v treh tehtanjih ugotovite, ali je poseben kovanec lahek ali težak? Kakšno je največje število kovancev, s katerimi lahko začnete in uspešno rešite ta problem v štirih tehtanjih?
Na prvi pogled se zdi, da je to uganko skoraj nemogoče rešiti v treh tehtanjih, kot je ugotovil eden od naših bralcev. Kljub temu se z nekaj pameti da, in to oboje Ted in Rainer aus dem Spring podal pravilne rešitve. Ted je ponudil nekaj neprecenljivih splošnih načel, ki jim je vredno posvetiti pozornost.
Prvič, dokler s tehtanjem ne dobite neuravnoteženega rezultata, ne boste imeli dovolj informacij, da bi ugotovili, ali je poseben kovanec težek ali lahek. Zato morate poskusiti izsiliti neuravnotežen rezultat.
Drugič, če dobite uravnotežen rezultat (recimo, da poseben kovanec A uravnoteži kovanec B), lahko združite kovance, ki so uravnoteženi, in jih stehtate z dvema dodatnima kovancema, C in D. Če sta neuravnotežena, imate odgovor; v nasprotnem primeru ste zdaj podvojili število podobnih kovancev, kar vam lahko pomaga pri naslednjem tehtanju pri neuravnoteženem odgovoru. Ta postopek lahko izvedete tudi v obratni smeri s številom kovancev, ki so potence števila dva (4, 8 itd.), če imate začetni neuravnotežen rezultat, kot je razvidno iz naslednje rešitve.
Spodaj je celoten postopek, s katerim lahko prepoznate vrsto posebnega kovanca A v vseh primerih v treh tehtanjih. (B, C in D so trije kovanci, postavljeni na isto stran kot A pri tehtanju 1 (W1); X in Y sta kovanca, ki nista uporabljena v W1.)
To uganko je izumil ruski matematik Konstantin Knop, svetovna avtoriteta na področju ugank tehtanja kovancev. Veliko njegovih člankov je v ruščini, vendar lahko najdete več ugank s kovanci (med drugimi zanimivimi ugankami) na blog njegove sodelavke Tanje Khovanove.
Kar zadeva posploševanje, vam prepuščam, da vidite, ali ta ista metoda deluje pri iskanju vrste posebnega kovanca med 32 kovanci, od katerih je 16 težkih in 16 lahkih.
Uganka 5
Moraš n na videz enaki kovanci, od katerih so nekateri ponarejeni in lažji od drugih. Veš le, da obstaja vsaj en ponarejen kovanec in da je običajnih kovancev več kot ponarejenih. Vaša naloga je odkriti vse ponarejene kovance.
Dejstvo, da obstaja vsaj en lahki kovanec in da je običajnih kovancev več kot lahkih, naredi to uganko manj zapleteno, kot se zdi na prvi pogled, vsaj za majhna števila. Poglejmo številke tehtanja za enega do osem kovancev.
Za en in dva kovanca ne more biti lahkih kovancev po drugem pogoju, zato tehtanja niso potrebna.
Trije kovanci: samo en lahki kovanec. Za vsako uganko 1 je potrebno eno tehtanje.
Štirje kovanci: samo en lahki kovanec. Potrebno je še eno dodatno tehtanje, torej w = 2.
Pet kovancev: en do dva lahka kovanca. To je prvi zanimiv primer. Vprašanje je: Ali naj tehtamo en kovanec proti enemu ali dva kovanca proti dvema?
Če tehtamo enega proti enemu, potem lahko imamo:
- Dve neuravnoteženi tehtanji: odkrita dva kovanca; končali smo.
- Eno uravnoteženo tehtanje od dveh: uravnoteženi kovanci morajo biti normalni, zato je treba zadnji kovanec še enkrat tehtati, w = 3.
- Dve uravnoteženi tehtanji: Pri tretjem tehtanju stehtajte en kovanec iz vsakega prejšnjega tehtanja proti drugemu. Če so uravnoteženi, so vsi štirje normalni, kovanec 5 pa je lahek. Končali smo; w = spet 3. Če sta neuravnotežena, smo našli dva lahka kovanca in končali smo s tremi tehtanji.
Če namesto tega stehtamo dva proti dvema, še vedno potrebujemo tri tehtanja, ker moramo razlikovati med možnostmi, da so kovanci na obeh straneh različni ali podobni. Zdi se, da tehtanje z majhnim številom združenih kovancev nima prednosti pred tehtanjem s posameznimi kovanci.
To je potrjeno za:
Šest kovancev: en do dva lahka kovanca; w = 4.
Sedem kovancev: en do trije lahki kovanci; w = 5.
Osem kovancev: en do trije lahki kovanci; w = 6. Ta rešitev ima preprosto zgradbo:
- Najprej štirikrat stehtajte en kovanec proti drugemu. Uporabljeni so vsi kovanci.
- Najslabši primer: Vsa štiri tehtanja so uravnotežena (obstajata dva lahka kovanca, ki se uravnotežita).
- Naslednji dve tehtanji: stehtajte kovanec iz tehtanja 1 proti kovancu iz tehtanja 2; podobno stehtajte kovanec s tehtanjem 3 in kovancem s tehtanjem 4.
- Eno od teh tehtanj bo neuravnoteženo in identificira dva lahka kovanca. Končali smo v šestih tehtanjih.
Oprostite, naše zaporedje 0, 0, 1, 2, 3, 4, 5, 6 zagotovo ni dovolj zanimivo, da bi ga predložili On-line enciklopedija celih zaporedij!
As Jonas Tøgersen Kjellstadli poudaril, se zdi, da je rešitev w = n − 2 za majhna števila, vendar nismo dokazali, da se to ne bo spremenilo za večja števila. Pri nekaterih n, lahko uporaba več tehtanj kovancev deluje bolje ali pa več tehtanj kot n − Morda bosta potrebna 2. Rešitev za osem kovancev lahko preprosto posplošimo na vse potence števila 2, kar je n − 2 kot zgornja meja za število tehtanj za vse potence števila 2.
Mark Pearson je razpravljal o podobnosti tega problema s kodami za popravljanje napak in predlagal uporabo pristopa teorije informacij, ki temelji na številu možnih rezultatov. Z uporabo takega pristopa, Mike Roberts objavil spodnjo mejo za splošnejši primer, ki Rainer aus dem Spring izpeljal približek za. Rainer je objavil tudi Zgornja meja iz objavljenega članka, vendar je opazil, da meje niso ostre za nizko n in zato ni v pomoč pri majhnih številkah, ki smo jih obravnavali zgoraj. Tako za sedem kovancev navedene meje dajejo razpon od 4 do 16, med katerima se uvršča naš odgovor 5. J. Payette ponuja dodatne matematične reference in meje za vse uganke.
Hvala vsem sodelujočim. Nagrado Insights za ta mesec skupaj prejmeta Ted in Rainer aus dem Spring. čestitke!
Se vidimo naslednjič za novo Vpogled.
