Matemaattisen totuuden etsiminen väärennetyistä kolikoista

Meidän uusi pulmasarja Siinä oli vaatimaton kaksinkertainen vaaka, joka oli historiallisesti kaupan ja hallituksen, taiteen ja tieteen symboli. Tasapainovaa'at ovat suosittuja myös vapaa-ajan matematiikassa. Tasapainopalapelit vaativat selkeää, loogista päättelyä ja soveltuvat hyvin matemaattiseen yleistykseen. Katsotaanpa miten Quanta lukijat tasapainottivat näitä ominaisuuksia alla olevissa arvoituksissa.

Palapeli 1

Sinulla on kahdeksan samannäköistä kolikkoa. Yksi on väärennös ja kevyempi kuin muut, joilla on sama paino. Etsi huono kolikko kahdessa punnituksessa. Etsi yleinen kaava kolikoiden enimmäismäärälle, josta löydät väärennetyn kolikon x punnitukset.

Ongelman yksinkertaisen version käsitteleminen paljastaa usein ratkaisun avaimen. Kuvittele tässä tapauksessa, että sinulla on vain kolme kolikkoa, joista yksi on kevyempi kuin kaksi muuta. Jos punnitat yhden niistä toiseen kahdesta muusta, ne joko tasapainottavat tai eivät. Jos he eivät, tiedät kumpi on kevyempi. Jos ne tasapainottavat, niin kolmas on kevyt. Tarvitset vain yhden punnituksen.

Joten tässä pulmapelissä, jos pystyt erottamaan kolmen (tai vähemmän) ryhmän, joka sisältää kevyen kolikon ensimmäisessä punnituksessa, tarvitset vain yhden punnituksen lisää. Voit tehdä tämän tasapainottamalla mitkä tahansa kolme muiden kolmen kanssa. Jos kaksi ryhmää ovat epätasapainossa, olet löytänyt kevyen ryhmän sisältävän ryhmän ja voit jatkaa kuten edellä toisessa punnituksessa. Jos ne ovat tasapainossa, punnitse vain jäljellä olevat kaksi kolikkoa toisiaan vasten, niin löydät kevyen.

Huomaa, että tämä toimii myös, jos punnittamattomassa ryhmässä on kolme, joten olisimme voineet aloittaa yhdeksällä kolikolla. Tätä logiikkaa noudattaen ja aloittaen kolmesta kolikosta jokaista lisäpunnitusta kohden voimme löytää vaalean kolikon kolme kertaa aiemmin saamistamme kolikoista. Kaava antaa meille enimmäismäärän kolikoita n in w punnitus on siis n = 3^w.

Palapeli 2

Sinulla on 12 samannäköistä kolikkoa. Yksi on joko painavampi tai kevyempi kuin muut, joilla on sama paino.

1. Etsi huono kolikko kolmessa punnituksessa.

2. Mikä on suurin kolikoiden määrä, josta löydät huonon neljällä punnituskerralla? Kuvaile, kuinka löydät väärennetyn kolikon.

Tämän pulman ratkaisun kuvaili hyvin Ted, joka osoitti myös, että voit todella havaita huonon kolikon 13 kolikon joukosta kolmessa punnituksessa. Tässä on Tedin ratkaisu (jossa on sisennykset kolmen punnituksen erottamiseksi kussakin tapauksessa):

Aloita punnitsemalla 4 kolikkoa vs. 4 kolikkoa.

Tapaus 1: Jos se on epätasapainossa, laita toista punnitusta varten 2 painavampaa puolta vaa'an molemmille puolille ja 1 kummallekin kevyemmälle puolelle.

1a: Jos se on epätasapainossa, huono kolikko on joko 2 kolikkoa, jotka ovat edelleen raskaalla puolella, tai yksi kolikko, joka on edelleen kevyellä puolella.

Punnitse 2 mahdollista painavaa kolikkoa, huono on joko painavampi kahdesta tai yksi kevyt, jos ne ovat tasapainossa.

1b: Jos toinen punnitus on tasapainotettu, huono kolikko on yksi kahdesta käyttämättömästä ensimmäisen punnituksen kevyemmältä puolelta.

Punnitse niitä toisiaan vastaan, kevyempi on huono.

Tapaus 2: Jos se on tasapainossa, huono kolikko on yksi viidestä jäljellä olevasta. Punnitse 5 näistä kolmea jo punnittua (jotka tiedetään [oikealle]) vastaan.

