Kezdőlap


Feladat:	Gy.2304	Korcsoport: 16-17	Nehézségi fok: nehéz
Megoldó(k):	Argay M. , Bán E. , Bán G. , Baross Á. , Binder Zs. , Bobok G. , Boda I. , Bordás F. , Bukszár J. , Cser Z. , Dutkó A. , Fajszi B. , Fellegi I. , Fleiner T. , Hadnagy É. , Hídvégi Z. , Illés T. , Jenei J. , Jinda B. , Kálmán E. , Károlyi Gy. , Kecskés K. , Keleti T. , Kun A. , Lois L. , Mándy A. , Mátyás Á. , Molnár S. V. , Paál B. , Pásztor 625 G. , Péter K. , Szabó 522 B. , Szabó 668 T. , Tasi A. , Tavaszi G. , Tóth 121 T. , Tóth 781 Zs. , Vasy A. , Vida P. , Weisz Z. , Wekszli M. , Zöldi M.
Füzet:	1986/május, 215 - 217. oldal		PDF \| MathML
Témakör(ök):	Kombinatorika, Skatulyaelv, Gyakorlat
Hivatkozás(ok):	Feladatok: 1985/december: Gy.2304

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. Ha minden egyes kupacban 2 kavics van, akkor a feladat állítása nyilvánvaló, hisz 25‐25 kupacot egy-egy csoportba gyűjtve mindkét csoportban 50 kavics lesz.
Ha a kupacok között vannak különböző elemszámúak, akkor jelölje $a_{1}$ , $a_{2}$ $...$ , $a_{50}$ az egyes kupacokban levő kavicsok számát, és tegyük fel, hogy például $a_{1} \neq a_{2}$ .
Tekintsük ezután az alábbi 51 darab számot:

\begin{matrix} a_{1}, a_{2}, a_{1} + a_{2}, a_{1} + a_{2} + a_{3}, ..., a_{1} + a_{2} + ... + a_{50} . \end{matrix}

A fenti 51 szám között feltétlenül van kettő,

b_{1}

és

b_{2}

, amelyek ugyanazt a maradékot adják 50-nel osztva. Mivel a felsorolt számok különbözők

(a_{1} \neq a_{2} és a_{i} > 0)

, továbbá mindegyikük 1 és 100 között van, ez csak úgy lehetséges, ha

∣ b_{1} - b_{2} ∣ = 50

. Ez a két szám így nem az

a_{1}

és az

a_{2}

, hisz az

a_{i}

-k között nincs 50-nél nagyobb. A felsorolt 51 szám közül viszont bármely további kettőnek a különbsége különböző

a_{i}

-k összege. Ha pedig ilyen számok összege 50, akkor a megfelelő kupacokat egybegyűjtve a kapott csoportra ‐ és így a kimaradókból összegyűjtött másikra ‐ teljesül a feladat állítása.

II. megoldás. A feladat szoros rokonságban van a 2518. feladattal (a megoldást lásd az ez évi januári szám 5‐6. oldalán). Ha az egyes kupacoknak egy-egy mérősúlyt feleltetünk meg, amelyek tömege a kupacokban lévő kavicsok száma grammokban mérve, akkor a 2518. feladat szerint 50 helyett 51 súlyra igaz az állítás, sőt az ott megadott eljárás ‐ a súlyokat csökkenő sorrendben helyezzük el 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 ‐ elő is állítja az összesen 100 grammnyi tömeg két egyenlő részre történő felosztását.
Megmutatjuk, hogy ezzel a "kiegyensúlyozó'' eljárással még 50 darab súly esetén is egyensúlyban lesz a mérleg a végén, ami bizonyítja a kívánt felosztás létezését. A bizonyítás során föltehető, hogy a súlyok nem mind egyenlők ‐ egyébként az állítás nyilvánvaló.
A megoldás annak idején azon múlott, hogy 51 súly esetén az 1 grammosnál nagyobb tömegű súlyok felrakása után a serpenyők közti különbség nem haladta meg az 1 grammos súlyok együttes tömegét. Hívjuk ezt a tényt "1-grammos feltételnek''. A 2518. feladat megoldásában láttuk, hogy ha ez teljesül, akkor a "kiegyensúlyozó'' eljárás végén a mérleg egyensúlyban lesz. Megmutatjuk, hogy most is teljesül az 1 grammos feltétel.
Jelölje ismét

M

a szereplő tömegek maximumát,

d_{1}

1, d_{2}

pedig a

2

gramm tömegű súlyok számát. Mivel a súlyok nem mind egyenlők,

M > 2

és

d_{1} > 0

