Tolv baller og en skala

Del dette i n til tre grupper på fire, A1, A2, A3, A4; B1, B2 …; C1, C2 … Hvert trinn her tilsvarer en veiing.

• Vei A mot B.
  • Hvis A> B, veier deretter A1, B1 og B2 mot B3 , B4 og C1.
    • Hvis vektene er like, er en av A2 … 4 tyngre; veier A2 og A3. Hvis de er like, er A4 tyngre. Hvis en er tyngre, er den ballen tyngst.
    • Hvis den første gruppen er tyngre, er enten A1 tyngre, eller B3-4 er lettere. Sammenlign B3 og B4; hvis de er like, er A1 tyngre; hvis de er forskjellige, er den letteste den letteste ballen.
    • Hvis den første gruppen er lettere, er enten B1 eller B2 lettere. Vei dem og se.
  • Hvis A < B, nummerer alle A-baller til B-baller og utfør ovennevnte trinn.
  • Hvis A = B, veier A1, A2, A3 mot C1, C2, C3
    • Hvis de er like, veier du A1 mot C4. Hvis A1 er lettere, er C4 den rare ballen og den er tung. Hvis A1 er tyngre, er C4 den rare ballen og den er lett.
    • Hvis A er tyngre enn C, veier du C1 mot C2. Hvis de er like, er C3 den rare ballen og den er lettere. Hvis de ikke er like, er den lettere av de to kulene den letteste kulen
    • Hvis A er lettere enn C, veier du C1 mot C2. Hvis de er like, er C3 den rare ballen, og den er tyngre. Hvis de ikke er like, er den tyngre av de to ballene den tyngste ballen.

Vi kan jobbe bakover fra det tredje trinnet for å se omtrent hvordan dette fungerer. Ved den tredje veien må alternativene reduseres til enten to eller tre baller. Dette betyr at den andre veien må reduseres til to eller tre mulige kuler.

Vi vet at det første trinnet vil fjerne enten 1/3 eller 2/3 av de mulige løsningene, uansett hva du gjør. Dette betyr at, i 1/3 tilfelle, må du dele mulighetene ned fra 8 i en gruppe på 3, en gruppe på 3 og en gruppe på 2. Fra dette peker den tredje veien til den odde ballen ut. Fordi denne saken antyder at ett sett med baller er tyngre, i kraft av å finne den rare ballen ut, vet vi om den er tyngre eller lettere, så vi trenger ikke å bekymre oss for denne informasjonen i det hele tatt.

I tilfelle 2/3 må du redusere mulighetene til en gruppe på 3 og en gruppe på 1, noe som er enkelt nok til å gjøre intuitivt. Fordi vi faktisk ikke vet den relative vekten til den odde ballen i dette tilfellet, må informasjonen fra den tredje veien brukes til å avgjøre om ballen er tyngre eller lettere.

Kommentarer

• Selv om dette svaret er riktig, håpet jeg på et svar som ville forklare strategien bak valg av gjenstander som skal veies.
• @JoeZ. I ‘ har lagt til litt om hvordan jeg bestemte dette svaret, selv om jeg ‘ ikke er sikker på at jeg kan snakke med en generell løsning på dette problemet. (Også FYI, jeg ‘ har redigert svaret mitt på det andre spørsmålet ditt.)
• Det du ‘ har satt opp er fint. Jeg tenkte å resonnere mer enn strategi, kom til å tenke på det igjen.

Der er en annen måte å gjøre dette problemet på, som ikke involverer noen form for betinget forgrening i det hele tatt. Det er faktisk mulig å sette en fast veieplan på forhånd og fremdeles bestemme hvilken ball som er lettere eller tyngre på bare tre veier. Jeg forklarer hvordan nedenfor.

Kjernen i problemer som disse er, hvor mye informasjon kan du få fra prosedyren du har lov til å gjennomføre? For hver veiing kan vekten enten tippe til venstre, tippe til høyre eller holde seg balansert.Dette gir deg totalt 3 ³ = 27 mulige resultater, og i dette tilfellet må du se 24 resultater fra dem (en av 12 baller er enten lette eller tunge, som er 12 × 2 = 24 ).

Så vi må starte den kjedelige oppgaven med å kartlegge hvert resultat til et resultat.

