Tolv bollar och en skala

Dela upp detta i n till tre grupper om fyra, A1, A2, A3, A4; B1, B2 …; C1, C2 … Varje steg här motsvarar en vägning.

• Väg A mot B.
  • Om A> B, väg sedan A1, B1 och B2 mot B3 , B4 och C1.
    • Om vikterna är lika, är en av A2 … 4 tyngre; väger A2 och A3. Om de är lika är A4 tyngre. Om en är tyngre är den bollen tyngst.
    • Om den första gruppen är tyngre är A1 antingen tyngre eller B3-4 är lättare. Jämför B3 och B4; om de är lika är A1 tyngre; om de är olika är den lättaste den lättaste bollen.
    • Om den första gruppen är lättare är antingen B1 eller B2 ljusare. Väg dem och se.
  • Om A < B, numrerar du om alla A-bollar till B-bollar och utför ovanstående steg.
  • Om A = B, väg A1, A2, A3 mot C1, C2, C3
    • Om de är lika, väger du A1 mot C4. Om A1 är lättare är C4 den udda bollen och den är tung. Om A1 är tyngre är C4 den udda bollen och den är lätt.
    • Om A är tyngre än C, väg C1 mot C2. Om de är lika är C3 den udda bollen och den är lättare. Om de inte är lika är den lättare av de två kulorna den lättaste kulan
    • Om A är lättare än C, väg C1 mot C2. Om de är lika är C3 den udda bollen och den är tyngre. Om de inte är lika är den tyngre av de två bollarna den tyngsta bollen.

Vi kan arbeta bakåt från det tredje steget för att se ungefär varför detta fungerar. Vid den tredje vägningen måste alternativen reduceras till antingen två eller tre bollar. Det betyder att den andra vägningen måste reduceras till antingen två eller tre möjliga kulor.

Vi vet att det första steget tar bort antingen 1/3 eller 2/3 av de möjliga lösningarna, oavsett vad du gör. Detta innebär att du i 1/3 fall måste dela upp möjligheterna från 8 i en grupp på 3, en grupp på 3 och en grupp på 2. Från detta, den tredje vägningen pekar till den udda bollen ut. Eftersom det här fallet innebär att en uppsättning bollar är tyngre, på grund av att vi hittar den udda bollen, vet vi om den är tyngre eller lättare, så vi behöver inte alls oroa oss för den här informationen.

I fallet 2/3 måste du minska möjligheterna till en grupp på 3 och en grupp på 1, vilket är lätt nog att göra intuitivt. Eftersom vi faktiskt inte vet den udda kulans relativa vikt i detta fall måste informationen från den tredje vägningen användas för att avgöra om bollen är tyngre eller lättare.

Kommentarer

• Även om det här svaret stämmer, hoppades jag på ett svar som skulle förklara strategin bakom valen av artiklar att väga.
• @JoeZ. I ’ har lagt till lite om hur jag bestämde det här svaret, även om jag ’ inte är säker på att jag kan tala med en allmän lösning på detta problem. (Också, FYI, jag ’ har redigerat mitt svar på din andra fråga.)
• Vad du ’ har lagt upp är bra. Jag tänkte resonera mer än strategi, kom att tänka igen.

Där är ett annat sätt att göra detta problem, som inte inbegriper någon form av villkorlig förgrening alls. Det är faktiskt möjligt att ställa in ett fast vågschema i förväg och ändå bestämma vilken boll som är lättare eller tyngre på bara 3 vägningar. Jag kommer att förklara hur nedan.

Kärnan i problem som dessa är, hur mycket information kan du få från det förfarande du får genomföra? Vid varje vägning kan vågen antingen tippa åt vänster, tippa åt höger eller hålla sig balanserad.Detta ger dig totalt 3 ³ = 27 möjliga resultat, och i detta fall måste du urskilja 24 resultat från dem (en av 12 bollar är antingen lätt eller tung, vilket är 12 × 2 = 24 ).

Så vi måste börja den tråkiga uppgiften att kartlägga varje resultat till ett resultat.

En av de saker som vi omedelbart kan märka är att det också finns tre tillstånd varje boll kan vara i under varje vägning – på vänster sida av vågen, på höger sida av vågen eller utanför vågen. Naturligtvis kartläggs detta till skalans tillstånd på ett sätt som är intuitivt analogt:

Om den udda bollen är tyngre …

