Kezdőlap


Feladat:	Gy.2425	Korcsoport: 16-17	Nehézségi fok: nehéz
Füzet:	1988/március, 114 - 115. oldal		PDF \| MathML
Témakör(ök):	Számhalmazok, Indirekt bizonyítási mód, Kombinatorika, Numerikus és grafikus módszerek, Maradékos osztás, Gyakorlat
Hivatkozás(ok):	Feladatok: 1987/szeptember: Gy.2425

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.

Hívjuk valós számok egy $11$ elemű $M$ halmazát jónak, ha teljesül rá a feladat feltétele, tehát az $M$ bármely tízelemű részhalmaza két, egyenként ötelemű csoportra osztható úgy, hogy a csoportokban egyenlő a számok összege.
A megoldás során felhasználjuk a jó halmazok alábbi tulajdonságait:

i) Egy jó halmaz minden egyes eleméhez ugyanazt a számot
adva ismét jó halmazhoz jutunk.

ii) Egy jó halmaz minden egyes elemét ugyanazzal a számmal
szorozva ismét jó halmazhoz jutunk.

iii) Egy egész számokból álló jó halmaz minden
egyes eleme ugyanazt a maradékot adja

2

-vel osztva.

Az első két tulajdonság nyilvánvaló. A harmadik bizonyításához jelölje a halmaz elemeinek összegét

S,

a halmaz tetszőleges elemét pedig

e

. A feltételből következik, hogy az

S - e

páros szám, és így az

e

ugyanazt a maradékot adja

2

-vel osztva, mint az

S

. Ez pedig éppen azt jelenti, hogy az

M

minden eleme ugyanazt a maradékot adja

2

-vel osztva.
Legyen ezután az

M

egy egész-elemű jó halmaz. Ha minden eleméhez hozzáadjuk az elemek minimumának az ellentettjét, akkor i) szerint ismét ‐ nem negatív egész elemű ‐ jó halmazhoz jutunk, ahol az elemek minimuma

0.

Ha belátjuk, hogy ebben az

M'

halmazban minden elem nulla, akkor készen vagyunk.
Tegyük fel, hogy ez nem igaz, tehát van olyan nem negatív egészekből álló jó halmaz, amelynek eleme a nulla, és van pozitív eleme is. Ekkor az ilyen "ellenpélda-halmazok'' között van olyan, amelynek legkisebb pozitív eleme minimális. Legyen az

M^{*}

egy ilyen jó halmaz és tekintsük az

M^{*}

elemeinek a felét. Ez a

11

szám ii) szerint ugyancsak jó halmazt alkot, elemei nemnegatív egészek ‐ hisz iii) szerint

M^{*}

minden eleme páros ‐ másfelől legkisebb pozitív eleme az

M^{*}

legkisebb pozitív elemének a fele és így annál kisebb. Ez viszont nem lehet, mert föltettük, hogy a pozitív elemek minimuma az

M^{*}

-ban a legkisebb.
A kapott ellentmondás azt jelenti, hogy nem létezhet az

M^{*}

halmaz, a feladat állítására nincsen ellenpélda, vagyis az

M'

halmazban valóban minden elem nulla.
Ezzel a bizonyítást befejeztük.

Megjegyzések. 1. A feladat állítása

11

helyett nyilván igaz tetszőleges páratlan számra.
2. Ha egy racionális számokból álló páratlan elemű jó halmaz elemeit megszorozzuk a nevezők egy többszörösével, akkor egész számokból álló páratlan elemű jó halmazt kapunk, így a feladat állítása racionális számokra is igaz.
3. Megmutatható, hogy a feladat állítása akkor is igaz, ha az

M

elemei valós számok.