En av tingene vi umiddelbart kan legge merke til er at det også er tre stater hver ball kan være inne under hver veiing – på venstre side av vekten, på høyre side av vekten eller utenfor vekten. Naturligvis kartlegges dette til tilstandene på skalaen på en måte som er intuitivt analog:

Hvis den odde ballen ut er tyngre …

• og ballen er plassert på venstre side, vil vekten vippe mot venstre.
• og ballen er plassert på høyre side, vekten vil vippe mot høyre.
• og ballen er utenfor skalaen vil skalaen forbli balansert.

Hvis ballen er lettere, blir de to første sakene invertert.

Det er 27 mulige måter å plassere hver ball på. i alle tre veiingene, som hver tilsvarer et annet resultat hvis den ballen er den rare. Vi må finne et arrangement av kuler der hvert mulig sett med plasseringer og dens inverse (for tunge og lette tilfeller) er forskjellige – så ingen to kuler er på samme sted for alle tre veiingene.

Her er det en foreløpig ordning som tilfredsstiller egenskapen for egenart. Legg merke til at ingen mulige ordninger vises mer enn én gang i begge tabellene:

 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 

Med en gang støter vi på problemet med at vi ikke legger det samme antallet baller på hver skala. Hvis du har syv baller på den ene siden og den ene på den andre, vil selvfølgelig skalaen vippe til siden med syv baller (med mindre oddetallsspillet ditt er latterlig tungt, men la oss ikke underholde det scenario). Så vi må snu noen av disse konfigurasjonene slik at vi legger fire på hver side for hver veiing. Med litt prøving og feiling kan vi få noe sånt som dette:

 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år siste veieplan for baller er som følger:

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 

Og resultatene tolkes slik:

==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 

Og dermed har vi laget et veiingsskjema der hver veiing er helt forhåndsbestemt på forhånd, som fremdeles klarer å bestemme hvilken ball som er den merkelige ut, og om den er lettere eller tyngre.

Du vil kanskje legge merke til at vi ikke brukte LLL, RRR, eller === i arrangementene våre.

Vi kan ikke bruke LLL og RRR som et 13. par for en 13. ball, for da skulle vi ende opp med å sette ni baller på skalaen, og det er ingen måte å gjøre det siden ni er merkelig. kunne sannsynligvis brukt den i sted for ett av LLR/RRL parene, men etterlater LLL og RRR ut gir en symmetri i resultatdiagrammet som jeg heller liker.

Det som er interessant er imidlertid at du kan ha en 13. ball som du aldri plasser dem på en hvilken som helst skala, og hvis skalaene dine balanserer i alle tre veier, er den 13. ballen du aldri veide, den rare ballen ut (selv om du tydeligvis ikke kan fortelle uten at en fjerde veier om den er lettere eller tyngre).

Kommentarer

• Så, i utgangspunktet kan man løse dette med 13 baller, hvis man har 14. etalonkule. Flott svar.
• Sannsynligvis er til og med 14 baller, der 14. ball kan være tyngre, løselig, men det er vanskeligere, mest sannsynlig kan du ‘ t.

Noen av de eksisterende svarene på dette eldgamle spørsmålet er utmerket, men det er et kjent svar at Jeg synes fortjener å bli nevnt her. Den kommer fra en artikkel i Eureka , det årlige magasinet til University of Cambridge student matematisk samfunn, skrevet av CAB Smith under pseudonymet «Blanche Descartes».

Den har to veldig fine funksjoner. Den første er at det er en «uforgrenet» løsning: du trenger ikke å endre hva du gjør på senere veier, avhengig av resultatene fra tidligere. Det andre er at når du først har sett det, er det nesten umulig å glemme.

Smiths løsning er skrevet helt i vers og inneholder en forklaring på hvordan det hele fungerer, men jeg skal bare sitere faktisk svar. «F» her er vår hovedperson professor Felix Fiddlesticks, hvis mor har bedt ham om hjelp med puslespillet. Jeg har gjort noen småtterier i den opprinnelige formateringen.

F satte myntene ut på rad
Og krittet på hver en bokstav, så,
For å danne ordene: F AM NOT LICKED
(An ideen i hjernen hans hadde klikket.)

Og nå skal moren hans «påta seg:
» MA, DO / LIKE
ME TO / FIND
FAKE / COIN! «

