Our suită recentă de puzzle-uri a prezentat cântarul umil cu două paturi, un simbol istoric al comerțului și guvernului, al artei și al științei. Cântarele de echilibru sunt, de asemenea, populare în matematica recreativă. Puzzle-urile de echilibru necesită un raționament clar, logic și se pretează bine generalizării matematice. Să vedem cum Cuante cititorii au echilibrat aceste calități în puzzle-urile de mai jos.
puzzle 1
Ai opt monede identice. Unul este contrafăcut și mai ușor decât celelalte, care au greutăți identice. Găsiți moneda rea în două cântăriri. Găsiți formula generală pentru numărul maxim de monede pentru care o puteți găsi pe cea contrafăcută x cântăriri.
Abordarea unei versiuni simple a unei probleme dezvăluie adesea cheia soluției. În acest caz, imaginați-vă că aveți doar trei monede, dintre care una mai ușoară decât celelalte două. Dacă cântărești pe oricare dintre ele față de unul dintre celelalte două, fie se vor echilibra, fie nu. Dacă nu, știți care este mai ușor. Dacă se echilibrează, atunci al treilea este cel ușor. Ai nevoie doar de o singură cântărire.
Deci, în acest puzzle, dacă puteți izola un grup de trei (sau mai puține) care conține moneda ușoară în prima cântărire, veți avea nevoie doar de încă o cântărire. Puteți face acest lucru echilibrând oricare trei față de oricare alte trei. Dacă cele două grupuri sunt dezechilibrate, ați găsit grupul care îl conține pe cel ușor și puteți proceda ca mai sus pentru a doua cântărire. Dacă se echilibrează, cântărește cele două monede rămase una față de alta și o vei găsi pe cea ușoară.
Observați că acest lucru funcționează și dacă sunt trei în grupul necântărit, așa că am fi putut începe cu nouă monede. Urmând această logică, și începând cu trei monede, pentru fiecare cântărire suplimentară putem găsi moneda ușoară în trei ori numărul de monede pe care îl aveam anterior. Formula care ne oferă numărul maxim de monede n in w cântăririle este prin urmare n = 3w.
puzzle 2
Ai 12 monede identice. Unul este fie mai greu, fie mai ușor decât celelalte, care au greutăți identice.
-
Găsiți moneda rea în trei cântăriri.
-
Care este numărul maxim de monede pentru care o poți găsi pe cea proastă în patru cântăriri? Descrieți cum ați găsi moneda falsă.
Soluția la acest puzzle a fost bine descrisă de Ted, care a mai arătat că, de fapt, puteți detecta moneda rea dintre 13 monede în trei cântăriri. Iată soluția lui Ted (cu indentări pentru a separa cele trei cântăriri în fiecare caz):
Începe prin a cântări 4 monede vs 4 monede.
Cazul 1: Dacă este dezechilibrat, pentru a doua cântărire puneți câte 2 părți mai grele de pe ambele părți ale cântarului împreună cu câte 1 din partea mai ușoară.
1a: Dacă este dezechilibrat, moneda proastă este fie cele 2 monede aflate încă pe partea grea, fie moneda unică aflată încă pe partea ușoară.
Cântărește cele 2 posibile monede grele, cea proastă este fie cea mai grea dintre cele două, fie cea ușoară, dacă sunt echilibrate.
1b: Dacă a doua cântărire este echilibrată, moneda proastă este una dintre cele 2 neutilizate din partea mai ușoară a primei cântăriri.
Cântărește-le unul împotriva celuilalt, cel mai ușor este rău.
Cazul 2: Dacă este echilibrată, moneda proastă este una dintre cele 5 rămase. Cântărește 3 dintre acestea față de oricare 3 cântăriți deja (care se știe [a fi] bune).
Cazul 2a: Dacă este dezechilibrat, știți că moneda proastă este una dintre acele 3 și dacă este ușoară sau grea.
A treia cântărire este oricare 2 dintre ele unul împotriva celuilalt - dacă este dezechilibrat, aceasta identifică moneda proastă, dacă este echilibrată, este ultima dintre cele trei.
Cazul 2b: Dacă a doua cântărire este echilibrată, moneda proastă este una dintre cele 2 rămase.
Cântărește oricare dintre ele față de o monedă bună cunoscută. Dacă acest rezultat este dezechilibrat, această monedă nouă este proastă și știi dacă este grea sau ușoară. Dacă acest rezultat este echilibrat, a 13-a monedă este proastă, dar nu se știe dacă este grea sau ușoară (ceea ce nu trebuie să știm, așa că am terminat).
Ted de asemenea, a arătat că numărul maxim de monede pentru patru cântăriri este de 40. Formula pentru acest puzzle este: n = (3w − 1)/2.
Pentru celelalte puzzle-uri, formulele generalizate sunt încă în curs de investigare de către matematicieni profesioniști și fac obiectul unor lucrări publicate, dintre care unele au fost citate de către Rainer aus dem Spring. Mă voi limita la soluții pentru numărul mic de monede pe care le luăm în considerare în puzzle-uri și voi aminti doar generalizări care decurg firesc din metodele folosite în aceste cazuri.
puzzle 3
Aceasta este o variantă a puzzle-ului 1. Aveți din nou opt monede identice, dintre care una este mai ușoară decât celelalte. Cu toate acestea, acum aveți trei scale. Două dintre cântare funcționează, dar al treilea este stricat și dă rezultate aleatorii (uneori este corect și alteori greșit). Nu știi care cântar este stricat. De câte cântăriri vor fi necesare pentru a găsi moneda uşoară?
După cum am văzut în problema 1, aceasta necesită doar două cântăriri cu o balanță bună. De asemenea, știm că cele două balanțe bune vor fi întotdeauna de acord, așa că dacă doar repetăm fiecare cântărire pe toate cele trei balanțe, vom avea răspunsul în șase cântăriri, așa cum a sugerat un cititor. Dacă încercăm să o facem într-un număr mai mic de cântăriri, devine puțin complicat. Nu putem identifica un cântar bun doar cântărind aceleași monede pe două cântare, pentru că, chiar dacă sunt de acord, oricare dintre cele două ar putea fi totuși un cântar prost. (Acest lucru arată, de asemenea, cât de ușor dezinformarea sau informațiile aleatorii pot înfunda adevărul.)
De fapt, această problemă poate fi rezolvată, foarte inteligent, în doar patru cântăriri! Rainer aus dem Spring a postat soluția folosind o notație nouă care pare să fi fost creată pentru acest puzzle. Dar înainte de a merge acolo, vreau să-ți imaginezi un scenariu care sper să facă lucrurile mai intuitive.
Imaginați-vă că sunteți un detectiv care investighează o lovitură într-o țară mică ale cărei mașini au plăcuțe de înmatriculare din două cifre folosind doar cifrele 0, 1 și 2. Trei persoane, A, B și C, au observat incidentul. Doi dintre ei răspund întotdeauna corect la o întrebare cu trei variante, iar unul oferă răspunsuri complet aleatorii. Nu știi cine este cel care răspunde la întâmplare. Trebuie să le pui fiecăruia o singură întrebare cu trei variante și apoi să o alegi pe cea care spune cu siguranță adevărul pentru a obține mai multe informații.
Iată cum o faci. Întrebați-l pe A dacă prima cifră este 0, 1 sau 2. Să presupunem că A spune 2. Întrebați-l pe B dacă a doua cifră este 0, 1 sau 2. Să presupunem că B spune 1. Apoi cereți-i lui C să aleagă între aceste trei afirmații:
- Doar A spune adevărul.
- Doar B spune adevărul.
- Ambii spun adevărul.
Îl poți crede pe cel pe care ți-l spune C și îl poți întreba despre cealaltă cifră. Pentru a vedea de ce, luați în considerare că dacă A minte, atunci C este de încredere și va spune că B spune adevărul. A doua cifră va fi de fapt 1 și apoi îl puteți întreba pe B despre prima cifră. În mod similar, dacă B minte, atunci C este din nou de încredere și va spune că A spune adevărul. Atunci prima cifră este de fapt 2 și puteți întreba A despre a doua cifră. În cele din urmă, dacă C minte, atunci atât A cât și B sunt de încredere, așa că poți în continuare să crezi și să alegi pe cine spune C. (Și dacă C spune că atât A cât și B spun adevărul, atunci trebuie să fie amândoi.) Cheia aici este că alegerea dvs. de întrebări nu permite lui C să mintă în așa fel încât să pună la îndoială atât A cât și B. Deoarece cel puțin unul dintre A și B trebuie să fie de încredere, îl puteți alege întotdeauna pe cel cu care C este de acord, chiar dacă este doar un răspuns aleatoriu. Dacă toți trei sunt de acord, atunci aveți deja ambele cifre ale plăcuței de înmatriculare.
Iată cum să traducem această poveste înapoi în puzzle-ul nostru. Cântarele sunt A, B și C. Puteți traduce cele două cifre ale plăcuței de înmatriculare în monede după cum urmează: 01 este moneda 1, 02 este moneda 2, 10 este moneda 3, 11 este moneda 4, 12 este moneda 5, 20 este moneda 6, 21 este moneda 7 și 22 este moneda 8. Cititorii pricepuți vor recunoaște că acesta este sistemul numeric de bază 3 (sau ternar). De asemenea, rețineți că există un număr posibil suplimentar 00, pe care îl puteți utiliza pentru o a noua monedă pentru care această tehnică va funcționa și ea, ca în puzzle-ul 1.
Pentru prima cântărire, împărțiți monedele la prima lor cifră (baza 3), astfel încât cele trei grupuri ale voastre vor fi monede [1, 2], [3, 4, 5] și [6, 7, 8]. Cântăriți [3, 4, 5] față de [6, 7, 8] pe cântarul A. Dacă A funcționează bine, veți avea grupul corect de prima cifră ca în puzzle-ul 1. În mod similar, pentru a doua cântărire pe cântarul B grupurile dvs. vor fi cele cu aceeași a doua cifră: [1, 4, 7], [2, 5, 8] și [3, 6]. Dacă B funcționează bine, veți avea a doua cifră corectă. Pentru a treia cântărire, pe scara C, cântăriți grupul pe care A l-a identificat cu grupul pe care l-a făcut B. Urmând exemplul nostru, pentru 21, grupurile vor fi [6, 7, 8] și [1, 4, 7]. Moneda 7 nu poate fi pusă pe ambele părți în același timp, așa că o lăsăm afară și cântărim [6, 8] și [1, 4] una față de cealaltă. Rețineți că, dacă A și B sunt ambele de încredere, atunci 7 este de fapt răspunsul corect și nu contează care parte iese mai ușoară pe C. Dacă întâmplător cântărirea pe C este echilibrată, atunci toate cele trei cântare sunt de acord și ai răspunsul tău (moneda 7) în doar trei cântăriri. Dacă A este de încredere și B nu, moneda mai ușoară este în [6, 8], care scară C va confirma, iar dacă B este de încredere și A nu este, moneda mai ușoară este în [1, 4], care scară C va confirma de asemenea.
Deci, în trei cântăriri, fie am identificat moneda ușoară, fie am restrâns-o la un grup de doi și am identificat și o cântar de lucru. A patra cântărire fie pe cântarul A, fie pe cântarul B (oricare dintre cântarul C a fost de acord) va face restul.
Această soluție mi se pare uimitor de frumoasă!
Această metodă poate fi generalizată pentru a găsi moneda ușoară între 32x monede în 3x + 1 cântăriri cu setul dat de cântare. Astfel, aveți nevoie de șapte cântăriri pentru 81 de monede. Pentru un număr mai mare de monede (>~1,000), o soluție și mai puternică există.
puzzle 4
Ai 16 monede, dintre care opt sunt grele și de aceeași greutate. Celelalte opt sunt usoare si de aceeasi greutate. Nu știi ce monede sunt grele sau ușoare. Monedele arată identic, cu excepția uneia care are marcaje speciale. Cu un cântar bun, vă puteți da seama dacă moneda specială este ușoară sau grea în trei cântăriri? Care este numărul maxim de monede cu care puteți începe și rezolva cu succes această problemă în patru cântăriri?
La prima vedere, acest puzzle pare aproape imposibil de realizat în trei cântăriri, după cum a concluzionat unul dintre cititorii noștri. Cu toate acestea, cu o oarecare inteligență se poate face și ambele Ted și Rainer aus dem Spring a oferit soluții corecte. Ted a oferit câteva principii generale neprețuite cărora merită să le acordăm atenție.
În primul rând, până când veți obține un rezultat dezechilibrat de la o cântărire, nu veți avea suficiente informații pentru a determina dacă moneda specială este grea sau ușoară. Așa că trebuie să încerci să forțezi un rezultat dezechilibrat.
În al doilea rând, dacă obțineți un rezultat echilibrat (să spunem că moneda specială A echilibrează moneda B), puteți combina monedele care sunt echilibrate și le puteți cântări cu alte două monede, C și D. Dacă sunt dezechilibrate, aveți răspunsul; în caz contrar, acum ați dublat numărul de monede similare, ceea ce vă poate ajuta să obțineți un răspuns dezechilibrat în următoarea cântărire. De asemenea, puteți efectua acest proces invers cu un număr de monede care au puteri de doi (4, 8 etc.) dacă aveți un rezultat inițial dezechilibrat, așa cum se vede în soluția următoare.
Mai jos este întreaga procedură care poate identifica tipul monedei speciale A în toate cazurile în trei cântăriri. (B, C și D sunt trei monede plasate pe aceeași parte cu A în cântărirea 1 (W1); X și Y sunt cele două monede neutilizate în W1.)
Acest puzzle a fost inventat de matematicianul rus Konstantin Knop, o autoritate mondială în puzzle-uri de cântărire a monedelor. Multe dintre lucrările sale sunt în limba rusă, dar puteți găsi mai multe puzzle-uri cu monede (printre alte puzzle-uri interesante) pe blogul a colaboratorului său Tanya Khovanova.
În ceea ce privește generalizarea, vă las pe voi să vedeți dacă aceeași metodă funcționează pentru a găsi tipul unei monede speciale printre 32 de monede, dintre care 16 sunt grele și 16 sunt ușoare.
puzzle 5
Tu ai n monede cu aspect identic, dintre care unele sunt contrafăcute și mai ușoare decât celelalte. Tot ce știi este că există cel puțin o monedă contrafăcută și că sunt mai multe monede normale decât cele contrafăcute. Sarcina ta este să detectezi toate monedele contrafăcute.
Faptul că există cel puțin o monedă ușoară și că există mai multe monede normale decât cele ușoare face acest puzzle mai puțin complex decât pare la prima vedere, cel puțin pentru numere mici. Să ne uităm la numerele de cântăriri pentru una până la opt monede.
Pentru una și două monede, nu pot exista monede ușoare pentru a doua condiție, deci nu sunt necesare cântăriri.
Trei monede: o singură monedă ușoară. Este necesară o cântărire pentru fiecare puzzle 1.
Patru monede: o singură monedă ușoară. Este necesară o cântărire suplimentară, deci w = 2.
Cinci monede: una până la două monede ușoare. Acesta este primul caz interesant. Întrebarea este: ar trebui să cântărim o monedă împotriva uneia sau două monede împotriva a două?
Dacă cântărim unul împotriva unu, atunci putem avea:
- Două cântăriri dezechilibrate: Două monede descoperite; am terminat.
- O cântărire echilibrată din două: monedele echilibrate trebuie să fie normale, deci ultima monedă are nevoie de o altă cântărire, w = 3.
- Două cântăriri echilibrate: în a treia cântărire, cântăriți o monedă din fiecare cântărire anterioară față de alta. Dacă sunt echilibrate, toate cele patru sunt normale, iar moneda 5 este cea ușoară. Am terminat; w = 3 din nou. Dacă sunt dezechilibrate, am găsit cele două monede ușoare și am terminat cu trei cântăriri.
Dacă în schimb cântărim doi împotriva doi, mai avem nevoie de trei cântăriri, deoarece trebuie să facem distincție între posibilitățile ca monedele să fie diferite sau similare pe ambele părți. Cântăririle care utilizează un număr mic de monede grupate nu par să aibă niciun avantaj față de cântăririle cu monede individuale.
Aceasta se confirmă pentru:
Șase monede: una până la două monede ușoare; w = 4.
Șapte monede: una până la trei monede ușoare; w = 5.
Opt monede: una până la trei monede ușoare; w = 6. Această soluție are o structură simplă:
- Mai întâi faceți patru cântăriri a unei monede față de următoarea. Toate monedele sunt folosite.
- Cel mai rău caz: toate cele patru cântăriri sunt echilibrate (există două monede ușoare care se echilibrează reciproc).
- Următoarele două cântăriri: Cântăriți o monedă din cântărirea 1 față de o monedă din cântărirea 2; în mod similar, cântărește o monedă de 3 cu o monedă de 4.
- Una dintre aceste cantariri va fi dezechilibrata, identificandu-se cele doua monede usoare. Am terminat în șase cântăriri.
Ne pare rău, secvența noastră de 0, 0, 1, 2, 3, 4, 5, 6 nu este cu siguranță suficient de interesantă pentru a fi supusă Enciclopedia on-line a secvențelor întregi!
As Jonas Tøgersen Kjellstadli subliniat, soluția pare să fie w = n − 2 pentru numere mici, dar nu am demonstrat că acest lucru nu se va schimba pentru numere mai mari. La unii n, utilizarea mai multor cântăriri de monede ar putea începe mai bine sau mai multe cântăriri decât n − 2 poate fi necesar. Putem generaliza pur și simplu soluția pentru opt monede la toate puterile lui 2, dând n − 2 ca limită superioară a numărului de cântăriri pentru toate puterile lui 2.
Mark Pearson a discutat despre asemănarea acestei probleme cu codurile de corectare a erorilor și a sugerat utilizarea unei abordări a teoriei informațiilor bazată pe numărul de rezultate posibile. Folosind o astfel de abordare, Mike Roberts a postat o limită inferioară pentru cazul mai general, care Rainer aus dem Spring a derivat o aproximare pentru. Rainer a postat și un limită superioară dintr-o lucrare publicată, dar a remarcat că limitele nu sunt clare pentru scăzute n și, prin urmare, nu este de ajutor pentru numerele mici pe care le-am considerat mai sus. Astfel, pentru șapte monede, limitele citate oferă un interval de la 4 la 16, între care se află răspunsul nostru, 5. J. Payette oferă referințe matematice suplimentare și limite pentru toate puzzle-urile.
Mulțumesc tuturor celor care au participat. Premiul Insights pentru această lună îi revine în comun lui Ted și Rainer aus dem Spring. Felicitări!
Ne vedem data viitoare pentru noi Insights.
