Feladat: F.2607 Korcsoport: 16-17 Nehézségi fok: nehéz
Megoldó(k):  Benczúr A. ,  Bereczky Á. ,  Cynolter G. ,  Gács A. ,  Grallert Krisztina ,  Keleti T. ,  Majoros László ,  Pál G. ,  Szalay Gy. ,  Talata I. ,  Zaránd G. 
Füzet: 1987/május, 203 - 204. oldal  PDF  |  MathML 
Témakör(ök): Partíciós problémák, Szöveges feladatok, Feladat
Hivatkozás(ok):Feladatok: 1986/november: F.2607

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.

A kérdés összefügg a 2518. feladattal és a 2304. gyakorlattal. (Megoldásuk az 1986. évi januári, illetve májusi számunkban olvasható.) Az utóbbi megoldásához fűzött megjegyzésből kiderül, hogy a mindkét esetben alkalmazott "kiegyensúlyozó eljárás'' nem feltétlenül vezet eredményre. Tehát ha az adott számoknak mérősúlyokat feleltetünk meg, és ezeket nagyság szerint csökkenő sorrendben helyezzük egy két karú mérleg egy-egy serpenyőjébe, egyensúly esetén a bal oldaliba, egyébként pedig a könnyebbikbe téve a soron következőt, akkor a súlyok elfogytával nem minden esetben lesz egyensúlyban a két serpenyő.
Ha az eljárás "elakad'', azaz valamelyik serpenyőbe egy m tömegű súlyt felrakva itt túllépnénk a teljes tömeg felét, az 50 grammot, akkor eddigre mindkét serpenyőn legalább 50-(m-1)=51-m a súlyok együttes tömege, így legfeljebb 2m-2 tömegű súly nincs még a mérlegen. A serpenyőkben lévő tömeg másrészt nyilván legfeljebb 100-m, és így eddig az elakadásig legfeljebb

[100-mm]=[100m]-1
darab súlyt helyezhettünk el a mérlegen, hiszen a csökkenő sorrend miatt az eddig felhasznált súlyok mindegyike legalább m tömegű.
Így legalább 35-([100m]-1)=36-[100m]≧36-100m darab súlyt kell még elhelyeznünk, és ezek együttes tömege az elakadás tényéből kiolvasott első becslés szerint legfeljebb 2m-2. Pontosabban a "kritikus'', m tömegű súlytól eltekintve még legalább 35-100m darab súly jut legfeljebb m-2 gramm tömegre.
Minden súly tömege legalább 1, ezért 35-100m≦m-2, azaz m2-37m+100≧0. Figyelembe véve, hogy m egész, ez akkor és csak akkor teljesül, ha 35≦m vagy 2≧m.
Az m≧35 eset nem lehetséges, hiszen ekkor a csökkenő sorrend miatt az elakadás előtt már mindkét serpenyőben volna egy-egy legalább 35 grammos súly és a "kritikus'' m tömeggel együtt ezek összege legalább 3⋅35, ami nagyobb 100-nál.
m=1 tömegű súllyal viszont már nem akadhat el az eljárás, ilyenkor ugyanis egyesével haladva egyik serpenyőben sem léphetjük át az 50 grammos tömeget.
Elakadás tehát valójában csak az m=2 esetben lehetséges, láthatóan úgy, ha mindkét serpenyőben 49 grammnyi súly gyűlt össze, és megmaradt egy 2 grammos súly. (1 grammos súlyunk ilyenkor egyáltalán nincsen.) Ez elő is fordulhat, például úgy, ha 30 darab 3 grammos és 5 darab 2 grammos súlyunk van. Megmutatható, hogy ilyenkor a két serpenyőben lévő súlyoknak létezik egy-egy olyan részhalmaza, amelyek össztömegének eltérése éppen 1 gramm. Ezt a két részhalmazt kicserélve a serpenyők eltérése 2 lesz, ami a megmaradt súllyal kiegyensúlyozható. Mi azonban most egy másik utat választunk.
Ha nincsen 1 grammos súly, akkor a 2 grammos súlyok száma nyilván legalább öt (4⋅2+31⋅3>100). Tegyünk félre öt darabot a 2 grammos súlyok közül. Belátjuk, hogy a többi harminc súlynak létezik olyan részhalmaza, hogy az abban lévő súlyok együttes tömege 40 és 50 közé eső páros szám, és így a félretett 2 grammos súlyok felhasználásával 50 grammá egészíthető ki.
A megmaradó súlyok összege (90 gramm) és száma (30) is páros, így közöttük mind a páratlan, mind pedig a páros tömegű súlyok száma páros. Készítsünk tehát párokat a páratlan tömegű súlyokból és a páros tömegűekből is, és tekintsük az egyes párokba került súlyok összegét. Így 15 páros számot kapunk, mindegyikük legalább 4, összegük pedig 90. Megmutatjuk, hogy ezek között van néhány olyan, amelyek S összegére ‐ ami nyilván páros ‐ 40≦S≦50.
Legyen a 15 szám csökkenő sorrendben b1, b2, ..., b15 és jelölje Sk az első k darab összegét. Mivel b1≧4, ezért Sk=90-(bk+1+...+b15)≦90-(15-k)⋅4=30+4k, vagyis S5≦50. Ha S5≧40, akkor készen vagyunk.
Ha S5≦38, akkor S5≧5⋅b5 miatt b5≦385<8, így ha i≧5, akkor bi≦6.
Eszerint ha egy 40-nél kisebb számot ‐ S4 ‐ legfeljebb 6-osával növelve 90-ig ‐ S15 ‐ jutunk, akkor nem "ugorhatjuk át'' a [40,50] számközt, lesz tehát olyan k, amelyre 40≦Sk≦50. Ezzel a bizonyítást befejeztük.