Hver av de tre linjene i Fs påbud beskriver en veiing.Når du har gjort dem alle, bestemmer resultatene unikt hvilken mynt som er falsk og på hvilken måte.

Kommentarer

• +1. Dette tror jeg er en forskjønnet versjon av Joe Z ‘ s svar

Jeg brukte litt tid på å jobbe med dette puslespillet etter at det dukket opp på «Brooklyn Nine-Nine» (hvis du vil, kan du se kaptein Holt beskrive puslespillet her ) og jeg skrev en detaljert, illustrert løsning her: Island of Tyreses Solution . I denne bestemt versjon Jeg prøver å finne en øyboer, Diffy, som enten er tyngre eller lettere enn de andre 11 øyboerne.

Leksjoner

Den endelige løsningen tar hensyn til to ting jeg lærte av tidligere forsøk:

1. I en gruppe på fire kan jeg identifisere Diffy i to veier.

   A. Først setter jeg to øboere fra gruppen mot to kjent ikke-Dif fys. Hvis sagen vipper, vet jeg at Diffy er en av disse to. Hvis sagen forblir jevn, vet jeg at Diffy er en av de to andre.

   B. Nå velger jeg en av de resterende to mulige Diffys og setter ham mot en kjent ikke-Diffy. Hvis vekten vipper, har jeg funnet Diffy. Hvis styret forblir jevnt, vet jeg at Diffy er den siste gjenværende øyboeren.

   C. Alternativt, hvis sagen vipper i trinn A, og du vil vite om Dffy er tung eller lett, kan du merke retningen fra trinn A og sette de to gjenværende mulige Diffys på skalaen overfor hverandre. Hvis sagen vipper i samme retning som trinn A, er Diffy den som fremdeles er på samme side som han var under trinn A. Ellers er Diffy på den andre siden hvis retningen til sagen endrer seg.

2. I en gruppe på tre kan jeg identifisere Diffy i en veiing, så lenge jeg har retningsinformasjon. Jeg vil beskrive dette nærmere under Bruk # 3.

Løsning

På grunn av leksjon nr. 1 kan jeg dele opp fire øyboere før jeg sjekker resten. Hvis Diffy er i den gruppen på fire, vil den første veien komme ut til og med, og jeg kan nå identifisere ham blant de fire med mine to gjenværende trekk. Hvis Diffy ikke er i den gruppen på fire, har jeg nå fire øyboere som jeg kan utelukke, og som jeg også bruker til å tare sagen min.

Så for min første bruk av sagen, jeg veie de åtte gjenværende øyboerne mot hverandre med fire på hver side.

Bruk # 1

Jeg har allerede skissert planen min hvis denne første seesag-bruken viser seg jevn, så hva er neste hvis det viser seg rart? Det er her geniet kommer inn.

Jeg har nå litt «retningsinformasjon.» Jeg vil heretter ringe hvilken retning sagen vippes i bruk 1 «Retning 1 ″ eller» D1 ″ for kort. Jeg vet at hvis Diffy er tung, er han på den delen av sagen som gikk ned, og hvis Diffy er lett, er han den delen av sagen som gikk opp. Hvis jeg flytter Diffy, vil sagen endre retning! Det har ikke noe valg fordi Diffy, og bare Diffy, får sagen til å vippe. Husk også leksjon nr. 2, jeg har retningsinformasjon og ett trekk etter den nåværende, slik at jeg helt kan ta ut tre mulige Diffys før neste bruk av sagen. Jeg må bruke en av øyboerne jeg utelukket i bruk 1 for å holde tre øboere på hver side.

Bruk # 2

Hvis Use # 2 gir oss en jevn vipp, kan vi finne Diffy i de tre vi fjernet, men hvis den ikke gjør det, må vi ta hensyn til retningen som sagen beveger seg. Flyttet den på samme måte som før, retning 1, eller endret den retning til retning 2? Vårt neste valg vil være basert på svaret! Hvis den flyttet i retning 1, så vet vi at Diffy ikke er en av øyboerne som byttet side for bruk # 2. Hvis sagen flyttes i retning 2, er Diffy en av sidebryterne. Uansett har vi fått ham til å være en av tre eller to. Bruk # 3 er litt vanskelig å generalisere siden det er forskjellig for hver mulighet.

