Kezdőlap


Feladat:	F.3090	Korcsoport: 16-17	Nehézségi fok: átlagos
Megoldó(k):	Almási Attila , Andrássy Zoltán , Horváth Gábor , Jakabfy Tamás , Kutalik Zoltán , Nyul Gábor , Puskás Péter , Rudolf Gábor , Sánta Zsuzsa , Szente Márk Zsombor , Szobonya László , Tóth Ádám , Tóth Mariann
Füzet:	1996/április, 219. oldal		PDF \| MathML
Témakör(ök):	Számelrendezések, Feladat
Hivatkozás(ok):	Feladatok: 1995/november: F.3090

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.

Legyen a táblázat $i$ -edik sorának $j$ -edik oszlopába írt szám $a_{i, j}$ . Jelölje $K_{i, j}$ annak a $2 \times 2$ -es és $H_{i, j}$ annak a $3 \times 3$ -as résztáblázatnak az összegét, amelynek bal felső sarka az $i$ -edik sor $j$ -edik eleme, azaz

\begin{matrix} \begin{matrix} K_{i, j} & = a_{i, j} + a_{i, j + 1} + a_{i + 1, j} + a_{i + 1, j + 1}, \\ H_{i, j} & = a_{i, j} + a_{i, j + 1} + a_{i, j + 2} + a_{i + 1, j} + a_{i + 1, j + 1} + a_{i + 1, j + 2} + a_{i + 2, j} + a_{i + 2, j + 1} + a_{i + 2, j + 2} . \end{matrix} \end{matrix}

Könnyen ellenőrizhető, hogy

\begin{matrix} \begin{matrix} H_{1,1} + H_{1,2} + H_{2,1} + H_{2,2} = a_{11} + a_{14} + a_{41} + a_{44} + \\ + 2 (a_{12} + a_{13} + a_{21} + a_{24} + a_{31} + a_{34} + a_{42} + a_{43}) + 4 (a_{22} + a_{23} + a_{32} + a_{33}) = \\ = K_{1,1} + K_{1,2} + K_{1,3} + K_{2,1} + K_{2,2} + K_{2,3} + K_{3,1} + K_{3,2} + K_{3,3} . \end{matrix} \end{matrix}

A feltételek szerint a bal oldalon álló összeg pozitív, tehát legalább az egyik

K_{i, j}

-nek szintén pozitívnak kell lennie.

Megjegyzés. A megoldás könnyen általánosítható. Ha a táblázat legalább

m + n - 1

sorból és oszlopból áll, továbbá minden

m \times m

-es résztáblázatban pozitív a számok összege, akkor van olyan

n \times n

-es résztáblázat, amelyben ugyancsak pozitív a számok összege. A bizonyítás alapja a következő azonosság:

\begin{matrix} \sum_{i = 1}^{m} \sum_{j = 1}^{m} (\sum_{k = 1}^{n} \sum_{l = 1}^{n} a_{i + k - 1, j + l - 1}) = \sum_{k = 1}^{n} \sum_{l = 1}^{n} (\sum_{i = 1}^{m} \sum_{j = 1}^{m} a_{k + i - 1, l + j - 1}) . \end{matrix}

(Valójában csak a tagok átrendezéséről van szó.) A bal oldalon

n \times n

-es, a jobb oldalon pedig

m \times m

-es táblázatok összegeit adjuk össze.