Kezdőlap


Feladat:	Pontversenyen kívüli P.126	Korcsoport: 16-17	Nehézségi fok: nehéz
Megoldó(k):	Bálint L. , Balogh Z. , Banai M. , Bara T. , Bartolits I. , Boros P. , Füredi Z. , Gergely I. , Hermann P. , Kelen M. , Kollár István , Nagy S. , Neumann A. , Reviczky J. , Szász Gy. , Székely A. , Szeredi J. , Totik V. , Ujfalussy M. , Wéber J.
Füzet:	1973/március, 118 - 119. oldal		PDF \| MathML
Témakör(ök):	Skatulyaelv, Természetes számok, Pontversenyen kívüli probléma
Hivatkozás(ok):	Feladatok: 1972/január: Pontversenyen kívüli P.126

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.

Legyen a kiválasztott számok száma $k$ , és maguk a számok $a_{1}$ , $a_{2}$ , $...$ , $a_{k}$ , úgy választva az indexeket, hogy

\begin{matrix} 1 ≦ a_{1} < a_{2} < ... < a_{k} ≦ n - 1, ahol & (1) \\ k > \frac{n + 1}{2}, & (2) \end{matrix}

és vegyük hozzájuk azt a

(k - 1)

számot, amennyivel legnagyobbikuk meghaladja rendre az előzők mindegyikét:

\begin{matrix} a_{k} - a_{1}, a_{k} - a_{2}, ..., a_{k} - a_{k - 1}, \end{matrix}

(3)

ekkor az előttünk álló számok száma (2) alapján

\begin{matrix} k + (k - 1) = 2 k - 1 > n . \end{matrix}

(4)

Az új számokra (1) alapján

\begin{matrix} n - 1 > a_{k} - a_{1} > a_{k} - a_{2} > ... > a_{k} - a_{k - 1} ≧ 1, \end{matrix}

és ezek is egészek, tehát ezek is a kiválasztásra megengedett számok közül valók. Mivel (4) szerint az (1) és (3) alatt felsorolt számok száma legalább 2-vel nagyobb, mint a megengedett számok

(n - 1)

száma, azért (1) és (3) alatt legalább két olyan szám van, amely kétszer szerepel. És mivel külön‐külön (1) is (3) is csupa különböző számot tartalmaz, ez csak úgy lehet, ha egy (1)-beli szám egyenlő egy (3)-beli számmal, mondjuk

\begin{matrix} a_{i} = a_{k} - a_{j}, ahol 1 ≦ i, j ≦ k - 1, \end{matrix}

ekkor tehát

\begin{matrix} a_{i} + a_{j} = a_{k}, \end{matrix}

vagyis teljesül az állítás, hacsak

i \neq j

.
Amennyiben pedig történetesen

i = j

lenne, vagyis

a_{k} = 2 a_{i}

, akkor még mindig vehetjük (1) és (3) másik közös számát:

\begin{matrix} a_{m} = a_{k} - a_{r}, ahol m \neq i, 1 ≦ m, r ≦ k - 1, \end{matrix}

ahol már

m \neq r

és

a_{m} + a_{r} = a_{k}

. Az állítást bebizonyítottuk.