Bruk # 3

I tilfelle der jeg har en gruppe på tre mulige Diffy Islanders, to av disse øyboerne var på samme side under bruk # 1, da seesagen flyttet inn i D1. Hvis jeg setter en av disse øyboerne på hver side av sagen, og sagen vender tilbake til D1, så vet vi at Diffy er øyboeren på den opprinnelige siden. Hvis sagen beveger seg inn i D2, så vet vi at Diffy er på motsatt side av sagen. Hvis seesagen forblir jevn, vet vi at Diffy er det tredje medlemmet av gruppen.

All Mapped Out

Kommentarer

• Denne løsningen er feil for dette spørsmålet.Det er bare akseptabelt hvis de ber om å identifisere Diffy, men ikke om han er lettere eller tyngre (se Even – Even – Selv i diagrammet ditt har ikke L blitt vektet :)) Så igjen, i så fall kan vi løse puslespillet med 13 mennesker.

Dette er en omskrivning av R. Allen Gilliam av Jared Andersons løsning fra en annen versjon av dette puslespillet på dette nettstedet. Kanskje det bare er hvordan tankene mine fungerer, men dette virker mye lettere å forstå.

Nummer mennene (eller myntene eller ballene) 1 til 12.
Vei 1 2 3 4 mot 5 6 7 8.
Hvis de er de samme, så er den forskjellige mannen 9 10 11 eller 12. Hopp til I nedenfor.
Hvis de er forskjellige, må du merke om 1 2 3 4 er tyngre eller lettere.

Vei 1 2 3 5 mot 4 10 11 12. (Legg merke til at vi vet at 10 11 og 12 ikke er forskjellige.) Det er tre muligheter:
(1) Hvis 1235 har det samme forskjell (tyngre eller lettere) som 1234, så må den forskjellige være 1 2 eller 3 og har samme forskjell (tyngre eller lettere) som 1234. Hopp til II nedenfor.
(2) Hvis 1235 balanserer 4 10 11 12 , så må den forskjellige være 6 7 eller 8 (de vi fjernet) og har samme forskjell (tyngre eller lettere) som 5678. Hopp til II nedenfor.
(3) Hvis 1235 nå har motsatt forskjell (tyngre eller lettere) som 1234, så er enten 4 eller 5 den forskjellige. Enten 4 har samme forskjell som 1234 (tyngre eller lettere) eller 5 har samme forskjell som 5678 (tyngre eller lettere). Så vi veier rett og slett 4 mot 1. Hvis de «er like, så er 5 den forskjellige. Hvis de» er forskjellige, så er 4 den forskjellige.

Jeg Finne hvilken av 9 10 11 12 som er forskjellig med to veier når du ikke vet om den forskjellige er tyngre eller lettere:

Vei 9 mot 10. To muligheter:
(1) Hvis de «er forskjellige, så må det være 9 eller 10. Vei 9 og 11. Hvis de» er like, er 10 den forskjellige. Hvis de «er forskjellige, er det 9.
(2) Hvis de «er det samme, så må det være 11 eller 12. Vei 9 og 11. Hvis de» er det samme, er 12 det forskjellige. Hvis de «er forskjellige, er det 11.
(Hvis det» s 12 vet vi ikke om han var tyngre eller lettere siden vi aldri veide ham. Vi fant ham ved eliminering. Han må være den andre siden alle de andre veier det samme.)

II. Finn hvilken av tre menn som er forskjellig med en veiing når du vet om den forskjellige er tyngre eller lettere:

Gi de tre mennene nytt navn 1 2 3. Vei 1 mot 2. To muligheter:
(1) Hvis de «er like, er 3 den forskjellige.
(2) Hvis de» er forskjellige, avhengig av hvilken som har riktig forskjell rence (tyngre eller lettere) er den forskjellige.

