Kezdőlap


Feladat:	1990. évi Nemzetközi Matematika Diákolimpia 12. feladata	Korcsoport: 16-17	Nehézségi fok: nehéz
Megoldó(k):	Balog József
Füzet:	1990/november, 338 - 339. oldal		PDF \| MathML
Témakör(ök):	Konstruktív megoldási módszer, Maradékosztályok, Nemzetközi Matematikai Diákolimpia
Hivatkozás(ok):	Feladatok: 1990/szeptember: 1990. évi Nemzetközi Matematika Diákolimpia 12. 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.

Kétségkívül ez a feladat volt az első versenynap legkönnyebb feladata, főleg azok számára, akik nem szeretik a geometriát. Ugyanis a megoldás folyamán csupa ,,természetes'' ötletet kell csak felhasználni, tulajdonképpen józan ész elegendő hozzá.
Legyenek a pontok nevei rendre $A_{1}$ , $A_{2}$ , $...$ , $A_{2 n - 1}$ . (Ha valamilyen $A_{i}$ -t említünk, amelyre $i \geq 2 n$ , vagy $i \leq 0$ , akkor az $i$ modulo $(2 n - 1)$ értendő.)
Könnyen kialakulhat az a sejtésünk, hogy $n$ -től függően $n - 1$ vagy $n$ a megfelelő $k$ .
Próbáljunk ,,rossz'' színezést találni. Vizsgáljuk a következő sorozatot

\begin{matrix} A_{n - 2}; A_{2 (n - 2)}; A_{3 (n - 2)}; ...; A_{i (n - 2)}, \end{matrix}

(

*

)

amelyre teljesüljön, hogy

A_{(i + 1) (n - 2)}

már előfordul a sorozatban. Ez az

A_{(i + 1) (n - 2)}

pont csak az

A_{n - 2}

lehet, hisz minden ponttól két pont van

n - 2

távolságnyira, s a többi pontnál ezek a szomszédok. Így

\begin{matrix} (i + 1) (n - 2) \equiv n - 2 (mod (2 n - 1)), \end{matrix}

vagyis

\begin{matrix} (i + 1) (n - 2) = n - 2 + a (2 n - 1), \end{matrix}

(ahol

a

megfelelő egész szám), így

\begin{matrix} i (n - 2) = a (2 n - 1) . \end{matrix}

(1)

i = 2 n - 1

, akkor a sorozatunk az összes pontot tartalmazza. Közülük

n

darabot kiválasztva lesz köztük szomszédos (

A_{n - 2}

és

A_{i (n - 2)}

szomszédosnak tekintendő), hiszen különben

A_{j (n - 2)}

kiválasztása esetén

A_{(j + 1) (n - 2)}

nem választható ki, s az egyértelmű hozzárendelés miatt

n

pontot kiválasztva

n

pontot zárunk ki, ami összesen már több, mint

2 n - 1

. Nyilván

n - 1

pont kiválasztható, ilyen p1. az

A_{2 (n - 2)}; A_{4 (n - 2)}; ...; A_{(2 n - 2) (n - 2)}

. Tehát ha

i = 2 n - 1

, akkor

k = n

.
Nézzük meg azt, hogy milyen

n

-re lehetséges

i \neq 2 n - 1

. Ekkor

n - 2

-nek és

2 n - 1

-nek van

1

-nél nagyobb közös osztója, ami csak a

(2 n - 1) - 2 \cdot (n - 2) = 3

lehet, éspedig abban az esetben, ha

n = 3 e + 2

alakú. Vagyis

i = \frac{2 n - 1}{3}

lehetséges még. Ekkor a (

*

) sorozatban éppen a

3

-mal osztható sorszámú pontok találhatóak. A sorszámokhoz

1

-et, ill.

2

-t adva kaphatjuk az alábbi sorozatokat:

\begin{matrix} A_{1 (n - 2) + 1}; A_{2 (n - 2) + 1}; ...; A_{\frac{2 n - 1}{3} (n - 2) + 1}, & (**) \\ A_{1 (n - 2) + 2}; A_{2 (n - 2) + 2}; ...; A_{\frac{2 n - 1}{3} (n - 2) + 2} . & (***) \end{matrix}

A három sorozat tartalmazza az összes pontot. Az előzőekhez hasonlóan igazolható, hogy ha egy sorozat

\frac{2 n - 1}{3}

elemet tartalmaz, akkor legfeljebb

\frac{n - 2}{3}

elem színezhető ki úgy, hogy a színezés rossz legyen. Ez mindhárom esetben megtehető, így adódik, hogy

n - 2

pontot még ki lehet színezni rosszul,

n - 1

-et azonban már nem.
Tehát: ha

n = 3 e + 2

alakú, akkor

k = n - 1

, különben

k = n