Kezdőlap


Feladat:	Pontversenyen kívüli P.211	Korcsoport: 18-	Nehézségi fok: -
Megoldó(k):	Kiss Emil
Füzet:	1975/november, 151 - 152. oldal		PDF \| MathML
Témakör(ök):	Egyenlőtlenségek, Mátrixok, Pontversenyen kívüli probléma
Hivatkozás(ok):	Feladatok: 1974/április: Pontversenyen kívüli P.211

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.

Rendezzük az elemeinket a szokásos módon négyzetes táblázatba, $n$ sorból és $n$ oszlopból álló ún. mátrixot kapunk:

\begin{matrix} (\begin{matrix} a_{11} & a_{12} & ... & a_{1 n} \\ a_{21} & a_{22} & ... & a_{2 n} \\ \cdot & \cdot & \cdot \cdot \cdot & \cdot \\ a_{n 1} & a_{n 2} & ... & a_{n n} \end{matrix}) \end{matrix}

Jelöljük az

i

-edik sor elemeinek összegét

S_{i}

-vel, a

j

-edik oszlop elemeinek az összegét

O_{j}

-vel, és válasszuk ki a sorok közül is, oszlopok közül is azt, amelyikben a legkisebb az összeg. Legyen ez ‐ mondjuk ‐ a

k

-adik sor és az

m

-edik oszlop:

\begin{matrix} S_{i} & \geq S_{k} i = 1,2, ..., n; & (3) \\ O_{j} & \geq O_{m} j = 1,2, ..., n . \end{matrix}

Tegyük fel először, hogy

S_{k} \leq O_{m}

. A

k

-adik sorban a pozitív elemek száma nem lehet nagyobb

S_{k}

-nál, hiszen ezek mindegyike legalább

1

. Tehát legalább

(n - S_{k})

darab nulla van a

k

-adik sorban. Az ezeken átmenő oszlopok összege

(1)

szerint legalább

(n - S_{k})

, a többi pedig feltevésünk szerint legalább

S_{k}

. Az első fajtából legalább

(n - S_{k})

darab van, tehát az oszlopösszegek összege legalább

{(n - S_{k})}^{2} + S_{k}^{2}

\begin{matrix} O_{1} + O_{2} + ... + O_{n} \geq {(n - S_{k})}^{2} + S_{k}^{2} . \end{matrix}

(4)

Ebből viszont következik

(2)

, hiszen

(2)

bal oldalán is,

(4)

bal oldalán is a mátrix összes elemének az összege áll,

(4)

jobb oldalán pedig

\begin{matrix} {(n - S_{k})}^{2} + S_{k}^{2} = {(\frac{n}{2} + Δ)}^{2} + {(\frac{n}{2} - Δ)}^{2} = \frac{n^{2}}{2} + 2 Δ^{2} \geq \frac{n^{2}}{2}, \end{matrix}

ahol

\begin{matrix} Δ = \frac{n}{2} - S_{k} . \end{matrix}

Hasonlóan bizonyíthatjuk a feladat állítását abban az esetben is, amikor

S_{k} \geq O_{m}

, csak az oszlopok és sorok szerepét kell felcserélni.
Mellékeredményként azt is beláttuk, hogy

(2)

-ben akkor és csakis akkor lehet az egyenlőség jele érvényes, ha a sorösszegek és oszlopösszegek mindegyike

\frac{n}{2}

. Ez persze csak páros

n

-ekre teljesülhet, de azokra mindig el is érhető, például az

a_{i j} = δ_{i j} \cdot \frac{n}{2}

választással, ahol

δ_{i j}

az ún. Kronecker-féle deltafüggvény, értéke

1

vagy

0

aszerint, hogy

i

és

j

egyenlőek-e vagy sem.