Kezdőlap


Feladat:	2000. évi Nemzetközi Matematika Diákolimpia 21. feladata	Korcsoport: 18-	Nehézségi fok: nehéz
Megoldó(k):	Vizer Máté
Füzet:	2000/október, 389 - 390. oldal		PDF \| MathML
Témakör(ök):	Oszthatósági feladatok, Konstruktív megoldási módszer, Szöveges feladatok, Nemzetközi Matematikai Diákolimpia
Hivatkozás(ok):	Feladatok: 2000/szeptember: 2000. évi Nemzetközi Matematika Diákolimpia 21. feladata

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 három doboz $A$ , $B$ és $C$ .

\begin{matrix} \begin{matrix} A & = {a_{1} < a_{2} < ... < a_{k}}, \\ B & = {b_{1} < b_{2} < ... < b_{l}}, \\ C & = {c_{1} < c_{2} < ... < c_{m}}, (k + l + m = 100) . \end{matrix} \end{matrix}

Vegyük a következő összegeket:

\begin{matrix} \begin{matrix} {a_{1} + b_{1} < a_{1} + b_{2} < ... < a_{1} + b_{l} < a_{2} + b_{l} < ... < a_{k} + b_{l}} \\ {a_{1} + c_{1} < a_{1} + c_{2} < ... < a_{1} + c_{m} < a_{2} + c_{m} < ... < a_{k} + c_{m}} \\ {b_{1} + c_{1} < b_{1} + c_{2} < ... < b_{1} + c_{m} < b_{2} + c_{m} < ... < b_{l} + c_{m}} \end{matrix} \end{matrix}

(az egyenlőtlenségek az eredeti egyenlőtlenségekből következnek).
Mivel két csoportban nem lehet ugyanolyan összeg, azért van

k + l - 1 + k + m - 1 + l + m - 1 = 2 (k + l + m) - 3 = 197

különböző számunk. Az 1‐100 számokból éppen ennyi, 197 különböző kéttagú összeg készíthető (

1 + 2 = 3

...

99 + 100 = 199

), ezért az összes szám szerepel. Ezután esetvizsgálattal nézzük meg a lehetőségeket:
Kezdjük feltölteni a dobozokat. Vegyük észre, hogy mivel a 3 összeg létrejön, az 1 és a 2 kártya különböző dobozokba kerül. Ezt a két kártyát összesen hatféleképpen rendezhetjük el. Tegyük fel, hogy az 1 kártya az

A

, a 2 pedig a

B

dobozba került. A 3 kártya ezután nem kerülhet az

A

dobozba, ellenkező esetben ugyanis a 4 összeg nem jöhet létre. A 3 kártya tehát vagy a

B

dobozba került ‐ ahová a 2 ‐ vagy pedig az eddigi üres

C

dobozba. Azt állítjuk, hogy a további kártyák elhelyezése mindkét esetben egyértelmű.
1. eset (a 3 kártya a

B

dobozba kerül):

*	$•$ a $C$ doboz nem üres, így legyen a legkisebb $C$ -beli kártya $k$ . Ekkor $k + 1$ csak az $A$ -ba kerülhet, hiszen különben $2 + k = (k + 1) + 1$ , a bűvész nem tud dönteni.

Ám ekkor

(k + 1) + 2 = k + 3

, a bűvész most sem tud dönteni, hacsak

k + 1

kártya már egyáltalán nincsen. Így ,,nem létezhet''

k + 1

, tehát

k = 100

. Ekkor az

A

és

C

dobozban egy-egy kártya van, az 1, illetve a 100, a többiek a

B

dobozba kerülnek. Ez az elrendezés pedig nyilván megfelelő, így tehát hat esetet kaptunk.
2. eset (a 3 kártya a

C

dobozba kerül):

*	$•$ $2 + 3 = 4 + 1$ , $4 \in A$

5 + 1 = 4 + 2

tehát

5 \notin C

, és

5 + 2 = 4 + 3

, tehát

5 \notin A

. Így

5 \in B

. Hasonlóan

6 + 1 = 4 + 3

, így

6 \notin B

, továbbá

6 + 2 = 5 + 3

, azért

6 \notin A

. Így csak

6 \in C

lehetséges.
Az első sort elhagyva ezt ,,eljátszva'' a második sorral kapjuk, hogy a számok 3-as maradék szerint vannak rendezve, és ez az elrendezés is tényleg jó lesz. Ez tehát további hat eset.
Így összesen 12 olyan elrendezés van, amikor mindig sikerülhet a mutatvány.

Vizer Máté (Fazekas M. Főv. Gyak. Gimn., 12. o.t.)