Feladat: Gy.2865 Korcsoport: 16-17 Nehézségi fok: nehéz
Megoldó(k):  Bárász Mihály ,  Braun Gábor ,  Burcsi Péter ,  Elek Péter ,  Fekete Zsolt ,  Kovács Baldvin ,  Lakatos Roland ,  Pap Gyula ,  Ruzsa Gábor ,  Tóth Gábor Zsolt ,  Tóth Péter ,  Újváry-Menyhárt Mónika ,  Valkó Benedek 
Füzet: 1994/április, 192 - 193. oldal  PDF  |  MathML 
Témakör(ök): Konstruktív megoldási módszer, Szöveges feladatok, Gyakorlat
Hivatkozás(ok):Feladatok: 1993/október: Gy.2865

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.

Ha tekintjük a tanulók két olyan beküldését, amelyek csak sorrendjükben különböznek egymástól, akkor mindkettő végén ugyanazok a súlyok lesznek az egyes serpenyőkben. Egy súly végső helyzetét ugyanis az határozza meg, hogy hányszor került át az egyik serpenyőből a másikba, vagyis az, hogy a rajta szereplő tanulókból hányat küldtünk be, ez pedig független a sorrendtől.

Jellemezzünk minden beküldést a bal és jobb oldali serpenyőben végeredményképpen levő súlyok összegének különbségével, jelölje ezt s. Az előbbiek alapján ez független a tanulók beküldésének sorrendjétől. Kezdetben ez az s negatív, a feladat állításának igazolásához pedig olyan beküldést kéne mutatni, amelyre s poztív. Ehhez azt látjuk be, hogy az összes lehetséges beküldésre (úgy értve, hogy aki egyszer bement, nem jöhet ki; a csak sorrendjükben különböző beküldéseket egyszer számoljuk) összegezve ezeket az s számokat, nullát kapunk. Ez tényleg elegendő, hiszen ha minden helyzetre s0 volna, akkor mivel a kezdeti helyzetre s<0, az összeg is negatív lenne; van tehát olyan beküldés, amelyre s>0.

Minden egyes s szám a serpenyőben levő súlyok ±1 együtthatójú kombinációja, így az s-ek összege is a súlyok egész együtthatós kombinációja. Azt mutatjuk meg, hogy ez az együttható minden súly esetén 0. Válasszunk egy tetszőleges súlyt és egy nevet a rajta szereplők közül. Tekintsük a többi tanuló beküldésének lehetőségeit. Ezekből úgy kapjuk meg az összes beküldést, ha a különválasztott tanulót is hozzávesszük, azaz vagy beküldjük, vagy nem. E szempont alapján párokba osztva a beküldéseket, olyan párokat kapunk, amelyek egyikében a vizsgált súly a bal oldalon van, együtthatója a beküldés s értékében +1, míg a másikban -1. Az összegzést a párok szerinti csoportosításban végezve látható, hogy az s számok összege valóban 0. Ezzel tehát bebizonyítottuk az állítást.

Pap Gyula (Debrecen, Fazekas M. Gimn., I. o.t.) dolgozata alapján