• och bollen är placeras på vänster sida, skalan kommer att tippa åt vänster.
• och bollen placeras på höger sida, skalan kommer att tippa åt höger.
• och bollen är utanför skalan förblir skalan balanserad.

Om bollen är lättare är de två första fallen inverterade.

Det finns 27 möjliga sätt att placera varje boll i alla tre vägningarna, var och en motsvarar olika resultat om den bollen är udda ut. Vi måste hitta ett arrangemang av kulor där varje möjlig uppsättning placeringar och dess inversa (för tunga och lätta fall) är distinkta – så ingen två bollar är på samma plats för alla tre vägningarna.

Här är ett preliminärt arrangemang som uppfyller egenskapen för distinkt. Lägg märke till att inget möjligt arrangemang visas mer än en gång i båda tabellerna:

 Normal Inverse Ball 1 2 3 1 2 3 1 L R 2 L R 3 L R 4 L R R L 5 L R R L 6 L R R L 7 L L R R 8 L L R R 9 L L R R 10 L L R R R L 11 L R L R L R 12 R L L L R R L = place it on the left R = place it on the right = leave it off 

Omedelbart stöter vi på problemet att vi inte lägger samma antal Om du har sju bollar på ena sidan och en på den andra kommer naturligtvis skalan att tippa åt sidan med sju bollar (såvida inte din udda boll är löjligt tung, men låt oss inte underhålla det scenario). Så vi måste invertera några av dessa konfigurationer så att vi sätter fyra på varje sida för varje vägning. Med lite försök och fel kan vi få något liknande:

 Normal Inverse Ball 1 2 3 1 2 3 1 L R 2 L R 3 R L 4 L R R L 5 R L L R 6 L R R L 7 R R L L 8 L L R R 9 L L R R 10 R R L L L R 11 R L R L R L 12 L R R R L L 

Så vårt slutliga vägningsschema för bollar är som följer:

Weighing 1: 1 4 8 12 / 5 7 10 11 Weighing 2: 2 6 9 11 / 4 7 10 12 Weighing 3: 5 8 9 10 / 3 6 11 12 

Och resultaten tolkas som sådana:

==L : 3L L== : 1H R== : 1L ==R : 3H L=L : 8H R=L : 5H =L= : 2H L=R : 5L R=R : 8L =LL : 9H LL= : 7L RL= : 4L =LR : 6H LLR : 10L RLL : 12L =R= : 2L LR= : 4H RLR : 11H =RL : 6L LRL : 11L RR= : 7H =RR : 9L LRR : 12H RRL : 10H = : scale balanced L : scale tipped to the left R : scale tipped to the right nL : ball n is light nH : ball n is heavy 

Och därmed har vi skapat ett vägningsschema där varje vägning är helt förutbestämd i förväg, som fortfarande lyckas avgöra vilken boll som är udda och om den är lättare eller tyngre.

Du kanske märker att vi inte använde LLL, RRR eller === i våra arrangemang.

Vi kan inte använda LLL och RRR som ett 13: e par för en 13: e boll, för då skulle vi slutligen behöva sätta nio bollar på skalan, och det finns inget sätt att göra det eftersom nio är udda. skulle förmodligen kunna använda det in plats för ett av LLR/RRL par, men lämnar LLL och RRR ut ger en symmetri i resultatdiagrammet som jag ganska gillar.

Det som är intressant är dock att du kan ha en 13: e boll som du aldrig placera dem på vilken skala som helst, och om dina skalor balanserar i alla tre vikter, är den 13: e kulan du aldrig vägde den udda kulan (även om du uppenbarligen inte kan säga utan att en fjärde väger om den är lättare eller tyngre).

Kommentarer

• Så, i princip kan man lösa detta med 13 bollar, om man har en 14: e etalonkula. Bra svar.
• Förmodligen till och med 14 bollar, där 14: e boll kan vara tyngre är lösbara, men det är svårare, troligtvis kan du ’ t.

Några av de befintliga svaren på den här forntida frågan är utmärkta, men det finns ett berömt svar som Jag tycker att det förtjänar att nämnas här. Det kommer från en artikel i Eureka , den årliga tidningen för University of Cambridge ”matematiska samhällsstudenter, skriven av CAB Smith under pseudonym” Blanche Descartes ”.

Den har två mycket fina funktioner. Den första är att det är en ”ungranching” -lösning: du behöver inte ändra vad du gör vid senare vägningar beroende på resultaten från tidigare. Det andra är att när du väl har sett det är det nästan omöjligt att glömma bort.

