Moneda mai ușoară: cântăriri cu balanța

Pentru a găsi o monedă sigur mai ușoară cu o balanță, împarți monedele suspecte în trei grupuri și compari două grupuri de aceeași mărime. Dacă balanța se echilibrează, moneda este în grupul nepus pe talere. Dacă nu, ea este în grupul de pe talerul mai ușor.

Metoda folosește trei rezultate posibile ale unei cântăriri: stânga mai ușoară, dreapta mai ușoară sau echilibru. Pentru opt monede, dintre care exact una este mai ușoară, două cântăriri sunt suficiente dacă alegi grupurile potrivite.

Ce presupuneri sunt obligatorii?

Toate monedele normale au aceeași masă. Există exact o monedă diferită și știi dinainte că aceasta este mai ușoară. Balanța este ideală: arată comparația maselor, fără erori și fără să ofere valori numerice.

Nu știm cu câte grame diferă moneda. Tocmai de aceea comparăm pe talere același număr de monede. Dacă ai pune patru monede pe un taler și trei pe celălalt, diferența ar putea veni pur și simplu din numărul lor, fără să localizeze moneda căutată.

Cerința este să garantezi identificarea în cel mai rău caz. O încercare norocoasă, în care compari două monede și găsești imediat moneda mai ușoară, nu dovedește că strategia rezolvă orice configurație la fel de repede.

Cum rezolvi cazul cu trei monede?

Numește monedele A, B și C. Compară A cu B. Dacă A este mai ușoară, ai găsit moneda. Dacă B este mai ușoară, ea este cea căutată. Dacă se echilibrează, C este diferită.

Ai folosit o singură cântărire și ai tratat toate cele trei rezultate. Moneda C poate fi identificată fără să o pui pe balanță, deoarece știi că există exact o monedă mai ușoară și le-ai exclus pe celelalte două.

Dacă enunțul ar spune „poate exista o monedă mai ușoară”, echilibrul dintre A și B nu ar demonstra că C este diferită. Ar putea fi toate normale. Schimbarea unui singur cuvânt din ipoteză schimbă concluzia permisă.

Cum rezolvi opt monede în două cântăriri?

Împarte monedele în grupurile A, B și C, cu trei, trei și două monede. La prima cântărire compară grupul A cu grupul B.

Dacă A este mai ușor, moneda căutată se află printre cele trei din A. Compari două dintre ele, iar a treia este identificată dacă acestea se echilibrează. Dacă B este mai ușor, procedezi la fel în B.

Dacă prima cântărire arată echilibru, moneda se află între cele două din C. Le compari direct și alegi moneda de pe talerul mai ușor. În acest caz, echilibrul la a doua cântărire nu este compatibil cu ipotezele problemei.

Toate ramurile se încheie după cel mult două cântăriri. Nu este nevoie ca toate grupurile să aibă aceeași mărime, dar cele două puse simultan pe talere trebuie să aibă același număr de monede.

De ce împărțirea în două grupuri poate fi mai slabă?

Dacă împarți cele opt monede în două grupuri de patru și le compari, balanța nu se poate echilibra: moneda mai ușoară este obligatoriu pe unul dintre talere. Vei afla grupul de patru care o conține.

Mai ai însă patru candidate și o singură cântărire. Cu trei rezultate posibile, o singură comparație nu poate identifica în mod garantat una dintre patru monede. Ai folosit prima cântărire cu numai două rezultate informative, deși balanța permitea trei.

Aceasta nu înseamnă că împărțirea în jumătăți este greșită în orice problemă de căutare. Aici instrumentul oferă trei categorii de răspuns. Strategia trebuie adaptată informației pe care o primești efectiv.

Cum arăți că două cântăriri nu ajung pentru zece monede?

După prima cântărire poți urma cel mult trei ramuri. După a doua, fiecare ramură se poate împărți în cel mult alte trei. Ai astfel cel mult nouă succesiuni distincte de rezultate.

Pentru a identifica zece monede posibile, fiecare trebuie să conducă la o concluzie distinctă. Dacă există doar nouă rezultate finale posibile, cel puțin două monede ar rămâne indistincte pe aceeași ramură. Nu poți garanta identificarea în două cântăriri.

Această argumentare oferă o limită inferioară: pentru zece monede ai nevoie de cel puțin trei cântăriri. Mai trebuie să construiești o strategie în trei pentru a demonstra că trei este și numărul suficient.