(

d_{2} = 0

lehetséges), így

50 - 1 - d_{1}

darab legalább 2 gramm tömegű súly van. A tömegek összegére így kapjuk, hogy

\begin{matrix} 100 ≧ M + d_{1} + 2 (49 - d_{1}), \end{matrix}

(1)

ahonnan

\begin{matrix} d_{1} + 2 ≧ M \end{matrix}

adódik.
Ha

d_{2} > 0

, azaz a súlyok között van 2 grammos, akkor

d_{1} + 2 ≦ d_{1} + 2 d_{2}

, azaz az 1 és 2 grammos súlyok együttes tömege legalább akkora, mint a szereplő tömegek maximuma. Mivel a kiegyensúlyozó eljárást követve a serpenyők eltérése sosem lehet

M

-nél nagyobb,

d_{2} > 0

esetén teljesül az 1 grammos feltétel "2 grammos'' változata, azaz a 2 grammnál nehezebb súlyok fölrakása után a serpenyők

E

eltérése legfeljebb annyi, mint a föl nem rakott súlyok együttes tömege,

d_{1} + 2 d_{2}

. Megmutatjuk, hogy ekkor fennáll az 1-grammos feltétel is.
Valóban, ha az

E

eltérés nagyobb, mint

2 d_{2}

, akkor ezután az eljárás szerint valamennyi 2 grammos súly a könnyebbik serpenyőbe kerül, és ekkor a serpenyők közti eltérés nem nagyobb, mint

d_{1}

. Ha pedig

E

nem nagyobb mint

2 d_{2}

, akkor az eljárás szerint elhelyezve a 2 grammos súlyokat, a serpenyők eltérése 0, 1 vagy 2 lesz. Az első két esetben

d_{1} > 0

miatt ismét igaz az 1 grammos feltétel, ha pedig éppen 2 az eltérés, akkor mivel a mérlegen levő súlyok együttes tömege páros,

d_{1}

is az (a súlyok összege 100 volt) és így

d_{1} > 0

miatt

d_{1} ≧ 2

d_{2} > 0

esetben tehát valóban teljesül az 1 grammos feltétel.
Ha

d_{2} = 0

, azaz nincsen 2 grammos súly, akkor (1) igaz marad, ha jobb oldalán a 2-es szorzót 3-mal helyettesítjük (ekkor minden 1 grammnál nehezebb súly legalább 3 grammos), ahonnan rendezés után kapjuk, hogy

\begin{matrix} 2 d_{1} ≧ M + 47. \end{matrix}

(2)

Ha itt most

M ≦ d_{1}

, akkor nyilván igaz az 1 grammos feltétel. Ha

M > d_{1}

, akkor (2)-ből

d_{1} > 47

, azaz

M ≧ 49

, ami

M ≦ 50

és

d_{2} = 0

mellett csak úgy lehet, ha 48 darab 1 grammos, egy 3 grammos és egy 49 grammos súlyunk van, ekkor pedig látható, hogy teljesül az 1 grammos feltétel.
Beláttuk tehát, hogy minden esetben teljesül az 1 grammos feltétel és ez azt jelenti, hogy a kiegyensúlyozó eljárás végén a mérleg egyensúlyban lesz, a keresett felosztás tehát valóban létezik.

Megjegyzések. 1. A második megoldás nyilván nem vetekszik az első eleganciájával. Gondolatmenetének némi módosításával azonban a kitűzöttnél lényegesen erősebb állítás igazolható: ha 35 darab súly mindegyikének tömege egész szám, a súlyok egyike sem nehezebb 50 grammnál, együttes tömegük pedig 100 gramm, akkor a súlyok két egyenlő tömegű csoportra oszthatók. (Az első megoldás módszerével reménytelennek tűnik ennek az állításnak a bizonyítása.)
Ez az alsó korlát a súlyok számára már éles. Ha 34 súly közül 33 darab 3 grammos, a 34-edik pedig 1 grammos, akkor bárhogyan osztjuk két csoportba a súlyokat, az egyik tömeg osztható lesz 3-mal, a másik pedig nem, így nem lehetnek egyenlők.
2. Az már 50-nél kevesebb súlyra nem igaz, hogy a kiegyensúlyozó eljárás mindig előállít egy keresett felosztást. Ha például 49 súly közül kettő 3 grammos, 47 pedig 2 grammos, akkor az eljárás végén az egyik serpenyőben 51, a másikban pedig 49 gramm lesz a súlyok együttes tömege, holott egyenlő felosztás nyilván létezik

(2 \cdot 3 + 22 \cdot 2 = 25 \cdot 2 = 50)