Kezdőlap


Feladat:	Gy.2120	Korcsoport: 16-17	Nehézségi fok: átlagos
Megoldó(k):	Megyesi Gábor
Füzet:	1983/október, 71 - 72. oldal		PDF \| MathML
Témakör(ök):	Számelrendezések, Gyakorlat
Hivatkozás(ok):	Feladatok: 1983/április: Gy.2120

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.

A táblázat bármelyik mezőjéről bármelyik másikra eljuthatunk legfeljebb $2 n - 2$ lépésben úgy, hogy minden lépésben egy mezőről valamelyik szomszédjára lépünk. Mivel a szomszédos mezőkbe írt számok különbsége legfeljebb 1, így a táblázatba írt számok maximumának és minimumának különbsége legfeljebb $2 n - 2$ . Ez azt jelenti, hogy a táblázatban legfeljebb $2 n - 1$ különböző szám szerepel.
Ebből következik, hogy a táblázatba írt $n^{2}$ darab szám közt van olyan, amelyik legalább $[\frac{n^{2}}{2 n - 1}]$ helyen szerepel. Mivel pedig

\begin{matrix} \frac{n^{2}}{2 n - 1} > \frac{n^{2}}{2 n} = \frac{n}{2}, így [\frac{n^{2}}{2 n - 1}] \geq [\frac{n}{2}] . \end{matrix}

Van tehát olyan szám, amiből legalább

[\frac{n}{2}]

darab van a táblázatban.

Megjegyzések. 1. A fentieknél jóval több igaz. Azt állítjuk, hogy vagy van olyan szám, amelyik minden sorban szerepel, vagy pedig olyan, amelyik a táblázat minden oszlopában előfordul. Van tehát olyan szám, amelyik legalább

n

-szer szerepel.
Jelölje ugyanis az

i

-edik sorban levő számok minimumát

m_{i}

, maximumát pedig

M_{i}

. Ha

m_{i} \leq a_{i} \leq M_{i}

, akkor

a_{i}

szerepel az

i

-edik sorban, hisz

m_{i}

és

M_{i}

előfordul itt, és közöttük a szomszédos mezőkön legfeljebb egyesével változnak a számok.
Ebből következik, hogy ha van olyan

a

, amelyre

m_{i} \leq a \leq M_{i}

, minden

i

-re, akkor

a

minden sorban szerepel.

Ha nincs ilyen

a

, akkor az [

m_{i}; M_{i}

]

i = 1, 2, ..., n

zárt intervallumok közös része üres. Könnyű belátni, hogy ha egy egyenesen véges sok zárt intervallum közül bármely kettőnek van közös pontja, akkor az intervallumok közös része nem üres. Így ha az [

m_{i}; M_{i}

] intervallumoknak nincs közös eleme, akkor van köztük kettő, amelyeknek szintén nincs közös eleme. Van tehát olyan

i

és

j

, hogy

m_{i} \leq M_{i} < m_{j} \leq M_{j}

.
Ez azt jelenti, hogy ha

M_{i} \leq b \leq m_{j}

, akkor az

i

-edik sor minden eleme legfeljebb

b

, a

j

-edik sorban pedig minden elem legalább

b

. Bármelyik oszlop mentén haladva jutunk tehát el az

i

-edik sorból a

j

-edikbe, át kell haladnunk olyan mezőn, amelyikben

b

szerepel, hisz a szomszédos mezőkbe írt számok eltérése legfeljebb 1. Így a

b

szám minden oszlopban szerepel.

Valóban van tehát olyan szám, amely legalább

n

-szer fordul elő a táblázatban.

Ennél többet már nem mondhatunk, hiszen egy olyan táblázatban, ahol az

i

-edik sor minden eleme

i