Tapaus 2a: Jos se on epätasapainossa, tiedät, että huono kolikko on yksi näistä kolmesta ja onko se kevyt tai raskas.

Kolmas punnitus on mikä tahansa 2 toisiaan vastaan ​​- jos ne ovat epätasapainossa, se tunnistaa huonon kolikon, jos tasapaino on viimeinen kolmesta.

Tapaus 2b: Jos toinen punnitus on tasapainotettu, huono kolikko on yksi jäljellä olevista kahdesta.

Punnitse jompikumpi niistä tunnettua hyvää kolikkoa vastaan. Jos tämä tulos on epätasapainoinen, tämä uusi kolikko on huono ja tiedät onko se painava vai kevyt. Jos tämä tulos on tasapainoinen, 13. kolikko on huono, mutta ei tiedetä, onko se raskas vai kevyt (mitä meidän ei tarvitse tietää, joten olemme valmiita).

Ted osoitti myös, että kolikoiden enimmäismäärä neljällä punnitsemisella on 40. Tämän palapelin kaava on: n = (3^w − 1)/2.

Ammattimatemaatikot tutkivat edelleen yleistettyjä kaavoja jäljellä olevien pulmien osalta, ja niistä on julkaistu julkaisuja, joista osa on lainannut Rainer aus dem Spring. Ratkaisun rajoittuen niihin pieniin kolikkomääriin, joita arvoitteluissa tarkastelemme, ja mainitsen vain yleistykset, jotka seuraavat luonnollisesti näissä tapauksissa käytetyistä menetelmistä.

Palapeli 3

Tämä on muunnelma palapelistä 1. Sinulla on taas kahdeksan samannäköistä kolikkoa, joista yksi on vaaleampi kuin muut. Nyt sinulla on kuitenkin kolme vaakaa. Kaksi vaa'oista toimii, mutta kolmas on rikki ja antaa satunnaisia ​​tuloksia (se on joskus oikein ja joskus väärin). Et tiedä mikä vaaka on rikki. Kuinka monta punnitusta tarvitaan valokolikon löytämiseen?

Kuten näimme tehtävässä 1, tämä vaatii vain kaksi punnitusta hyvässä tasapainossa. Tiedämme myös, että kaksi hyvää vaakaa ovat aina yhtä mieltä, joten jos vain toistamme jokaisen punnituksen kaikilla kolmella vaa'alla, saamme vastauksen kuudessa punnituksessa, kuten lukija ehdotti. Jos yritämme tehdä sen pienemmällä punnitusmäärällä, siitä tulee hieman hankalaa. Emme voi tunnistaa hyvää vaakaa vain punnitsemalla samoja kolikoita kahdella vaa'alla, koska vaikka ne olisivat samaa mieltä, jompikumpi näistä kahdesta voi silti olla huono vaaka. (Tämä osoittaa myös, kuinka helposti väärä tai satunnainen tieto voi hämärtää totuuden.)

Itse asiassa tämä ongelma voidaan ratkaista, erittäin taitavasti, vain neljällä punnitsemisella! Rainer aus dem Spring julkaisi ratkaisun käyttämällä uutta merkintää, joka näyttää olevan luotu tätä pulmapeliä varten. Mutta ennen kuin menet sinne, haluan sinun kuvittelevan skenaarion, jonka toivon tekevän asioista intuitiivisempia.

Kuvittele, että olet etsivä, joka tutkii törmäystä pienessä maassa, jonka autoissa on kaksinumeroiset rekisterikilvet, joissa käytetään vain numeroita 0, 1 ja 2. Kolme henkilöä, A, B ja C, ovat havainneet tapahtuman. Kaksi heistä vastaa aina oikein kolmivalintaiseen kysymykseen ja yksi antaa täysin satunnaisia ​​vastauksia. Et tiedä, kuka satunnainen vastaaja on. Sinun täytyy kysyä jokaiselta heiltä yksi kolmivalintakysymys ja valita sitten se, joka varmasti puhuu totta saadaksesi lisätietoja.

Näin teet sen. Kysy A:lta, onko ensimmäinen numero 0, 1 vai 2. Oletetaan, että A sanoo 2. Kysy B:ltä, onko toinen numero 0, 1 vai 2. Oletetaan, että B sanoo 1. Pyydä sitten C:tä valitsemaan näiden kolmen väittämän välillä:

• Vain A puhuu totta.
• Vain B puhuu totta.
• Molemmat puhuvat totta.

