Rješenje problema lažne kovanice

Evo odgovora na problem 12 kovanica.

Razmislimo najprije o jednostavnijem problemu nalaženja jedne teže kovanice (dakle znamo da je teža) među 3 kovanice, u samo jednom vaganju.

Rješenje je očito. Stavimo po jednu kovanicu na svaku stranu vage, a treću ostavimo sa strane. Ako je vaga u ravnoteži, kovanica sa strane je tražena teža kovanica. Ako vaga nije u ravnoteži teža je ona kovanica koja preteže na vagi. (Istim postupkom možemo, u samo jednom vaganju, naći i jednu lakšu kovanicu među tri.)

Vratimo se sada problemu 12 kovanica. Podijelimo ih u tri grupe po 1+3 (vidjet ćemo da je korisno grupu od 4 podijeliti na 1+3). Po jednu (1+3)-grupu stavimo na svaku stranu vage, a treću (1+3)-grupu ostavimo sa strane. To je prvo vaganje.

Ako je vaga u ravnoteži, lažna je kovanica u (1+3)-grupi sa strane. Drugim vaganjem 3 iz te grupe testiramo tako da ih usporedimo s 3 prave kovanice.

Ako je vaga opet u ravnoteži, lažna je ona preostala 1 kovanica (iz lažne (1+3)-grupe). Trećim vaganjem odredimo je li ona teža ili lakša.

Ako vaga u drugom vaganju nije u ravnoteži, lažna je kovanica među 3 testirane. Ovisno o tome na koju stranu vaga sada preteže, lako odlučujemo je li među te 3 kovanice teža ili lakša. Budući da sada imamo 3 kovanice, od kojih je jedna teža ili lakša (i mi znamo koji je od ta dva slučaja nastupio), nalazimo se u uvjetima početnog jednostavnijeg problema. Dakle, još jednim (trećim) vaganjem lako nalazimo tu težu ili lakšu kovanicu.

Sve je to bilo pod pretpostavkom da su dvije (1+3)-grupe u prvom vaganju bile u ravnoteži. Što ako nisu? Tada je jedna (1+3)-grupa na vagi teža ili je pak ona druga lakša.

Drugo vaganje sada je malo složenije: 3 iz (1+3)-grupe koja je pretezala u prvom vaganju stavimo sa strane; na njeno mjesto stavimo 3 iz (1+3)-grupe koja nije pretezala u prvom vaganju; a na njeno ispražnjeno mjesto stavimo 3 iz (1+3)-grupe koja je u prvom vaganju bila sa strane.

Pokušajte si zamisliti tu cikličku zamjenu trojki. Sljedeća slika može biti od pomoći:

Ako vaga ovim drugim vaganjem dođe u ravnotežu, lažna je kovanica očito u trojki koju smo maknuli na stranu. Budući da je ona pretezala, imamo trojku u kojoj je teža kovanica. To je naš jednostavniji problem koji se rješava još jednim (trećim) vaganjem.

Ako vaga ovim drugim vaganjem (pogledajte još jednom sliku) ne dođe u ravnotežu, moguća su dva slučaja.

Prvi je slučaj da vaga „klecne“ na drugu stranu. No, to znači da se lakša kovanica nalazi u trojci koja je za drugo vaganje „ciklički“ prebačena na drugu stranu vage.Opet naš jednostavni slučaj koji rješavamo još jednim (trećim) vaganjem.

Drugi je slučaj da vaga u drugom vaganju ostane u istom položaju u kojem je bila nakon prvoga. No, to znači da u trojkama koje smo pomicali nema lažnih kovanica. Dakle, one su u nepomaknutim „jedinicama“. Što znamo o njima? Ili je ona na strani koja preteže teža ili je ona na strani koja ne preteže lakša. O kojem je slučaju riječ možemo odlučiti trećim vaganjem, tako da jednu od njih usporedimo  s pravom kovanicom.

Nije sasvim lako. Možda obrazloženje trebate pročitati još koji put.

Koga zanima kako se problem 39 kovanica može riješiti u 4 vaganja, a 120 kovanica u 5 vaganja, neka pogleda ovdje:

http://www.fsb.unizg.hr/matematika/download/ZS_problem_laznog_novcica.pdf

Tu je dokazano da se među 3(3⁰+3¹+…+3ⁿ) kovanica, koje sadrže 1 lažnu, ona može naći u n+2 vaganja. (Za n=1 imamo naš 3(1+3) = 12 slučaj.)

Nemojte odmah odustati. Netko će možda lakše pratiti taj općenitiji slučaj (to je čest slučaj u matematici).

Mislim da je za danas dosta. Rješenje problema „životinjskog carstva“ dati ću sljedećeg petka.

Oglasi