Dette ser ut til å være den enkleste løsningen for 12 gjenstander hvis du bare må finne gjenstanden med ulik vekt, som noen versjoner av puslespillet spør. Joe Zs løsning kan finne varen og forskjellen med 12 gjenstander, og den forskjellige varen med 13 gjenstander. Å finne den forskjellige varen og forskjellen med 14 gjenstander virker matematisk umulig med 3 veier fordi det bare er 27 mulige resultater med 3 veier og det er 28 muligheter med 14 gjenstander. Men kan en variant av Joe Zs løsning finne de forskjellige varene av 13, og om det er tyngre eller lettere? Hvis ja, så finn den forskjellige, men ikke forskjellen med 14 å finne den forskjellige, men ikke forskjellen ut av 15, ville være umulig fordi du bare kan la en vare være utenfor vektene mens du fremdeles er i stand til å identifisere den andre, og hvis du veier varen, vil du vet om det er lettere eller tyngre som vi vet er matematisk umulig med 14 elementer.

Denne løsningen ligner på den som er gitt av R Gilliam, men skiller seg ut i andre trinn de ballene i 3 grupper på 4 baller hver. La oss kalle dem g1 g2 og g3 velg to grupper og veie dem mot hverandre. Ett av to scenarier er sant. Pannene er balanserte: de 8 kulene du nettopp veide har riktig vekt. Pannene er ubalanserte: Fire kuler du ikke veide, har alle riktig vekt.

Uansett ved slutten av den første veien har du minst 4 kuler med riktig vekt.

For den andre veien den ene siden av gryten skal ha 3 kuler med riktig vekt. Hvis grytene var ubalanserte etter den første veien, satte du 3 kuler fra en av de ubalanserte grytene i den andre gryten. Fire kuler som satt ut den første veien i den andre pannen.

Hvis pannene er ubalanserte etter denne veien, vil du vite om oddballen er tyngre eller lettere siden en av pannene inneholder kuler med riktig vekt. Hvis pannene er balansert, er den fjerde ballen som ble utelatt oddball, og du kan finne ut om den er tyngre eller li ved å veie den mot en ball med riktig vekt.

Hvis pannene er ubalanserte, vet du om oddballen er tyngre eller lettere. Ta 2 av de 3 kulene fra pannen (som ikke inneholder de riktige vektballene) og veie dem mot hverandre. Du vet allerede om oddball er tyngre eller lettere. Hvis grytene er ubalanserte, velg pannen som samsvarer med oddballens vektretning. hvis pannene er balansert, er den tredje ballen oddballen.

Du kan også løse den ved å bruke 4 grupper på 3 baller . Vei 3 mot 3, og hvis det balanserer, kan du holde de 6 kulene til side som kjent. Hvis de ikke balanserer, vet du at den odde ballen er i den gruppen på 6. Deretter veier du 3 av de kjente likene mot en av de to gruppene på 3 ukjente. Hvis den balanserer, er den rare i finalen gruppe på 3. Hvis den ikke balanserer, vet du at den rare er fortsatt på skalaen. Til slutt bruker du den siste gruppen på 3 baller som er ukjent og ulik, og legger en i hver ende og holder den tredje til side. Hvis skalaen balanserer, vet du at den ensomme ballen du holdt til side, er den rare ballen. Hvis skalaen ikke balanserer, vet du at den odde ballen er på skalaen. For å bestemme den odde ballen og om den er tyngre eller lettere, må du ha lagt merke til om den ukjente gruppen var tyngre eller lettere enn den kjent-like grupper. Hvis de var tyngre, er den ensomme ballen tyngre.

Kommentarer

• » For å bestemme odd ball og om den ‘ er tyngre eller lettere, må du ha merket deg om den ukjente gruppen var tyngre eller lettere enn de kjent-like gruppene. » Hvis alle de tre gruppene du veide i de to første veiene var like, har du ikke ‘ ikke denne informasjonen.

(1) Plasser kulene 6 og 6 på skalaen. Fjern en fra hver side til skalaen balanserer.

(2) Ta de to siste fjernet (eller gjenværende to hvis skalaen aldri balanseres) og legg på den ene siden (side A) og to like vektede kuler på den andre (side B). Hvis side A er lavere er oddball tyngre, hvis side B er lavere oddball er lettere. Fjern en fra hver side. Hvis skala balanserer, er ballen som er fjernet fra side A oddballen, hvis ikke ballen som er igjen på side A er.

Kommentarer

• Det krever opp til syv veier. Problemet ber deg gjøre det i tre.
• @nosun – Velkommen til puzzling.se. Bare for å gi deg beskjed, blir feil svar noen ganger nedstemt for å skille dem fra gode svar. Dette er ikke ment å fraråde deg å gi gode svar på andre spørsmål.