m op n matrix
Opgave - APMC 1986 dag 3 vraag 2
$mn$ verschillende reële getallen worden zodanig geschikt in een $m\times n-$matrix zodat alle elementen in iedere rij toenemen van links naar rechts. Iedere kolom wordt dan herschikt zodat de elementen in iedere kolom van boven naar onder toenemen. Toon aan dat de elementen in iedere rij nog altijd toenemen van links naar rechts.
- login om te reageren
Oplossing
Het is dus voldoende te bewijzen dat na de herschikking er geen getal rechts kan staan van een groter getal.
We bewijzen dit uit het ongerijmde: stel een getal $x$ uit kolom A en een getal $y$ uit kolom $A+1$.
Y is kleiner dan x.
Nu zijn alle elementen uit kolom $A+1$ die onder y staan ook lager dan y en dus lager dan x.
Als x het n-de hoogste element is uit kolom A, dan zijn er in kolom $A+1$ maximum $n-1$ elementen hoger dan x. $[1]$
Echter, bij de horizontale herschikking gold dat ieder element uit kolom $A+1$ hoger was dan het corresponderende element uit kolom A.
Voor een bepaald getal $b$ geldt dus dat er minstens zoveel getallen in kolom $A+1$ groter zijn dan $b$ als in kolom $A$.
Dus in kolom $A+1$ zijn minstens $n$ elementen hoger dan het n-de hoogste element van kolom A, hetgeen in tegenspraak is met het eerder gestelde bij $[1]$.
Alle getallen nemen dus nog steeds toe van links naar rechts.