Smiths lösning är helt skriven i vers och innehåller en förklaring till hur allt fungerar, men jag kommer bara att citera faktiska svaret. ”F” här är vår huvudperson professor Felix Fiddlesticks, vars mamma har bett honom om hjälp med pusslet. Jag har gjort några smärre ändringar i den ursprungliga formateringen.

F ställde ut mynten i rad
Och krita på varje bokstav, så,
För att bilda orden: F AM NOT LICKED
(An idén i hans hjärna hade klickat.)

Och nu kommer hans mor att han kommer att föreslå:
”MA, GÖR / Gilla mig att / hitta” FAKE / COIN! ”

Var och en av de tre raderna i F: s föreläggande beskriver en vägning.När du har gjort dem alla bestämmer resultaten unikt vilket mynt som är falskt och på vilket sätt.

Kommentarer

• +1. Detta tror jag är en förskönad version av Joe Z ’ s svar

Jag tillbringade lite tid på att arbeta med detta pussel efter att det dök upp på ”Brooklyn Nine-Nine” (om du vill kan du se kapten Holt beskriva pusslet här ) och jag skrev en detaljerad, illustrerad lösning här: Island of Tyreses Solution . I denna särskild version Jag försöker hitta en öbor, Diffy, som antingen är tyngre eller lättare än de andra 11 öborna.

Lektioner

Den slutliga lösningen tar hänsyn till två saker jag lärde mig av tidigare försök:

1. I en grupp på fyra kan jag identifiera Diffy i två viktningar.

   A. Först satte jag två öbor från gruppen mot två känd icke-Dif fys. Om sågsågen lutar vet jag att Diffy är en av dessa två. Om den sågade förblir jämn, vet jag att Diffy är en av de andra två.

   B. Nu väljer jag en av de återstående två möjliga Diffys och ställer honom mot en känd icke-Diffy. Om vågen lutar har jag hittat Diffy. Om styrelsen förblir jämn, vet jag att Diffy är den sista återstående öboret.

   C. Alternativt, om sågsågen lutar i steg A och du vill veta om DIffy är tung eller lätt, kan du notera riktningen från steg A och sätta de två återstående möjliga Diffys på skalan mittemot varandra. Om sågsågen lutar i samma riktning som steg A, är Diffy den som fortfarande är på samma sida som han var under steg A. Annars, om orienteringen av sågsågen ändras, är Diffy på andra sidan.

2. I en grupp på tre kan jag identifiera Diffy i en vägning, så länge jag har riktningsinformation. Jag kommer att beskriva detta mer detaljerat under Använd # 3.

Lösning

På grund av lektion 1 kan jag dela upp fyra öbor innan jag kollar resten. Om Diffy är i den gruppen av fyra kommer den första vägningen att bli jämn, och jag kan nu identifiera honom bland de fyra med mina två återstående drag. Om Diffy inte är i den gruppen på fyra, har jag nu fyra öbor som jag kan utesluta och också använder för att tara min sågsåg.

Så för min första användning av sågsågen, jag väga de åtta återstående öborna mot varandra med fyra på varje sida.

Använd # 1

Jag har redan beskrivit min plan om den här första sågade användningen blir jämn, så vad är nästa om det blir konstigt? Det är här geni kommer in.

Jag har nu lite ”riktad information”. Jag ringer hädanefter vilken riktning som sågsågen lutar i Använd 1 ”Riktning 1 ″ eller” D1 ″ för kort. Jag vet att om Diffy är tung är han på den sida av sågsågen som gick ner, och om Diffy är lätt, så är han på den sida av sågsågen som gick upp. Om jag flyttar Diffy, kommer sågsågen att ändra riktning! Det har inget val eftersom Diffy, och bara Diffy, gör att sågningen lutar. Kom också ihåg lektion 2, jag har riktningsinformation och ett drag efter den nuvarande, så jag kan helt ta ut tre möjliga Diffys innan nästa användning av sågsågen. Jag måste använda en av de öbor som jag uteslutit i användning 1 för att hålla tre öbor på varje sida.

Använd # 2

