a Q6 again
Opgave - IMO 1971 dag 2 vraag 3
Gegeven zijn $n^2$ niet-negatieve gehele getallen in een $n*n$matrix zodat el. $a_{ij}$ in de $i ^{de}$ rij en $j^{de}$ kolom staat.
Voor alle elementen waarvoor $a_{ij}=0$ geldt dat de som van de elementen in rij $i$ en kolom $j$ minimum $n$ is.
Bewijs dat de som van alle getallen in de matrix min. $0.5n^2$ is.
- login om te reageren
Oplossing
Zij $A$ de rij of kolom met kleinste som, zeg $S$, en zeg een rij (het bewijs voor een kolom verloopt analoog). Veronderstel eerst dat $S \geq \frac n2$. Dan zijn we klaar, aangezien de totale som, zeg $S_{T}$, dan groter dan of gelijk aan $n \frac n2=\frac {n^2}{2}$ is. Veronderstel daarom dat $S<\frac n2$. Merk op dat het aantal nullen in deze rij, zeg $N$, minimaal $n-S$ is, daar er maximaal $S$ niet-nul elementen kunnen voorkomen. In elk van de kolommen onder een $0$ in $A$ is de som minimaal $n-S$ volgens het gegeven. In elk van de andere kolommen is de som minstens $S$.
We krijgen nu de ongelijkheid $S_{T} \geq N(n-S)+(n-N)S$.
Merk op dat $S \le \frac n2$ en $N \ge \frac n2$ en bijgevolg is
\begin{align*}
N(n-S)+(n-N)S&=(n-N)S+(n-N)(n-S)+(2N-n)(n-S)\\
& \ge n(n-N) + (2N-n)\frac n2\\
&=\frac{n^2}2
\end{align*}
zodat we concluderen dat $S_T\ge \frac{n^2}{2}$ zoals gevraagd.