Vår siste pakke med gåter inneholdt den ydmyke doble balanseskalaen, historisk sett et symbol på handel og myndigheter, kunst og vitenskap. Balanseskalaer er også populære innen rekreasjonsmatematikk. Balanseoppgaver krever klare, logiske resonnementer og egner seg godt til matematisk generalisering. La oss se hvordan Quanta leserne balanserte disse egenskapene i gåtene nedenfor.
Puslespill 1
Du har åtte identiske mynter. Den ene er falsk og lettere enn de andre, som har identiske vekter. Finn den dårlige mynten i to veiinger. Finn den generelle formelen for maksimalt antall mynter du kan finne den falske i x veiinger.
Å takle en enkel versjon av et problem avslører ofte nøkkelen til løsningen. I dette tilfellet, forestill deg at du bare har tre mynter, med en lettere enn de to andre. Hvis du veier en av dem mot en av de to andre, vil de enten balansere eller ikke. Hvis de ikke gjør det, vet du hvilken som er lettere. Hvis de balanserer, er den tredje den lette. Du trenger bare en enkelt veiing.
Så i dette puslespillet, hvis du kan isolere en gruppe på tre (eller færre) som inneholder den lette mynten i den første veiingen, trenger du bare en veiing til. Du kan gjøre dette ved å balansere hvilke som helst tre mot hvilke som helst andre tre. Hvis de to gruppene er ubalanserte, har du funnet gruppen som inneholder den lette og kan fortsette som ovenfor for den andre veiingen. Hvis de balanserer, veier du bare de resterende to myntene mot hverandre, så finner du den lette.
Legg merke til at dette også fungerer hvis det er tre i den uveide gruppen, så vi kunne ha startet med ni mynter. Etter denne logikken, og starter med tre mynter, for hver ekstra veiing kan vi finne lettmynten i tre ganger antall mynter vi tidligere hadde. Formelen som gir oss maksimalt antall mynter n in w veiinger er derfor n = 3w.
Puslespill 2
Du har 12 identiske mynter. Den ene er enten tyngre eller lettere enn de andre, som har identiske vekter.
-
Finn den dårlige mynten i tre veiinger.
-
Hva er det maksimale antallet mynter du kan finne den dårlige for av fire veiinger? Beskriv hvordan du finner den falske mynten.
Løsningen på dette puslespillet var godt beskrevet av Ted, som også viste at du faktisk kan oppdage den dårlige mynten blant 13 mynter i tre veiinger. Her er Teds løsning (med fordypninger for å skille de tre veiingene i hvert tilfelle):
Start med å veie 4 mynter vs 4 mynter.
Tilfelle 1: Hvis ubalansert, for den andre veiingen, legg 2 hver av de tyngre sidene på begge sider av vekten sammen med 1 hver av de lettere sidene.
1a: Hvis den er ubalansert, er den dårlige mynten enten de 2 myntene som fortsatt er på den tunge siden eller den enkle mynten som fortsatt er på den lyse siden.
Vei de 2 mulige tunge myntene, den dårlige er enten den tyngre av de to, eller den enkle lette hvis de er balansert.
1b: Hvis andre veiing er balansert, er den dårlige mynten en av de 2 ubrukte fra den lettere siden av den første veiingen.
Vei dem mot hverandre, den lettere er dårlig.
Tilfelle 2: Hvis den er balansert, er den dårlige mynten en av de 5 gjenværende. Vei 3 av de mot alle 3 som allerede er veid (som er kjent for å være gode).
Tilfelle 2a: Hvis den er ubalansert, vet du at den dårlige mynten er en av disse 3 og om den er lett eller tung.
Den tredje veiingen er to av dem mot hverandre - hvis de er ubalanserte, identifiserer det den dårlige mynten, hvis den er balansert er den den siste av de tre.
Tilfelle 2b: Hvis den andre veiingen er balansert, er den dårlige mynten en av de resterende 2.
Vei en av dem mot en kjent god mynt. Hvis dette resultatet er ubalansert, er denne nye mynten dårlig og du vet om den er tung eller lett. Hvis dette resultatet er balansert, er den 13. mynten dårlig, men det er ukjent om den er tung eller lett (som vi ikke trenger å vite, så vi er ferdige).
Ted fortsatte også med å vise at maksimalt antall mynter for fire veiinger er 40. Formelen for dette puslespillet er: n = (3w − 1)/2.
For de resterende gåtene er de generaliserte formlene fortsatt under undersøkelse av profesjonelle matematikere og er gjenstand for publiserte artikler, hvorav noen er sitert av Rainer fra våren. Jeg vil begrense meg til løsninger for det lille antallet mynter vi vurderer i gåtene og vil kun nevne generaliseringer som følger naturlig av metodene som brukes i disse tilfellene.
Puslespill 3
Dette er en variant av puslespill 1. Du har igjen åtte identiske mynter, hvorav en er lettere enn de andre. Nå har du imidlertid tre skalaer. To av skalaene fungerer, men den tredje er ødelagt og gir tilfeldige resultater (det er noen ganger riktig og noen ganger feil). Du vet ikke hvilken skala som er ødelagt. Hvor mange veiinger skal til for å finne den lette mynten?
Som vi så i oppgave 1 tar dette bare to veiinger med god balanse. Vi vet også at de to gode vektene alltid vil stemme overens, så hvis vi bare gjentar hver veiing på alle tre vektene, vil vi ha svaret i seks veiinger som en leser foreslo. Hvis vi prøver å gjøre det i et mindre antall veiinger, blir det litt vanskelig. Vi kan ikke identifisere en god vekt bare ved å veie de samme myntene på to vekter, for selv om de er enige, kan en av de to fortsatt være en dårlig vekt. (Dette viser også hvor lett feilinformasjon eller tilfeldig informasjon kan tilsløre sannheten.)
Faktisk kan dette problemet løses, veldig smart, på bare fire veiinger! Rainer fra våren la ut løsningen ved å bruke en nymotens notasjon som ser ut til å ha blitt laget for dette puslespillet. Men før du drar dit, vil jeg at du skal forestille deg et scenario som jeg håper vil gjøre ting mer intuitivt.
Se for deg at du er en etterforsker som etterforsker en påkjørsel i et lite land hvis biler har tosifrede bilskilt med kun sifrene 0, 1 og 2. Tre personer, A, B og C, har observert hendelsen. To av dem svarer alltid riktig på et trevalgsspørsmål, og en gir helt tilfeldige svar. Du vet ikke hvem den tilfeldige svareren er. Du må stille hver av dem et enkelt trevalgsspørsmål og deretter velge den som definitivt snakker sannheten for å få mer informasjon.
Slik gjør du det. Spør A om det første sifferet er 0, 1 eller 2. La oss si at A sier 2. Spør B om det andre sifferet er 0, 1 eller 2. La oss si at B sier 1. Be så C velge mellom disse tre påstandene:
- Bare A snakker sant.
- Bare B snakker sant.
- Begge snakker sannheten.
Du kan tro på den som C forteller deg til og spørre den personen om det andre sifferet. For å se hvorfor, tenk på at hvis A lyver, så er C pålitelig og vil si at B snakker sant. Det andre sifferet vil faktisk være 1 og du kan da spørre B om det første sifferet. På samme måte, hvis B lyver, er C igjen pålitelig og vil si at A snakker sant. Da er det første sifferet faktisk 2 og du kan spørre A om det andre sifferet. Til slutt, hvis C lyver, så er både A og B pålitelige, så du kan fortsatt tro og velge hvem C sier til. (Og hvis C sier at både A og B snakker sant, så må de begge være det.) Nøkkelen her er at valget ditt av spørsmål ikke lar C lyve på en slik måte at det sår tvil om både A og B. Siden minst én av A og B må være pålitelig, kan du alltid velge den som C er enig i, selv om det bare er et tilfeldig svar. Hvis alle tre er enige, har du allerede begge sifrene på bilskiltet.
Slik oversetter du denne historien tilbake til puslespillet vårt. Skalaene er A, B og C. Du kan oversette de to sifrene på bilskiltet til myntene som følger: 01 er mynt 1, 02 er mynt 2, 10 er mynt 3, 11 er mynt 4, 12 er mynt 5, 20 er mynt 6, 21 er mynt 7 og 22 er mynt 8. Glimrende lesere vil forstå at dette er base 3 (eller ternære) tallsystem. Vær også oppmerksom på at det er et ekstra mulig nummer 00, som du kan bruke for en niende mynt som denne teknikken også vil fungere for, som i puslespill 1.
For den første veiingen deler du myntene med deres første (base 3) siffer, så dine tre grupper vil være mynter [1, 2], [3, 4, 5] og [6, 7, 8]. Vei [3, 4, 5] mot [6, 7, 8] på skala A. Hvis A fungerer bra, vil du ha den riktige førstesiffergruppen som i puslespill 1. På samme måte for den andre veiingen på skala B dine grupper vil være de med samme andre siffer: [1, 4, 7], [2, 5, 8] og [3, 6]. Hvis B fungerer bra, har du riktig andre siffer. For den tredje veiingen, på skala C, veier du gruppen som A identifiserte mot gruppen som B gjorde. Etter vårt eksempel, for 21, vil gruppene være [6, 7, 8] og [1, 4, 7]. Mynt 7 kan ikke settes på begge sider samtidig, så vi utelater den og veier [6, 8] og [1, 4] mot hverandre. Legg merke til at hvis A og B begge er pålitelige, så er faktisk 7 det riktige svaret, og det spiller ingen rolle hvilken side som kommer lysere ut på C. Hvis veiingen på C tilfeldigvis er balansert, så stemmer alle tre vektene overens, og du har svaret ditt (mynt 7) på bare tre veiinger. Hvis A er pålitelig og B ikke er den lettere mynten i [6, 8], som skala C vil bekrefte, og hvis B er pålitelig og A ikke er det, er den lettere mynten i [1, 4], hvilken skala C vil også bekrefte.
Så i tre veiinger har vi enten identifisert lysmynten eller begrenset den til en gruppe på to, og vi har også identifisert en arbeidsskala. Den fjerde veiingen på enten skala A eller skala B (avhengig av hva en skala C stemte med) vil gjøre resten.
Denne løsningen synes jeg er utrolig vakker!
Denne metoden kan generaliseres for å finne den lette mynten blant 32x mynter i 3x + 1 veiinger med det gitte settet med vekter. Dermed trenger du syv veiinger for 81 mynter. For større antall mynter (>~1,000), en enda sterkere løsning finnes.
Puslespill 4
Du har 16 mynter, hvorav åtte er tunge og av samme vekt. De andre åtte er lette og av samme vekt. Du vet ikke hvilke mynter som er tunge eller lette. Myntene ser identiske ut bortsett fra en som har spesielle markeringer. Med én god vekt, kan du finne ut om spesialmynten er lett eller tung i tre veiinger? Hva er det maksimale antallet mynter du kan starte med og løse dette problemet med fire veiinger?
Ved første øyekast virker dette puslespillet nesten umulig å gjøre i tre veiinger, som en av våre lesere konkluderte. Likevel, med litt smarthet kan det gjøres, og begge deler Ted og Rainer fra våren gitt riktige løsninger. Ted ga noen uvurderlige generelle prinsipper som det er verdt å være oppmerksom på.
For det første, før du får et ubalansert resultat fra en veiing, vil du ikke ha nok informasjon til å avgjøre om den spesielle mynten er tung eller lett. Så du må prøve å tvinge frem et ubalansert resultat.
For det andre, hvis du får et balansert resultat (si den spesielle mynten A balanserer mynt B), kan du kombinere myntene som er balansert og veie dem mot ytterligere to mynter, C og D. Hvis de er ubalanserte, har du svaret; ellers har du nå doblet antall mynter som er like, noe som kan hjelpe deg å få et ubalansert svar i neste veiing. Du kan også utføre denne prosessen omvendt med antall mynter som er to potenser (4, 8, osv.) hvis du har et ubalansert innledende resultat som vist i følgende løsning.
Nedenfor er hele prosedyren som kan identifisere typen av spesialmynten A i alle tilfeller i tre veiinger. (B, C og D er tre mynter plassert på samme side som A i veiing 1 (W1); X og Y er de to myntene som ikke brukes i W1.)
Dette puslespillet ble oppfunnet av den russiske matematikeren Konstantin Knop, en verdensautoritet på myntveiende puslespill. Mange av papirene hans er på russisk, men du kan finne flere myntoppgaver (blant andre interessante oppgaver) på blog av hans samarbeidspartner Tanya Khavanova.
Når det gjelder generalisering, overlater jeg til deg å se om den samme metoden fungerer for å finne typen spesialmynt blant 32 mynter, hvorav 16 er tunge og 16 er lette.
Puslespill 5
Du har n mynter med identisk utseende, hvorav noen er falske og lettere enn de andre. Alt du vet er at det er minst én falsk mynt og at det er flere normale mynter enn falske. Din jobb er å oppdage alle de falske myntene.
Det faktum at det er minst én lett mynt og at det er flere normale mynter enn lette gjør dette puslespillet mindre komplekst enn det først ser ut til, i hvert fall for små tall. La oss se på antall veiinger for én til åtte mynter.
For én og to mynter kan det ikke være lette mynter i den andre tilstanden, så ingen veiing er nødvendig.
Tre mynter: Kun én lett mynt. En veiing kreves per puslespill 1.
Fire mynter: Kun én lett mynt. En ekstra veiing kreves, så w = 2.
Fem mynter: En til to lette mynter. Dette er den første interessante saken. Spørsmålet er: Skal vi veie én mynt mot én, eller to mynter mot to?
Hvis vi veier en mot en, kan vi ha:
- To ubalanserte veiinger: To mynter oppdaget; vi er ferdige.
- En balansert veiing av to: De balanserte myntene må være normale, så den siste mynten trenger en ny veiing, w = 3.
- To balanserte veiinger: I den tredje veiingen, vei en mynt fra hver tidligere veiing mot en annen. Hvis de er balansert, er alle fire normale, og mynt 5 er den lette. Vi er ferdige; w = 3 igjen. Hvis de er ubalanserte, har vi funnet de to lette myntene, og vi er ferdige i tre veiinger.
Hvis vi i stedet veier to mot to, krever vi fortsatt tre veiinger, fordi vi må skille mellom mulighetene for at myntene kan være forskjellige eller like på hver side. Veiing med et lite antall mynter gruppert sammen ser ikke ut til å ha noen fordel fremfor veiing med enkeltmynter.
Dette er bekreftet for:
Seks mynter: En til to lette mynter; w = 4.
Syv mynter: En til tre lette mynter; w = 5.
Åtte mynter: En til tre lette mynter; w = 6. Denne løsningen har en enkel struktur:
- Gjør først fire veiinger av en mynt mot den neste. Alle mynter er brukt.
- Worst case: Alle fire veiingene er balansert (det er to lette mynter som balanserer hverandre).
- Neste to veiinger: Vei en mynt fra veiing 1 mot en mynt fra veiing 2; vei på samme måte en mynt fra å veie 3 mot en mynt fra å veie 4.
- En av disse veiingene vil være ubalansert, og identifisere de to lette myntene. Vi er ferdige i seks veiinger.
Beklager, sekvensen vår på 0, 0, 1, 2, 3, 4, 5, 6 er absolutt ikke interessant nok til å sende inn til On-Line Encyclopedia of Integer Sequences!
As Jonas Tøgersen Kjellstadli påpekt, synes løsningen å være w = n − 2 for små tall, men vi har ikke bevist at dette ikke vil endre seg for større tall. På noen n, kan bruk av flere myntveiinger begynne å gjøre det bedre, eller flere veiinger enn n − 2 kan være nødvendig. Vi kan ganske enkelt generalisere løsningen for åtte mynter til alle potenser av 2, gi n − 2 som øvre grense for antall veiinger for alle potenser av 2.
Mark Pearson diskuterte likheten mellom dette problemet og feilkorrigerende koder og foreslo å bruke en informasjonsteoretisk tilnærming basert på antall mulige utfall. Ved å bruke en slik tilnærming, Mike Roberts la en nedre grense for den mer generelle saken, som Rainer fra våren utledet en tilnærming for. Rainer har også lagt ut en øvre grense fra en publisert artikkel, men bemerket at grensene ikke er skarpe for lav n og derfor ikke nyttig for de små tallene vi har vurdert ovenfor. For syv mynter gir de oppgitte grensene et område på 4 til 16, som vårt svar, 5, faller mellom. J. Payette gir ekstra matematiske referanser og grenser for alle gåtene.
Takk til alle som deltok. Insights-prisen for denne måneden går i fellesskap til Ted og Rainer aus dem Spring. Gratulerer!
Vi sees neste gang for nytt Insights.