Om Use # 2 ger oss en jämn sågning kan vi hitta Diffy i de tre vi tog bort, men om den inte gör det, måste vi vara uppmärksamma till den riktning som sågsågen rör sig. Rörde det sig på samma sätt som tidigare, riktning 1, eller ändrade det riktning till riktning 2? Vårt nästa val kommer att baseras på svaret! Om den rörde sig i riktning 1 vet vi att Diffy inte är en av öborna som bytte sida för användning # 2. Om sågen flyttas i riktning 2 är Diffy en av sidoomkopplarna. Hur som helst, vi har fått honom till att vara en av tre eller två. Användning # 3 är lite svår att generalisera eftersom det är olika för varje möjlighet.

Använd # 3

Om jag har en grupp av tre möjliga Diffy öbor, två av dessa öbor var på samma sida under användning nr 1, när sågsågen flyttade in i D1. Om jag lägger en av dessa öbor på vardera sidan om sågsågen och gungsågen åter flyttar in i D1, vet vi att Diffy är öbor på den ursprungliga sidan. Om sågningen rör sig in i D2, vet vi att Diffy är på motsatt sida av sågverket. Om den sågade förblir jämn, vet vi att Diffy är den tredje medlemmen i gruppen.

All Mapped Out

Kommentarer

• Denna lösning är felaktig för denna fråga.Det är bara acceptabelt om de ber om att identifiera Diffy men inte om han är lättare eller tyngre (se Even – Even – Även i ditt diagram har L inte viktats :)) Återigen, i så fall kan vi lösa pusslet med 13 människor.

Detta är en omskrivning av R. Allen Gilliam av Jared Andersons lösning från en annan version av detta pussel på den här webbplatsen. Kanske är det bara hur mitt sinne fungerar, men det verkar mycket lättare att förstå.

Numrera männen (eller mynt eller bollar) 1 till 12.
Väg 1 2 3 4 mot 5 6 7 8.
Om de är desamma är den andra mannen 9 10 11 eller 12. Hoppa till I nedan.
Om de är annorlunda, notera om 1 2 3 4 är tyngre eller lättare.

Väg 1 2 3 5 mot 4 10 11 12. (Lägg märke till att vi vet att 10 11 och 12 inte är olika.) Det finns tre möjligheter:
(1) Om 1235 har samma skillnad (tyngre eller lättare) som 1234, då måste den olika vara 1 2 eller 3 och ha samma skillnad (tyngre eller lättare) som 1234. Hoppa till II nedan.
(2) Om 1235 balanserar 4 10 11 12 , då måste den olika vara 6 7 eller 8 (de vi tog bort) och ha samma skillnad (tyngre eller lättare) som 5678. Hoppa till II nedan.
(3) Om 1235 nu har motsatt skillnad (tyngre eller lättare) som 1234, då är antingen 4 eller 5 annorlunda. Antingen 4 har samma skillnad som 1234 (tyngre eller lättare) eller 5 har samma skillnad som 5678 (tyngre eller lättare). Så vi väger helt enkelt 4 mot 1. Om de ”är desamma, är 5 olika. Om de” är olika, så är 4 olika.

I. Hitta vilken av 9 10 11 12 som är annorlunda med två vägningar när du inte vet om den andra är tyngre eller lättare:

Väg 9 mot 10. Två möjligheter:
(1) Om de ”är annorlunda, då måste det vara 9 eller 10. Väg 9 och 11. Om de är desamma är 10 olika. Om de” är olika, är det 9.
(2) Om de ”är samma, då måste det vara 11 eller 12. Väg 9 och 11. Om de” är samma, är 12 olika. Om de ”är olika, är det 11.
(Om det” s 12 vet vi inte om han var tyngre eller lättare eftersom vi aldrig vägde honom. Vi hittade honom genom eliminering. Han måste vara en annan eftersom alla andra väger samma.)

II. Hitta vilken av tre män som är annorlunda med en vägning när du vet om den andra är tyngre eller lättare:

Byt namn på de tre männen 1 2 3. Väg 1 mot 2. Två möjligheter:
(1) Om de ”är desamma, är 3 olika.
(2) Om de” är olika, beroende på vilken som har rätt skillnad rence (tyngre eller lättare) är den annorlunda.

