Kezdőlap


Feladat:	C.406	Korcsoport: 16-17	Nehézségi fok: átlagos
Füzet:	1996/március, 149. oldal		PDF \| MathML
Témakör(ök):	Skatulyaelv, Oszthatósági feladatok, C gyakorlat
Hivatkozás(ok):	Feladatok: 1995/október: C.406

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.

Állítsuk sorba nagyság szerint az adott 100 pozitív egész számot, és jelöljük $a_{1}$ , $a_{2}$ , $a_{3}$ , $...$ , $a_{100}$ -zal. Jelölje $s_{i}$ ( $i = 1$ , 2, $...$ , 100) az első $i$ szám összegét:

\begin{matrix} \begin{matrix} s_{1} & = a_{1} \\ s_{2} & = a_{1} + a_{2} \\ s_{3} & = a_{1} + a_{2} + a_{3} \\ ⋮ \\ s_{100} & = a_{1} + a_{2} + ... + a_{100} . \end{matrix} \end{matrix}

Ha ezen 100 összeg mindegyikét 100-zal osztva különböző maradékot kapunk, akkor készen vagyunk. Ugyanis a 100-zal való osztásai maradék 100-féle lehet: 0, 1,

...

, 99, ezért a felsorolt összegek között kell legyen egy, amelyik 0-t ad maradékul, ami éppen azt jelenti, hogy ez az összeg osztható 100-zal.
Ha viszont nem mindegyik maradék különböző, akkor van közöttük legalább kettő, amelyik ugyanazt a maradékot adja; legyen ez

s_{j}

és

s_{i}

, ahol

j > i

, azaz

s_{j} > s_{i}

s_{j} = 100 k + a

s_{i} = 100 l + a

(

k

l \in {0, 1, 2,, ...}

).
Ekkor az

s_{j} - s_{i}

különbség,

\begin{matrix} (100 k + a) - (100 l + a) = 100 (k - l) \end{matrix}

osztható lesz 100-zal, és

s_{j} - s_{i} = a_{i + 1} + a_{i + 2} + ... + a_{j}