Feladat: F.2585 Korcsoport: 18- Nehézségi fok: átlagos
Megoldó(k):  Bánkövi Johanna ,  Beke T. ,  Benczúr András [1983-1987] ,  Bereczky Á. ,  Bóna M. ,  Csott R. ,  Cynolter Gábor ,  Domokos M. ,  Grallert Krisztina ,  Hajdú G. ,  Illés L. ,  Jinda B. ,  Keletei T. ,  Kovács 555 T. ,  Pál G. ,  Pfandler P. ,  Pfening A. ,  Pogány P. ,  Ribényi Á. ,  Rimányi R. ,  Szalay Gy. ,  Talata I. ,  Vargay P. ,  Zaránd Gergely 
Füzet: 1987/február, 64 - 66. oldal  PDF  |  MathML 
Témakör(ök): Algoritmikus eljárások, Szöveges feladatok, Feladat
Hivatkozás(ok):Feladatok: 1986/május: F.2585

A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre.

I. megoldás. A 2500. feladat idézett megoldásában azt bizonyítottuk be, hogy ugyanilyen feltételek mellett 2k darab érme esetén k méréssel választ adhatunk a feladat kérdésére. Az érmék száma most nem 2-hatvány, ezért az ott leírt felezési eljárás közvetlenül nem alkalmazható.

 

Hívjuk érmék egy H halmazát vegyesnek, ha mindkét fajta, a könnyebb és nehezebb is előfordul benne. A 2500. feladat megoldásában azt használtuk fel, hogy ha érmék egy 2n elemű H csoportját két n elemű részre osztva a részek egyforma nehezek, akkor mindkét rész ugyanolyan típusú, mint a H, míg ha nincs egyensúly ‐ ekkor persze H vegyes ‐, akkor bárhogyan is osztjuk újabb két-két, egyenként n1 és n2 elemű csoportra a két n elemű részt (n1+n2=n), nem lehet, hogy mind az n1, mind pedig az n2 elemű részek egyforma súlyúak legyenek, hisz ekkor a teljes, n elemű csoportok összehasonlításakor is egyensúlyt kellett volna tapasztalnunk. Az n1 vagy pedig az n2 elemű részeket lemérve tehát mindenképpen lesz olyan H' és H'' csoportunk, hogy H' és H'' ugyanannyi ‐ n1 vagy n2 ‐ elemből áll, H' és H'' együttese vegyes, és azt is tudjuk, hogy H' és H'' közül melyik a könnyebbik. Erre a mérésre tetszés szerint választhatjuk az n1 vagy pedig az n2 elemű részeket, ha nincs egyensúly, akkor H' és H'' a két lemért csoport, ellenkező esetben pedig a megmaradó kettő. A 2500. feladat megoldásában n1=n2=n/2 volt, hiszen a vizsgált érmék száma az eljárás minden lépésében 2-hatvány volt, azaz felezhető.
A fentieket előrebocsátva, megadunk egy eljárást, amelynek révén 7 mérés elegendő a feladat kérdésének megválaszolásához. A 2500. feladat állítása szerint ennyi mérés még 27=128 érme esetén is elegendő, a látszólagos többletet arra használjuk, hogy az eljárás egy adott pontján az eredeti, 100 érméből álló csoporttal azonos típusú és immár 2-hatvány elemből álló részt állítsunk össze.
Jelölje a 100 érméből álló halmazt H100. Elsőre most is felezzük, azaz 50 ‐ 50 érmét hasonlítsunk össze. Ha egyensúly van, akkor mindkét 50-es csoport H100-zal azonos típusú és az egyikből 14 darabot a másikhoz téve 26=64 érméből álló, H100-zal azonos típusú halmazhoz jutunk. Ennek vizsgálatára éppen elegendő a még hátralevő 6 mérés.
Ha az első mérés után nincs egyensúly, akkor H100 természetesen vegyes, és így a két rész is az. Legyen most n1=18, ekkor n2=32, és osszuk mindkét 50-es csoportot egy-egy 18, illetve 32 elemű részre. Hasonlítsuk össze például a 18 elemű halmazokat. Ha ezek egyforma nehezek, akkor legyen H' és H'' a két nem mért, 32 elemű halmaz. H' és H'' közül most ismerjük a könnyebbiket, még 5 mérés van hátra. Így a 2500. feladat szerint felezve, az ötödik mérés után a kezünkben van egy könnyebb és egy nehezebb érme.
Ha viszont a két 18 elemű csoport különböző súlyú, akkor újabb, n1=2 és n2=16 választással az n1 vagy pedig az n2 elemű részek lemérése után ‐ és így 4 méréssel a befejezés előtt ‐ vagy egy-egy n1=16=24 elemű H' és H'' csoportunk van, vagy pedig egy-egy 2 elemű. Mindkét esetben tudjuk, hogy a két csoport közül melyik a könnyebb, így az első esetben még 4, a másodikban pedig 1 újabb mérés elegendő egy könnyebb és egy nehezebb érme kiválasztásához.
Láttuk tehát, hogy minden esetben elegendő legfeljebb 7 mérés a feladat kérdésének megválaszolásához.
 