Voit uskoa sitä, jolle C kertoo sinulle, ja kysyä kyseiseltä henkilöltä toista numeroa. Ymmärtääksesi miksi, harkitse, että jos A valehtelee, niin C on luotettava ja sanoo, että B puhuu totta. Toinen numero on itse asiassa 1 ja voit sitten kysyä B:tä ensimmäisestä numerosta. Vastaavasti, jos B valehtelee, C on jälleen luotettava ja sanoo, että A puhuu totta. Silloin ensimmäinen numero on itse asiassa 2 ja voit kysyä A:ta toisesta numerosta. Lopuksi, jos C valehtelee, niin A ja B ovat luotettavia, joten voit silti uskoa ja valita kenet C sanoo. (Ja jos C sanoo, että sekä A että B puhuvat totta, niin molempien täytyy olla.) Tärkeintä tässä on, että valitsemasi kysymykset eivät anna C:n valehdella tavalla, joka kyseenalaistaa sekä A:n että B:n. Koska vähintään toisen A:sta ja B:stä on oltava luotettava, voit aina valita sen, jonka kanssa C on samaa mieltä, vaikka se olisi vain satunnainen vastaus. Jos kaikki kolme ovat samaa mieltä, sinulla on jo molemmat rekisterikilven numerot.

Näin käännetään tämä tarina palapeliksi. Asteikot ovat A, B ja C. Voit kääntää rekisterikilven kaksi numeroa kolikoiksi seuraavasti: 01 on kolikko 1, 02 on kolikko 2, 10 on kolikko 3, 11 on kolikko 4, 12 on kolikko 5, 20 on kolikko 6, 21 on kolikko 7 ja 22 on kolikko 8. Tarkat lukijat ymmärtävät, että tämä on perus-3 (tai kolmiosainen) lukujärjestelmä. Huomaa myös, että on olemassa ylimääräinen mahdollinen numero 00, jota voit käyttää yhdeksänteen kolikkoon, jolle tämä tekniikka toimii myös, kuten pulmapelissä 1.

Ensimmäistä punnitusta varten jaat kolikot niiden ensimmäisellä (kanta 3) numerolla, joten kolme ryhmääsi ovat kolikot [1, 2], [3, 4, 5] ja [6, 7, 8]. Punnitse [3, 4, 5] vastaan ​​[6, 7, 8] asteikolla A. Jos A toimii hyvin, sinulla on oikea ensimmäinen numeroryhmä, kuten pulmapelissä 1. Vastaavasti toisessa punnituksessa asteikolla B ryhmäsi ovat ne, joilla on sama toinen numero: [1, 4, 7], [2, 5, 8] ja [3, 6]. Jos B toimii hyvin, sinulla on oikea toinen numero. Kolmannella punnitsemisella, asteikolla C, punnitat A:n tunnistaman ryhmän B:n punnitsemaa ryhmää vastaan. Esimerkkimme mukaisesti 21:lle ryhmät ovat [6, 7, 8] ja [1, 4, 7]. Kolikkoa 7 ei voi laittaa molemmille puolille samanaikaisesti, joten jätämme sen pois ja punnitsemme [6, 8] ja [1, 4] toisiaan vastaan. Huomaa, että jos A ja B ovat molemmat luotettavia, niin 7 on itse asiassa oikea vastaus, eikä sillä ole väliä kumpi puoli tulee kevyemmäksi C:stä. Jos sattumalta C:n punnitus on tasapainossa, niin kaikki kolme vaakaa ovat yhtä mieltä. sinulla on vastauksesi (kolikko 7) vain kolmessa punnituksessa. Jos A on luotettava ja B ei, kevyempi kolikko on [6, 8], mikä asteikko C vahvistaa, ja jos B on luotettava ja A ei ole, kevyempi kolikko on [1, 4], mikä asteikko C myös vahvistaa.

Joten kolmessa punnituksessa olemme joko tunnistaneet kevyen kolikon tai rajanneet sen kahden hengen ryhmään, ja olemme myös tunnistaneet toimivan vaa'an. Neljäs punnitus joko vaa'alla A tai vaa'alla B (kumpi tahansa vaaka C on sopinut) hoitaa loput.

Tämä ratkaisu on minusta hämmästyttävän kaunis!

Tämä menetelmä voidaan yleistää niin, että valokolikko löytyy kolmen joukosta^2x kolikot 3:ssax + 1 punnitus annetulla vaakasarjalla. Tarvitset siis seitsemän punnitusta 81 kolikkoa kohden. Suuremmille kolikkomäärille (>~1,000 XNUMX) vielä vahvempi ratkaisu olemassa.

