Kezdőlap


Feladat:	2009. évi Nemzetközi Matematika Diákolimpia 23. feladata	Korcsoport: 18-	Nehézségi fok: nehéz
Megoldó(k):	Éles András
Füzet:	2009/október, 393. oldal		PDF \| MathML
Témakör(ök):	Nemzetközi Matematikai Diákolimpia, Teljes indukció módszere, Számhalmazok
Hivatkozás(ok):	Feladatok: 2009/szeptember: 2009. évi Nemzetközi Matematika Diákolimpia 23. 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.

Éles András megoldása. A szöcske csak az $O$ és $S$ közötti szakaszokra léphet (és $S$ -re biztos rálép). Megmutatjuk, hogy ha útjában legfeljebb $n - 1$ mező van, amire nem szabad lépnie, akkor végig tud menni az úton.
Feltehetjük, hogy $a_{1} < a_{2} < ... < a_{n}$ . Teljes indukcióval bizonyítunk $n$ -re, $n = 1$ triviális. Ha $n = 2$ , akkor $a_{1} \notin M$ , vagy $a_{2} \notin M$ , így $a_{1}$ , $a_{1} + a_{2}$ , vagy $a_{2}$ , $a_{1} + a_{2}$ jó lesz. Legyen $M$ legkisebb eleme $d$ , ekkor $n > 2$ -re három eset állhat fönn:
I. $d < a_{n}$ , $a_{n} \notin M$ . Legyen a szöcske első lépése $a_{n}$ , ekkor átugorja $d$ -t, így az útjában legfeljebb $n - 2$ eleme marad $n$ -nek, és $n - 1$ különböző lépése. Az indukciós feltétel értelmében innen a szöcske már be tudja fejezni az útját (indukció: $n - 1$ ).
II. $d < a_{n}$ , $a_{n} \in M$ . Tekintsük az alábbi $2 n - 1$ darab páronként különböző számot:

\begin{matrix} a_{1} < a_{2} < ... < a_{n - 1} < a_{n} < a_{1} + a_{n} < a_{2} + a_{n} < ... < a_{n - 1} + a_{n} . \end{matrix}

Mivel

| M | \leq n - 1

és

a_{n} \in M

, azért a számok közül kiválasztható egy olyan

(a_{i}, a_{i} + a_{n})

pár, hogy semelyik sincs

M

-ben (különben

| M | \geq n

lenne). Legyen

a_{i}

és

a_{n}

a szöcske első két lépése, ekkor átugorja az

M

-beli

d

-t és

d < a_{n}

-et, így hátralévő útjában már csak legfeljebb

n - 3

tiltott mező van, és

(n - 2)

-t ugrik még, innen már be tudja fejezni az útját (indukciós feltétel,

(n - 2)

-re).
III.

d \geq a_{n}

. Hagyjuk el a

d

-t az

M

-ből, és legyen

a_{n}

a szöcske első lépése, ami legális. További útjában (

d

-t nem számolva)

n - 1

ugrás és legfeljebb

n - 2

tiltott mező szerepel, így végig tud menni az úton (indukciós feltétel

(n - 1)

-re) úgy, hogy

d

kivételével nem érinti

M

-et.
Ha

d

-t sem érinti, akkor a teljes útvonal jó, így készen vagyunk.
Ha

d

-t érinti, akkor

d \in M

miatt

d \neq S

, így a szöcske fog még lépni

d

-ről, tegyük fel, hogy

(d + a_{i})

-be lép. Ekkor

d + a_{i} \notin M

és utána sem lép rá

M

-beli elemre.

(d + a_{i})

-ig pedig legalább két ugrása van, mivel

d \geq a_{n}

és

a_{n}

a legelső lépés, így

a_{i} \neq a_{n}

.
Rendezzük a teljes útvonalon csak a

d + a_{i}

előtti ugrásokat olyan sorrendbe, hogy

a_{n}

legyen az utolsó ugrás. Ekkor az utolsó szám, amire a szöcske

d + a_{i}

előtt ugrott:

\begin{matrix} d + a_{i} - a_{n} = d - (a_{n} - a_{i}) < d, \end{matrix}

tehát

d + a_{i}

előtt az átrendezett útvonalon már nincs tiltott pont, mert

d

-nél kisebb mindegyik.
Így ez az átrendezett útvonal egyetlen tiltott mezőt sem tartalmaz, az állítást igazoltuk.