II. megoldás. Az első megoldás módszerével általában is igazolhatjuk, hogy ha N≦2k, akkor N érme esetén legfeljebb k méréssel választ adhatunk a feladat kérdésére. Ehhez először belátjuk az alábbi (1) állítást:
(1) Ha H1 és H2 olyan n elemű (érmékből álló) halmazok, hogy n≦2k és H1-ről tudjuk, hogy könnyebb H2-nél, akkor a vegyes H1∪H2 halmazból legfeljebb k méréssel kiválasztható egy könnyebb és egy nehezebb érme. A bizonyítást a k-ra vonatkozó teljes indukcióval végezzük.
Ha k=0, akkor n=1, H1 és H2 egy-egy érméből áll, az állítás nyilvánvaló.
Legyen most k>0 és n≦2k. Ha n≦2k-1. is fennáll, akkor az indukciós feltevés szerint legfeljebb k-1 mérés is elegendő, így föltehető, hogy n>2k-1. Legyen most n1=2k-1, n2=n-n1 ‐ ekkor nyilván n2≦2k-1 ‐ és osszuk H1-et és H2-t az n1 és n2 elemű H1' és H1'', illetve H2' és H2'' részekre.
Mérjük meg ezután az n1 elemű H'1-t és H2'-t. Akár egyensúlyban vannak, akár nem, a mérés eredményeként egy-egy legfeljebb 2k-1 elemű halmazhoz jutunk, amelyek viszonyát ismerjük, így az indukciós feltevés szerint további, legfeljebb k-1 méréssel kiválaszthatunk egy könnyebb és egy nehezebb érmét. Ezzel az (1) állítás bizonyítását befejeztük.
Térjünk most rá az eredeti állítás bizonyítására. Ismét a k-ra vonatkozó teljes indukcióval okoskodunk. Ha k=0, akkor N=1, az állítás semmitmondó, k=1 esetén pedig N=2, ilyenkor 1 mérés nyilván elegendő. Legyen most k>1 és N≦2k. Az indukciós föltevés miatt N>2k-1 nyilván föltehető.
Ha az N páros, akkor felezzünk és hasonlítsuk össze a két, egyenként N/2≦2k-1 érméből álló halmazt. Ha egyensúly van, akkor a két rész ugyanolyan típusú, mint az eredeti N elemű halmaz, és az indukciós feltevés szerint bármelyikük legfeljebb (k-1) méréssel megvizsgálható. Ha pedig nincs egyensúly, akkor a kiindulási halmaz vegyes, a két, legfeljebb 2k-1 elemű rész viszonyát ismerjük, így az (1) állítás szerint legfeljebb k-1 méréssel kiválasztható egy könnyebb és egy nehezebb érme.
Ha az N páratlan, akkor nyilván N<2k. Tegyünk félre egy érmét, a maradékot pedig felezzük meg. Egy rész ilyenkor N1=N-12<2k-1 elemből áll. Ha a két részt megmérve nincs egyensúly, akkor az (1) állítás szerint egy könnyebb és egy nehezebb érme kiválasztása legfeljebb k-1 további méréssel lehetséges. Ha egyensúly van, akkor a két rész egyforma típusú és ha egyikükhöz hozzávesszük a félretett érmét, akkor ez az N1+1=N+12≦2k-1 érméből álló halmaz az eredeti, N eleművel lesz azonos típusú, másrészt az indukciós feltevés szerint legfeljebb k-1 további méréssel megvizsgálható.
Ezzel a bizonyítást befejeztük.
 

Megjegyzés. A II. megoldásból könnyű algoritmust kiolvasni a feladat megoldására. Ez N=100-ra némiképpen különbözik az I. megoldásban talált eljárástól, azt lehet mondani, hogy az első megoldás a lehető leghamarább, a második pedig a lehető legkésőbb egészíti ki 2 hatvánnyá a vizsgált érmék számát. A megoldást szolgáltató méréssorozat tehát általában nem egyértelmű ‐ bár 2k darab érmére valószínűleg az ‐, azonban könnyű utánagondolni, hogy a talált eljárások során, ha 2k<N≦2k+1, akkor a legrosszabb esetben mindig sor kerül k+1 mérésre. A fentiekből azonban nem következik, hogy ez a szám nem csökkenthető.