Separarea dintre „nu se poate mai puțin” și „există o metodă” este utilă în învățarea prin înțelegere. O formulă de numărare a rezultatelor nu înlocuiește automat descrierea cântăririlor.

Cum găsești moneda dintre zece în trei cântăriri?

Compară trei monede cu alte trei și lasă patru deoparte. Dacă un taler este mai ușor, ai rămas cu trei candidate, care se rezolvă printr-o singură cântărire suplimentară.

Dacă prima comparație se echilibrează, moneda este între cele patru lăsate deoparte. Compară una cu alta. Dacă diferă, ai identificat-o. Dacă se echilibrează, rămân două monede, pe care le compari la a treia cântărire.

În unele ramuri termini după două cântăriri, în altele după trei. Numărul garantat al strategiei este trei, adică lungimea celei mai lungi ramuri, nu media dintre ramuri și nici cel mai favorabil caz.

Nu trebuie să presupui probabilități egale pentru a rezolva această cerință. Întrebarea despre numărul mediu de cântăriri ar fi alta și ar necesita o distribuție a cazurilor sau o convenție explicită.

Cum funcționează aceeași idee pentru 27 de monede?

Împarte monedele în trei grupuri de câte nouă și compară două grupuri. Rezultatul identifică grupul de nouă care conține moneda mai ușoară. Îl împarți apoi în trei grupuri de câte trei.

A doua cântărire identifică grupul de trei. A treia identifică moneda, prin comparația a două dintre cele trei candidate. Fiecare etapă reduce numărul posibilităților de trei ori.

Cu k cântăriri există cel mult $3^k$ succesiuni de rezultate. Pentru exact $3^k$ monede, împărțirea repetată în trei grupuri egale atinge această limită. Exemplele sunt trei monede într-o cântărire, nouă în două și 27 în trei.

Calculează puterile înainte de a compara o țintă cu această limită. Dacă te încurcă notația, poți folosi ordinea operațiilor pentru a separa exponentul de o simplă înmulțire. Trei la puterea a patra este 81, nu 12.

Ce se schimbă dacă nu știi dacă moneda este mai ușoară?

Nu mai poți interpreta un taler mai ușor drept dovadă că moneda diferită se află acolo. Ar putea exista o monedă prea grea pe celălalt taler. Același rezultat ar corespunde unor ipoteze diferite.

Problema devine una nouă, cu alte strategii și alte limite. Nu transfera automat soluția cu trei grupuri fără să urmărești toate posibilitățile. În articolul de față, informația „sigur mai ușoară” este folosită la fiecare ramură.

Nici două monede diferite nu respectă modelul. Dacă una este pe fiecare taler, efectele se pot compensa sau pot produce alt rezultat. Înainte să judeci o strategie, verifică dacă ipotezele ei coincid cu enunțul.

Cum îți verifici arborele de decizie?

Scrie sub fiecare rezultat lista monedelor care mai pot fi căutate. După o cântărire, listele pentru ramurile posibile trebuie să fie disjuncte și să acopere toate candidatele inițiale. Nu pierde monede în desen și nu declara aceeași monedă în două ramuri incompatibile.

La final, fiecare ramură admisibilă trebuie să conțină o singură candidată. Poți verifica strategia imaginând pe rând că fiecare monedă este cea mai ușoară și urmărind răspunsurile balanței.

Un astfel de desen este potrivit pentru o discuție cu un profesor din anunțurile pentru meditații la matematică: arată unde rămân prea multe candidate și verifică dacă ai folosit toate rezultatele disponibile.

Exerciții cu răspunsuri explicate

1. Poți identifica una dintre patru monede într-o singură cântărire? Nu, deoarece ai cel mult trei rezultate.
2. Câte monede din modelul analizat pot fi tratate prin patru împărțiri succesive în trei? 81.
3. Ai șase monede. Compari două cu două. După prima cântărire rămân două candidate, indiferent de rezultat, deci încă o comparație este suficientă.
4. Ai nouă monede, dar compari patru cu patru. În ramura dezechilibrată rămân patru candidate, prea multe pentru o singură cântărire finală.

Întrebări frecvente

Pot afla moneda fără să o cântăresc direct?

Da, prin eliminare, dacă ipotezele spun că există exact una și toate celelalte au fost excluse.

Unde pot explora limita de trei rezultate?

NRICH analizează identificarea unei monede diferite, într-o variantă cu moneda sigur mai grea. Aici direcția diferenței este inversată, iar strategiile pentru opt și zece monede sunt dezvoltate separat.