Palapeli 4

Sinulla on 16 kolikkoa, joista kahdeksan on raskaita ja samanpainoisia. Muut kahdeksan ovat kevyitä ja saman painoisia. Et tiedä mitkä kolikot ovat raskaita tai kevyitä. Kolikot näyttävät samanlaisilta, paitsi yksi, jossa on erikoismerkinnät. Voitko yhdellä hyvällä vaa'alla selvittää, onko erikoiskolikko kevyt vai painava kolmessa punnituksessa? Kuinka monta kolikkoa voit aloittaa ja ratkaista tämän ongelman onnistuneesti neljässä punnituksessa?

Ensi silmäyksellä tämä palapeli näyttää melkein mahdottomalta tehdä kolmella punnitsemisella, kuten yksi lukijoistamme päätteli. Siitä huolimatta, tietyllä älykkyydellä se voidaan tehdä, ja molemmat Ted ja Rainer aus dem Spring tarjosi oikeita ratkaisuja. Ted esitti joitakin korvaamattomia yleisperiaatteita, joihin kannattaa kiinnittää huomiota.

Ensinnäkin, ennen kuin saat epätasapainoisen tuloksen punnitsemisesta, sinulla ei ole tarpeeksi tietoa määrittääksesi, onko erikoiskolikko painava vai kevyt. Joten sinun täytyy yrittää pakottaa epätasapainoinen tulos.

Toiseksi, jos saat tasapainoisen tuloksen (sanotaan, että erityinen kolikko A tasapainottaa kolikon B), voit yhdistää tasapainotetut kolikot ja punnita ne kahteen muuhun kolikkoon, C ja D. Jos ne ovat epätasapainossa, sinulla on vastaus. muuten olet nyt kaksinkertaistanut samankaltaisten kolikoiden määrän, mikä saattaa auttaa sinua saamaan epätasapainoisen vastauksen seuraavassa punnituksessa. Voit myös suorittaa tämän prosessin käänteisesti kolikoiden lukumäärällä, jotka ovat kahden potenssit (4, 8 jne.), jos sinulla on alkuperäinen epätasapainoinen tulos seuraavan ratkaisun mukaisesti.

Alla on koko menettely, jolla voidaan tunnistaa erikoiskolikon A tyyppi kaikissa tapauksissa kolmessa punnituksessa. (B, C ja D ovat kolme kolikkoa, jotka on asetettu samalle puolelle kuin A punnituksessa 1 (W1); X ja Y ovat kaksi kolikkoa, joita ei käytetä W1:ssä.)

Tämän palapelin keksi venäläinen matemaatikko Konstantin Knop, maailman auktoriteetti kolikoiden punnitsemisessa. Monet hänen papereistaan ​​ovat venäjäksi, mutta löydät useita kolikkopulmia (muiden mielenkiintoisten pulmien ohella) blogi hänen yhteistyökumppaninsa Tanya Khovanova.

Mitä tulee yleistykseen, jätän sinun tarkastettavaksi, toimiiko tämä sama menetelmä erikoiskolikon tyypin löytämiseen 32 kolikon joukosta, joista 16 on raskaita ja 16 kevyitä.

Palapeli 5

Sinulla on n samannäköisiä kolikoita, joista jotkut ovat väärennettyjä ja kevyempiä kuin toiset. Tiedät vain, että on olemassa ainakin yksi väärennetty kolikko ja että tavallisia kolikoita on enemmän kuin väärennettyjä. Sinun tehtäväsi on havaita kaikki väärennetyt kolikot.

Se, että on olemassa vähintään yksi kevyt kolikko ja että normaaleja kolikoita on enemmän kuin kevyitä, tekee tästä palapelistä vähemmän monimutkaisen kuin miltä se aluksi näyttää, ainakin pienten lukujen osalta. Katsotaanpa yhdestä kahdeksaan kolikon punnitusnumeroita.

Yhdelle ja kahdelle kolikolle ei voi olla kevyitä kolikoita toisessa ehdossa, joten punnituksia ei tarvita.

Kolme kolikkoa: Vain yksi kevyt kolikko. Yksi punnitus vaaditaan palapeliä kohden 1.

Neljä kolikkoa: Vain yksi kevyt kolikko. Yksi ylimääräinen punnitus vaaditaan, joten w = 2.

