Kezdőlap


Feladat:	Gy.2665	Korcsoport: 16-17	Nehézségi fok: nehéz
Füzet:	1991/szeptember, 262 - 263. oldal		PDF \| MathML
Témakör(ök):	Logikai feladatok, Teljes indukció módszere, Sakk, Gyakorlat
Hivatkozás(ok):	Feladatok: 1990/december: Gy.2665

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.

Mivel egy sakkparti két résztvevője $1$ ponton osztozkodik, a lejátszott mérkőzések száma egyenlő a résztvevők pontszámának összegével. Ha $n$ játékos jött el az edzésre, akkor a pontok összege és így a mérkőzések $M$ száma:

\begin{matrix} M ≦ n \cdot k . \end{matrix}

(1)

Ha az

i

-edik játékos

p_{i}

darab partit játszott, akkor nyilván

\begin{matrix} M = \frac{\sum_{i = 1}^{n} p_{i}}{2}, \end{matrix}

(2)

hiszen az összegzés során minden egyes partit mindkét részvevője szerint számoltunk. Ha a

p_{i}

számok minimuma

p

, akkor a

(2)

összeget alulról becsülhetjük:

\begin{matrix} M ≧ \frac{\sum_{i = 1}^{n} p}{2} = \frac{n \cdot p}{2} . \end{matrix}

(3)

Egybevetve

(1)

-et és

(3)

-at

\begin{matrix} n \cdot k ≧ \frac{n \cdot p}{2}, azaz 2 k ≧ p, \end{matrix}

valóban van tehát olyan játékos, aki legfeljebb

2 k

darab mérkőzést játszott.
Az állítás második részét a játékosok számára vonatkozó teljes indukcióval igazoljuk, miközben a

k

értékét természetesen rögzítjük. Ha

n ≦ 2 k + 1

, akkor az állítás semmitmondó, hiszen minden egyes játékos külön-külön szobába kerülhet. Legyen most

n ≧ 2 k + 1

és tegyük föl, hogy az állítás igaz minden olyan edzés résztvevőire, ahol legfeljebb

n - 1

játékos vett részt. A feladat első része szerint van olyan

A

játékos, aki legfeljebb

2 k

partit játszott. Ha

A

-t elhagyjuk és töröljük a mérkőzéseit is, akkor a megmaradó játékosok pontjainak a száma nem nő, így az indukciós feltevés szerint ők elhelyezhetők legfeljebb

2 k + 1

teremben a feladat követelményei szerint. Mivel pedig

A

legfeljebb

2 k

meccset játszott, ezért legfeljebb ennyi teremben ülhet olyan játékos, aki

A

-val játszott az edzés során. A termek száma viszont több ennél, így a

2 k + 1

között van olyan terem ‐ esetleg üres ‐ ahol nincs olyan játékos, aki

A

-val játszott volna. Küldjük

A

-t ide, ezzel a kívánt elrendezést

n

darab játékossal is megvalósítottuk.

Megjegyzés. A feladat állítása éles abban az értelemben, hogy a feltételek teljesülése esetén

(2 k + 1)

-nél kevesebb terem már nem feltétlenül elegendő. Ha ugyanis

(2 k + 1)

résztvevője volt az edzésnek, mindenki játszott mindenkivel, és minden egyes parti döntetlenül végződött, akkor a feltételek nyilván teljesülnek és egyetlen terembe sem kerülhet egynél több résztvevő.