Kezdőlap


Feladat:	N.140	Korcsoport: 18-	Nehézségi fok: nehéz
Megoldó(k):	Kun Gábor
Füzet:	1998/január, 35. oldal		PDF \| MathML
Témakör(ök):	Indirekt bizonyítási mód, Kombinációk, Nehéz feladat
Hivatkozás(ok):	Feladatok: 1997/május: N.140

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.

Tegyük fel, hogy az állítással ellentétben $a_{9} \leq 100$ .
Legyen $S$ azoknak a legfeljebb öttagú összegeknek a halmaza, amelyek az $a_{1}$ , $a_{2}$ , $...$ , $a_{8}$ számokból készíthetők, és nem kisebbek $a_{4}$ -nél. A legfeljebb öttagú összegek száma $(\binom{8}{1}) + ... + (\binom{8}{5}) = 218$ , ezek közül azok lehetnek kisebbek $a_{4}$ -nél, amelyekben csak $a_{1}$ , $a_{2}$ vagy $a_{3}$ szerepel, összesen 7 darab. Tehát $| S | \geq 211$ .
A legnagyobb összeg $a_{4} + a_{5} + a_{6} + a_{7} + a_{8} < a_{4} + 4 a_{9}$ , ezért mindegyik összeg az $I = [a_{4}; a_{4} + 4 a_{9} - 1]$ intervallumba esik. Az $| S | > 2 a_{9}$ egyenlőtlenség alapján $S$ -nek létezik három olyan eleme, amelyek $a_{9}$ -cel osztva ugyanazt a maradékot adják. Mivel azonban $I$ bármely két elemének különbsége kisebb $4 a_{9}$ -nél, a három elem közül kettő különbsége pontosan $a_{9}$ . Ez azonban ellentmondás, mert a kisebbik összeghez $a_{9}$ -et adva a nagyobbikat kapjuk.

Kun Gábor (Budapest, Piarista Gimn., III. o.)

Megjegyzések. 1. Egy kis számolással ellenőrizhető, hogy az

a_{1}

a_{2}

...

a_{9}

számokból legalább 376 darab olyan összeg készíthető, amely biztosan

a_{1} + a_{4} + a_{5}

és

a_{1} + a_{4} + a_{5} + a_{7} + a_{8} + a_{9}

közé esik. Ebből azonnal következik, hogy

a_{7} + a_{8} + a_{9} \geq 375

és

a_{9} \geq 126

. Ez az eredmény még mindig messze van a lehetséges legjobbtól.
2. Többféle módszerrel, például az előző pontbeli ötlet általánosításával igazolható, hogy ha az

a_{1}

a_{2}

...

a_{9}

számokból készíthető összegek mind különbözők, akkor

a_{n} > c \frac{2^{n}}{\sqrt[]{n}}

. Az is könnyen látható, hogy a 2-hatványok sorozatára teljesül a feltétel.
Erdős Pál azt sejtette, hogy megfelelő pozitív

c

konstanssal

a_{n} > c 2^{n}

. Ennek bizonyításáért vagy megcáfolásáért 300 dollárt ajánlott fel. A probléma jelenleg még megoldásra vár.