Kezdőlap


Feladat:	F.2334	Korcsoport: 16-17	Nehézségi fok: átlagos
Füzet:	1982/április, 154 - 155. oldal		PDF \| MathML
Témakör(ök):	Logikai feladatok, Feladat
Hivatkozás(ok):	Feladatok: 1981/november: F.2334

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.

Jelöljük a futamban részt vevő autók számát $n$ -nel, és $e_{i, j}$ -vel azoknak az előzéseknek a számát, melyben az $i$ sorszámú autó elhagyja a $j$ sorszámút $(1 ≦ i$ , $j ≦ n$ , $i \neq j)$ . Legyen még $k_{i}$ az $i$ -edik autó által megtett körök száma. Állítjuk, hogy

\begin{matrix} e_{j, i} - e_{i, j} = k_{i} - k_{j} . \end{matrix}

(1)

Valóban, tegyük fel, hogy

k_{i} ≧ k_{j}

(a másik eset hasonlóan kezelhető), és képzeljük el, hogy az

i

-edik autóban ülünk. A futam végéig mi összesen

e_{i, j}

-szer hagytuk le a

j

-edik autót, az pedig összesen

e_{j, i}

-szer ment el mellettünk. Így

(e_{j, i} - e_{i, j})

-szer "köröztük le'', vagyis ennyivel több kört tettünk meg, mint a

j

-edik autó.
A futamban összesen

\sum_{(i, j)} e_{i, j}

előzés történt, ez pedig

\begin{matrix} \sum_{i = 1}^{n - 1} \sum_{j = i + 1}^{n} (e_{i, j} + e_{j, i}) = \sum_{i = 1}^{n - 1} \sum_{j = i + 1}^{n} (e_{i, j} - e_{j, i}) + 2 \sum_{i = 1}^{n - 1} \sum_{j = i + 1}^{n} e_{j, i}, \end{matrix}

és (1) alapján ugyanolyan párosságú, mint a

\begin{matrix} \sum_{i = 1}^{n - 1} \sum_{j = i + 1}^{n} (k_{i} - k_{j}) = (n - 1) k_{1} + (n - 3) k_{2} + ... + (- n + 3) k_{n - 1} + (- n + 1) k_{n} \end{matrix}

kifejezés. Esetünkben

n = 25

páratlan, tehát a jobb oldalon mindegyik

k_{i}

, egy páros számmal van szorozva. Ez az érték tehát páros. Ezzel bizonyítottuk, hogy a futamban páros sok előzés történt.

Megjegyzések. 1. Annyit használtunk csak ki, hogy az autók száma páratlan, így az állítás minden páratlan számú autóra érvényes. Páros sok autó esetén könnyen találhatunk ellenpéldát: ha egyetlen autó lekörözi a többit, nyilván páratlan sok előzést végez.
2. Sokan azon törték a fejüket, vajon hogyan bonyolítják le a feladatban említett próbafutamot. Többen feltételezték, hogy minden autó ugyanannyi kört tesz meg. Ez esetben a résztvevő autók számától függetlenül mindig páros sok előzés történik.