Viisi kolikkoa: Yksi tai kaksi kevyttä kolikkoa. Tämä on ensimmäinen mielenkiintoinen tapaus. Kysymys kuuluu: Pitäisikö meidän punnita yksi kolikko yhtä vastaan ​​vai kaksi kolikkoa kahta vastaan?

Jos punnittelemme yhtä vastaan, voimme saada:

1. Kaksi epätasapainoista punnitusta: Kaksi kolikkoa löydetty; olemme valmiita.
2. Yksi tasapainotettu punnitus kahdesta: Tasapainotettujen kolikoiden on oltava normaaleja, joten viimeinen kolikko tarvitsee toisen punnituksen, w = 3.
3. Kaksi tasapainotettua punnitusta: Punnitse kolmannessa punnituksessa yksi kolikko kustakin edellisestä punnituksesta toiseen. Jos ne ovat tasapainossa, kaikki neljä ovat normaaleja, ja kolikko 5 on kevyt. Olemme valmiita; w = 3 taas. Jos ne ovat epätasapainossa, olemme löytäneet kaksi kevyttä kolikkoa, ja olemme tehneet kolme punnitusta.

Jos sen sijaan punnitsemme kaksi kahta vastaan, tarvitsemme silti kolme punnitusta, koska meidän on erotettava mahdollisuudet, että kolikot voivat olla erilaisia ​​tai samanlaisia ​​kummallakin puolella. Punnituksella, jossa käytetään pientä määrää kolikoita ryhmiteltyinä, ei näytä olevan mitään etua yksittäisten kolikoiden punnitsemiseen.

Tämä perustuu:

Kuusi kolikkoa: XNUMX-XNUMX kevyttä kolikkoa; w = 4.

Seitsemän kolikkoa: yhdestä kolmeen kevyttä kolikkoa; w = 5.

Kahdeksan kolikkoa: yhdestä kolmeen kevyttä kolikkoa; w = 6. Tällä ratkaisulla on yksinkertainen rakenne:

• Punnitse ensin neljä kolikkoa seuraavaa vastaan. Kaikki kolikot ovat käytössä.
• Pahin tapaus: Kaikki neljä punnitusta ovat tasapainotettuja (kaksi kevyttä kolikkoa tasapainottavat toisiaan).
• Seuraavat kaksi punnitusta: Punnitse kolikko punnitsemisesta 1 ja kolikon punnitus 2; vastaavasti punnita kolikko, jonka paino on 3, vastaan ​​kolikko, jonka paino on 4.
• Toinen näistä punnituksista on epätasapainossa, mikä tunnistaa kaksi kevyttä kolikkoa. Meillä on kuusi punnitusta.

Valitettavasti sarjamme 0, 0, 1, 2, 3, 4, 5, 6 ei todellakaan ole tarpeeksi kiinnostava, jotta voisimme hyväksyä On-line Encyclopedia of Integer Sequences!

As Jonas Tøgersen Kjellstadli huomautti, että ratkaisu näyttää olevan w = n − 2 pienille luvuille, mutta emme ole osoittaneet, etteikö tämä muutu isompien lukujen kohdalla. Jossain n, useiden kolikoiden punnitseminen saattaa alkaa toimia paremmin tai punnita enemmän kuin n − 2 voidaan tarvita. Voimme yksinkertaisesti yleistää kahdeksan kolikon ratkaisun 2:n kaikkiin potenssiin, antaen n − 2 punnitusmäärän ylärajana kaikilla 2:n potenssilla.

Mark Pearson keskusteli tämän ongelman samankaltaisuudesta virheenkorjauskoodien kanssa ja ehdotti mahdollisten tulosten määrään perustuvan informaatioteorian käyttöä. Käyttämällä tällaista lähestymistapaa, Mike Roberts asetti alarajan yleisemmälle tapaukselle, mikä Rainer aus dem Spring johdettu likimääräinen arvo. Rainer lähetti myös viestin yläraja julkaistusta julkaisusta, mutta totesi, että rajat eivät ole teräviä n ja siksi se ei ole hyödyllinen edellä tarkastelemillemme pienille luvuille. Siten seitsemän kolikon kohdalla mainitut rajat antavat vaihteluvälin 4-16, jonka väliin vastauksemme 5 osuu. J. Payette antaa lisää matemaattisia viitteitä ja rajoja kaikille arvoituksille.

Kiitos kaikille osallistuneille. Tämän kuun Insights-palkinto menee yhdessä Tedille ja Rainerille aus dem Springille. Onnittelut!

Nähdään ensi kerralla uusissa Insights.