Feladat: F.2500 Korcsoport: 16-17 Nehézségi fok: nehéz
Füzet: 1985/december, 441 - 442. oldal  PDF file
Témakör(ök): Algoritmikus eljárások, Szöveges feladatok, Feladat
Hivatkozás(ok):Feladatok: 1984/december: F.2500

2k érme között nincs három különböző súlyú. Egy kétkarú mérlegen súlyok használata nélkül k méréssel meg kell mondanunk, hogy van-e köztük két különböző súlyú, és ha van, kell mutatni egy könnyebbet és egy nehezebbet. Bizonyítsuk be, hogy ez lehetséges, és mutassuk meg, hogyan.

Megadunk egy eljárást, amellyel k mérés után el tudjuk dönteni, vannak-e különböző súlyú érmék, és ez utóbbi esetben ki is tudunk jelölni majd egy könnyebbet és egy nehezebbet.
Osszuk el az érméket két egyenlő számú csoportra, és tegyük a két részt a két serpenyőbe. Ha a mérleg egyensúlyban van, akkor az egyik részt tegyük félre, a másikkal pedig ismételjük meg az eljárást, azaz ismét felezzük meg és hasonlítsuk össze a két részt. Folytassuk ezt mindaddig, amíg a mérleg ki nem billen.
Ha erre a k-adik mérésben sem kerül sor, akkor ‐ mivel az érmék száma minden lépésben feleződik ‐ az utolsó, k-adik mérésre 2 érme bizonyult egyenlő súlyúnak.
Azt állítjuk, hogy ebben az esetben az egymás után félretett csoportokban is minden érme egyenlő súlyú.
A k-adik felezés és összehasonlítás után a serpenyőkben 1-1 db érme van és a terhelések egyenlők : e=e, a vizsgálat alatt álló súly együttvéve 2e. Ennélfogva a (k-1)-edik mérésben 2e=2e volt fenn a mérlegen, együttvéve 22e,..., Ugyanígy visszafelé haladva az 1. mérésben 2k-1e+2k-1e=2ke, akkor pedig az összes érme fent volt. Nem lehetett tehát e-nél kisebb súlyú, mert akkor e-nél nagyobbnak is kellett volna lennie, ezt pedig a szöveg kizárta.
Ha az l-edik mérésben a mérleg kibillen és éppen l=k, akkor eddigre a serpenyőkben már csak 1-1 érme van, kezünkben van tehát egy könnyebbik és egy nehezebbik érme.
Ha l<k, akkor az l+1-edik méréstől kezdve módosítjuk eljárásunkat. Legyen ekkor ‐ mondjuk ‐ a bal oldali serpenyőben levő 2k-l darab érme nehezebb a jobb oldali serpenyőben levő ugyanennyi érménél. Ebben az esetben vannak különböző súlyú érmék, sőt a bal oldalon több van a nehezebbik, a jobb oldalon pedig a könnyebbik fajtából.
Egy könnyebb és egy nehezebb érmét akarunk tehát kiválasztani a még hátralevő k-l mérés alapján. Ezután is felezünk majd, de most külön-külön tesszük ezt az egyes serpenyők tartalmával.
Belátjuk, hogy innen kezdve minden lépés után tudunk mutatni két olyan csoportot, amelyben ugyanannyi érme van, súlyuk viszont különböző.
Osszuk tehát a bal és a jobb oldali serpenyő tartalmát a két-két egyenlő számú érméből álló B1 és B2, illetve J1 és J2 részekre, majd hasonlítsuk össze B1-et és J1-et egy méréssel. Ha továbbra is a bal oldali serpenyő bizonyul nehezebbnek, akkor B1-gyel és J1-gyel folytatjuk ezt az eljárást tovább. Ha egyensúly van, vagy J1 nehezebb B1-nél, akkor J2 biztosan könnyebb B2-nél. Ekkor tegyük félre J1-et és B1-et, a részenkénti felezést pedig a nehezebb B2-vel és a könnyebb J2-vel folytassuk tovább.
Ezen a módon továbbra is mérésenként felére csökken az összemérendő részekben levő érmék száma, és mind a serpenyők tartalmának, mind pedig az éppen félretett részeknek ismerjük a viszonyát. (A két-két halom közül legalább az egyik esetben nincs egyensúly, nem veszítjük tehát szem elől a különböző súlyú érméket.)
A k-adik méréssel most is egy-egy érmét hasonlítunk össze. Ha nincs egyensúly, akkor ez a két érme szolgáltatja a választ, ellenkező esetben pedig a fentiek szerint az utolsó felezéskor levett egy-egy érme.