Vår senaste svit av pussel presenterade den ödmjuka balansvågen med två pansar, historiskt en symbol för handel och regering, konst och vetenskap. Balansvågar är också populära inom rekreationsmatematik. Balanspussel kräver tydliga, logiska resonemang och lämpar sig väl för matematisk generalisering. Låt oss se hur Quanta läsarna balanserade dessa egenskaper i pusslen nedan.
Pussel 1
Du har åtta likadana mynt. Den ena är förfalskad och lättare än de andra, som har samma vikt. Hitta det dåliga myntet i två vägningar. Hitta den allmänna formeln för det maximala antalet mynt som du kan hitta det förfalskade i x vägningar.
Att tackla en enkel version av ett problem avslöjar ofta nyckeln till lösningen. I det här fallet, föreställ dig att du bara har tre mynt, med ett ljusare än de andra två. Om du väger någon av dem mot någon av de andra två, kommer de att balansera eller inte. Om de inte gör det vet du vilken som är lättare. Om de balanserar, så är den tredje den lätta. Du behöver bara en enda vägning.
Så i det här pusslet, om du kan isolera en grupp på tre (eller färre) som innehåller det lätta myntet i den första vägningen, behöver du bara en vägning till. Du kan göra detta genom att balansera valfri tre mot vilka andra tre. Om de två grupperna är obalanserade har du hittat gruppen som innehåller den lätta och kan fortsätta enligt ovan för den andra vägningen. Om de balanserar, väg bara de återstående två mynten mot varandra, så hittar du det lätta.
Lägg märke till att detta också fungerar om det är tre i den ovägda gruppen, så vi kunde ha börjat med nio mynt. Efter denna logik, och börjar med tre mynt, för varje ytterligare vägning kan vi hitta det lätta myntet i tre gånger antalet mynt vi tidigare hade. Formeln som ger oss det maximala antalet mynt n in w vägningar är därför n = 3w.
Pussel 2
Du har 12 mynt som ser likadana ut. Den ena är antingen tyngre eller lättare än de andra, som har samma vikt.
-
Hitta det dåliga myntet i tre vägningar.
-
Vilket är det maximala antalet mynt som du kan hitta det dåliga för av fyra vägningar? Beskriv hur du skulle hitta det falska myntet.
Lösningen på detta pussel beskrevs väl av Ted, som också visade att man faktiskt kan upptäcka det dåliga myntet bland 13 mynt i tre vägningar. Här är Teds lösning (med fördjupningar för att separera de tre vägningarna i varje fall):
Börja med att väga 4 mynt mot 4 mynt.
Fall 1: Om den är obalanserad, för den andra vägningen lägg 2 vardera av den tyngre sidan på båda sidor av vågen tillsammans med 1 vardera av den lättare sidan.
1a: Om det är obalanserat är det dåliga myntet antingen de 2 mynten som fortfarande är på den tunga sidan eller det enda myntet som fortfarande är på den lätta sidan.
Väg de 2 möjliga tunga mynten, det dåliga är antingen det tyngre av de två, eller det enda lätta om de är balanserade.
1b: Om andra vägningen är balanserad, är det dåliga myntet ett av de 2 oanvända från den lättare sidan av den första vägningen.
Väg dem mot varandra, den lättare är dålig.
Fall 2: Om det är balanserat är det dåliga myntet ett av de 5 kvarvarande. Väg 3 av dem mot 3 redan vägda (som är kända för att vara bra).
Fall 2a: Om det är obalanserat vet du att det dåliga myntet är ett av dessa 3 och om det är lätt eller tungt.
Den tredje vägningen är två av dessa mot varandra - om de är obalanserade identifierar det det dåliga myntet, om det är balanserat är det det sista av de tre.
Fall 2b: Om den andra vägningen är balanserad är det dåliga myntet ett av de återstående 2.
Väg någon av dem mot ett känt bra mynt. Om detta resultat är obalanserat är det här nya myntet dåligt och du vet om det är tungt eller lätt. Om detta resultat är balanserat är det 13:e myntet dåligt, men det är okänt om det är tungt eller lätt (vilket vi inte behöver veta, så vi är klara).
Ted fortsatte också med att visa att det maximala antalet mynt för fyra vägningar är 40. Formeln för detta pussel är: n = (3w − 1)/2.
För de återstående pusslen är de generaliserade formlerna fortfarande under utredning av professionella matematiker och är föremål för publicerade artiklar, av vilka några har citerats av Rainer från våren. Jag kommer att begränsa mig till lösningar för det lilla antal mynt vi överväger i pusslen och kommer bara att nämna generaliseringar som följer naturligt av de metoder som används i dessa fall.
Pussel 3
Detta är en variant av pussel 1. Du har återigen åtta likadana mynt, varav ett är lättare än de andra. Men nu har du tre skalor. Två av skalorna fungerar, men den tredje är trasig och ger slumpmässiga resultat (det är ibland rätt och ibland fel). Du vet inte vilken skala som är trasig. Hur många vägningar tar det för att hitta det lätta myntet?
Som vi såg i uppgift 1 tar detta bara två vägningar med en bra balans. Vi vet också att de två bra vågorna alltid kommer att överensstämma, så om vi bara upprepar varje vägning på alla tre vågarna kommer vi att få svaret i sex vägningar som en läsare föreslog. Om vi försöker göra det i ett mindre antal vägningar blir det lite knepigt. Vi kan inte identifiera en bra våg bara genom att väga samma mynt på två vågar, för även om de överensstämmer kan någon av de två fortfarande vara en dålig våg. (Detta visar också hur lätt felaktig information eller slumpmässig information kan fördunkla sanningen.)
Faktum är att detta problem kan lösas, mycket smart, på bara fyra vägningar! Rainer från våren lade upp lösningen med en nymodig notation som verkar ha skapats för detta pussel. Men innan du går dit vill jag att du ska föreställa dig ett scenario som jag hoppas kommer att göra saker mer intuitivt.
Föreställ dig att du är en detektiv som utreder en påkörning i ett litet land vars bilar har tvåsiffriga registreringsskyltar med endast siffrorna 0, 1 och 2. Tre personer, A, B och C, har observerat händelsen. Två av dem svarar alltid rätt på en trevalsfråga, och en ger helt slumpmässiga svar. Du vet inte vem slumpsvararen är. Du måste ställa var och en av dem en enda trevalsfråga och sedan välja den som definitivt talar sanning för att få mer information.
Så här gör du. Fråga A om den första siffran är 0, 1 eller 2. Låt oss säga att A säger 2. Fråga B om den andra siffran är 0, 1 eller 2. Låt oss säga att B säger 1. Be sedan C göra ett val mellan dessa tre påståenden:
- Bara A talar sanning.
- Det är bara B som talar sanning.
- Båda talar sanning.
Du kan tro på den som C säger åt dig och fråga den personen om den andra siffran. För att se varför, tänk på att om A ljuger så är C pålitlig och kommer att säga att B talar sanning. Den andra siffran blir i själva verket 1 och du kan då fråga B om den första siffran. På samma sätt, om B ljuger, är C återigen pålitlig och kommer att säga att A talar sanning. Då är den första siffran i själva verket 2 och du kan fråga A om den andra siffran. Slutligen, om C ljuger, så är både A och B pålitliga, så du kan fortfarande tro och välja vem C säger till. (Och om C säger att både A och B talar sanning, så måste de båda vara det.) Nyckeln här är att ditt val av frågor inte tillåter C att ljuga på ett sådant sätt att det tvivlar på både A och B. Eftersom minst en av A och B måste vara tillförlitlig kan du alltid välja den som C håller med om, även om det bara är ett slumpmässigt svar. Om alla tre är överens har du redan båda siffrorna på registreringsskylten.
Så här översätter du denna berättelse tillbaka till vårt pussel. Skalorna är A, B och C. Du kan översätta de två siffrorna på registreringsskylten till mynten enligt följande: 01 är mynt 1, 02 är mynt 2, 10 är mynt 3, 11 är mynt 4, 12 är mynt 5, 20 är mynt 6, 21 är mynt 7 och 22 är mynt 8. Sköna läsare kommer att inse att detta är bas 3 (eller ternära) talsystemet. Observera också att det finns ytterligare ett möjligt nummer 00, som du kan använda för ett nionde mynt som den här tekniken också kommer att fungera för, som i pussel 1.
För den första vägningen delar du mynten med deras första (bas 3) siffra, så dina tre grupper kommer att vara mynt [1, 2], [3, 4, 5] och [6, 7, 8]. Väg [3, 4, 5] mot [6, 7, 8] på våg A. Om A fungerar bra kommer du att ha rätt förstasiffriga grupp som i pussel 1. På samma sätt, för den andra vägningen på våg B dina grupper kommer att vara de med samma andra siffra: [1, 4, 7], [2, 5, 8] och [3, 6]. Om B fungerar bra har du rätt andra siffra. För den tredje vägningen, på våg C, väger du gruppen som A identifierade mot gruppen som B gjorde. Efter vårt exempel, för 21, kommer grupperna att vara [6, 7, 8] och [1, 4, 7]. Mynt 7 kan inte läggas på båda sidor samtidigt, så vi lämnar det ute och väger [6, 8] och [1, 4] mot varandra. Observera att om A och B båda är tillförlitliga, så är 7 i själva verket det rätta svaret, och det spelar ingen roll vilken sida som blir ljusare på C. Om vägningen på C av en slump är balanserad, så är alla tre vågorna överens, och du har ditt svar (mynt 7) på bara tre vägningar. Om A är tillförlitlig och B inte är det lättare myntet i [6, 8], vilket skala C kommer att bekräfta, och om B är tillförlitligt och A inte är det ljusare myntet i [1, 4], vilken skala C kommer också att bekräfta.
Så i tre vägningar har vi antingen identifierat det lätta myntet eller minskat det till en grupp om två, och vi har också identifierat en fungerande våg. Den fjärde vägningen på antingen våg A eller våg B (beroende på vilken våg C överensstämmer med) kommer att göra resten.
Den här lösningen tycker jag är fantastiskt vacker!
Denna metod kan generaliseras för att hitta det lätta myntet bland 32x mynt i 3x + 1 vägningar med den givna uppsättningen vågar. Du behöver alltså sju vägningar för 81 mynt. För större antal mynt (>~1,000 XNUMX), en ännu starkare lösning finns.
Pussel 4
Du har 16 mynt, varav åtta är tunga och av samma vikt. De övriga åtta är lätta och har samma vikt. Du vet inte vilka mynt som är tunga eller lätta. Mynten ser identiska ut förutom ett som har speciella märkningar. Med en bra våg, kan du räkna ut om specialmyntet är lätt eller tungt i tre vägningar? Vad är det maximala antalet mynt du kan börja med och framgångsrikt lösa detta problem i fyra vägningar?
Vid första anblicken verkar detta pussel nästan omöjligt att göra i tre vägningar, som en av våra läsare drog slutsatsen. Ändå kan det göras med viss smarthet, och både och Ted och Rainer från våren tillhandahållit korrekta lösningar. Ted gav några ovärderliga allmänna principer som är värda att uppmärksamma.
För det första, tills du får ett obalanserat resultat från en vägning, har du inte tillräckligt med information för att avgöra om det speciella myntet är tungt eller lätt. Så du måste försöka tvinga fram ett obalanserat resultat.
För det andra, om du får ett balanserat resultat (säg att specialmyntet A balanserar mynt B), kan du kombinera mynten som är balanserade och väga dem mot ytterligare två mynt, C och D. Om de är obalanserade har du svaret; annars har du nu fördubblat antalet mynt som är lika, vilket kan hjälpa dig att få ett obalanserat svar vid nästa vägning. Du kan också utföra den här processen omvänt med antalet mynt som är tvåpotenser (4, 8, etc.) om du har ett initialt obalanserat resultat som visas i följande lösning.
Nedan följer hela proceduren som kan identifiera typen av specialmyntet A i samtliga fall i tre vägningar. (B, C och D är tre mynt placerade på samma sida som A i vägning 1 (W1); X och Y är de två mynten som inte används i W1.)
Detta pussel uppfanns av den ryska matematikern Konstantin Knop, en världsauktoritet på myntvägningspussel. Många av hans papper är på ryska, men du kan hitta flera myntpussel (bland andra intressanta pussel) på blogg av hans medarbetare Tanya Khovanova.
När det gäller generalisering överlåter jag till dig att se om samma metod fungerar för att hitta typen av ett specialmynt bland 32 mynt, varav 16 är tunga och 16 är lätta.
Pussel 5
Du har n identiskt utseende mynt, av vilka några är förfalskade och lättare än de andra. Allt du vet är att det finns minst ett falskt mynt och att det finns fler normala mynt än falska. Ditt jobb är att upptäcka alla förfalskade mynt.
Det faktum att det finns minst ett lätt mynt och att det finns fler normala mynt än lätta gör detta pussel mindre komplext än det först verkar, åtminstone för små nummer. Låt oss titta på antalet vägningar för ett till åtta mynt.
För ett och två mynt kan det inte finnas några lätta mynt i det andra tillståndet, så inga vägningar krävs.
Tre mynt: Endast ett lätt mynt. En vägning krävs per pussel 1.
Fyra mynt: Endast ett lätt mynt. En extra vägning krävs, alltså w = 2.
Fem mynt: Ett till två lätta mynt. Detta är det första intressanta fallet. Frågan är: Ska vi väga ett mynt mot ett, eller två mynt mot två?
Om vi väger en mot en kan vi ha:
- Två obalanserade vägningar: Två mynt upptäckta; vi är klara.
- En balanserad vägning av två: De balanserade mynten måste vara normala, så det sista myntet behöver vägas till, w = 3.
- Två balanserade vägningar: I den tredje vägningen, väg ett mynt från varje tidigare vägning mot ett annat. Om de är balanserade är alla fyra normala och mynt 5 är det lätta. Vi är klara; w = 3 igen. Om de är obalanserade har vi hittat de två lätta mynten, och vi är klara i tre vägningar.
Om vi istället väger två mot två kräver vi ändå tre vägningar, eftersom vi måste skilja på möjligheterna att mynten kan vara olika eller liknande på vardera sidan. Vägningar med ett litet antal mynt grupperade verkar inte ha någon fördel jämfört med vägningar med enstaka mynt.
Detta bekräftas för:
Sex mynt: En till två lätta mynt; w = 4.
Sju mynt: Ett till tre lätta mynt; w = 5.
Åtta mynt: Ett till tre lätta mynt; w = 6. Denna lösning har en enkel struktur:
- Gör först fyra vägningar av ett mynt mot nästa. Alla mynt används.
- Värsta fall: Alla fyra vägningarna är balanserade (det finns två lätta mynt som balanserar varandra).
- Nästa två vägningar: Väg ett mynt från att väga 1 mot ett mynt från att väga 2; väga på samma sätt ett mynt från att väga 3 mot ett mynt från att väga 4.
- En av dessa vägningar kommer att vara obalanserad, vilket identifierar de två lätta mynten. Vi är klara i sex vägningar.
Tyvärr, vår sekvens av 0, 0, 1, 2, 3, 4, 5, 6 är verkligen inte tillräckligt intressant för att On-Line Encyclopedia of Integer Sequences!
As Jonas Tøgersen Kjellstadli påpekade, verkar lösningen vara w = n − 2 för små tal, men vi har inte bevisat att detta inte kommer att förändras för större tal. Hos vissa n, att använda flera myntvägningar kan börja bli bättre, eller fler vägningar än n − 2 kan krävas. Vi kan helt enkelt generalisera lösningen för åtta mynt till alla styrkor av 2, ge n − 2 som den övre gränsen för antalet vägningar för alla potenser av 2.
Mark Pearson diskuterade likheten mellan detta problem och felkorrigerande koder och föreslog att man skulle använda ett informationsteoretiskt tillvägagångssätt baserat på antalet möjliga utfall. Att använda ett sådant tillvägagångssätt, Mike Roberts lade en nedre gräns för det mer allmänna fallet, som Rainer från våren härledde en approximation för. Rainer har också skrivit ett övre gräns från en publicerad tidning men noterade att gränserna inte är skarpa för låga n och därför inte till hjälp för de små siffrorna vi har övervägt ovan. För sju mynt ger de angivna gränserna ett intervall på 4 till 16, vilket vårt svar, 5, hamnar mellan. J. Payette ger ytterligare matematiska referenser och gränser för alla pussel.
Tack till alla som deltog. Insights-priset för denna månad går gemensamt till Ted och Rainer aus dem Spring. Grattis!
Vi ses nästa gång för nytt Insikter.