Detta verkar vara den enklaste lösningen för 12 objekt om du bara måste hitta objektet med olika vikt, som vissa versioner av pusslet frågar. Joe Z: s lösning kan hitta artikeln och skillnaden med 12 artiklar, och den olika artikeln med 13 artiklar. Att hitta olika objekt och skillnaden med 14 artiklar verkar matematiskt omöjligt med 3 vägningar eftersom det bara finns 27 möjliga resultat med 3 vägningar och det finns 28 möjligheter med 14 artiklar. Men kan en variant av Joe Z: s lösning hitta de olika artiklarna av 13, och om det är tyngre eller lättare? Om så är fallet, hitta då den andra men inte skillnaden med 14 objekt skulle vara möjliga. Att hitta den andra men inte skillnaden av 15 skulle vara omöjlig eftersom du bara kan lämna ett objekt ur vägningarna samtidigt som du fortfarande kan identifiera det olika, och om du väger föremålet kommer du att vet om det är lättare eller tyngre vilket vi vet är matematiskt omöjligt med 14 objekt.

Denna lösning liknar den som tillhandahålls av R Gilliam men skiljer sig åt i det andra steget de bollarna i 3 grupper om 4 bollar vardera. Låt oss kalla dem g1 g2 och g3 välj valfria två grupper och väga dem mot varandra. Ett av två scenarier är sant. Pannorna är balanserade: de 8 bollar du just vägde har alla rätt vikt. Pannorna är obalanserade: Fyra kulor som du inte väger har alla rätt vikt.

Hur som helst i slutet av den första vägningen har du minst fyra kulor med rätt vikt.

För den andra vägningen ena sidan av kokkärlet ska ha 3 kulor med rätt vikt. Om kokkärlen var obalanserade efter den första vägningen, sätt 3 kulor från en av de obalanserade kokkärlen i den andra kokkärlet. 4 kulor som satt ut den första vägen i den andra pannan.

Om kokkärlen är obalanserade efter denna vägning kommer du att få veta om oddballen är tyngre eller lättare eftersom en av kokkärlen innehåller kulor med rätt vikt. Om kokkärlen är balanserade är den fjärde bollen som utelämnats udda och du kan ta reda på om den är tyngre eller li väga den mot en boll med rätt vikt.

Om stekpannorna är obalanserade vet du om oddballen är tyngre eller lättare. Ta 2 av de 3 kulorna från pannan (som inte innehåller rätt viktkulor) och väga dem mot varandra. Du vet redan om oddball är tyngre eller lättare. Om kokkärlen är obalanserade väljer du den kokkärl som matchar oddbollens viktriktning. om stekpannorna är balanserade är den tredje kulan udda.

Du kan också lösa det med 4 grupper om 3 bollar . Väg 3 mot 3 och om det balanserar kan du hålla de 6 bollarna åt sidan som kända-lika. Om de inte balanserar, vet du att udda bollen är i den gruppen av 6. Därefter väger du 3 av de kända-lika mot någon av de två grupperna med 3 okända. Om den balanserar är den udda i finalen grupp 3. Om den inte balanserar, vet du att den udda fortfarande finns på skalan. Slutligen, använd den sista gruppen av tre bollar som är okänd och ojämn, sätt en i varje ände och håll den tredje åt sidan. Om skalan balanserar, vet du att den ensamma bollen du höll åt sidan är den udda bollen. Om skalan inte balanserar, vet du att udda bollen är på skalan. För att bestämma udda bollen och om den är tyngre eller lättare måste du ha noterat om den okända gruppen var tyngre eller lättare än den kända-lika grupper. Om de var tyngre är den ensamma bollen tyngre.

Kommentarer

• ” För att bestämma udda boll och om den ’ är tyngre eller lättare, måste du ha noterat om den okända gruppen var tyngre eller lättare än de kända lika grupperna. ” Om alla tre grupper som du vägde i de två första vägningarna var lika, har du inte ’ den här informationen.

(1) Placera kulorna 6 och 6 på skalan. Ta bort en från varje sida tills skalan balanserar.

(2) Ta de sista två borttagna (eller återstående två om skalan aldrig balanseras) och placera på ena sidan (sida A) och två lika viktade kulor på andra (sida B). Om sida A är lägre är oddboll tyngre, om sida B är lägre är oddball lättare. Ta bort en från varje sida. Om skalan balanserar är bollen som tas bort från sida A udda, om inte bollen kvar på sida A är.

Kommentarer

• Det kräver upp till sju vägningar. Problemet ber dig att göra det i tre.
• @nosun – Välkommen till puzzling.se. Bara för att meddela dig blir felaktiga svar ibland nedröstade för att skilja dem från bra svar. Detta är inte avsett att avskräcka dig från att ge bra svar på andra frågor.