Kreni od suprotne pretpostavke, da ne postoji takva podmatrica, tj. da svaka podmatrica formata mora da sadrži bar jednu nulu, pa onda vidi koliko takvih može da se smesti u matricu formata .

Ako se još nisi dosetio, evo ideje dokaza:

Neka je podmatrica formata (). Tada postoji mogućih pozicija podmatrice u okviru „velike“ matrice.

Ako pretpostavimo suprotno, da svaka podmatrica mora da sadrži bar jednu nulu, i uzmemo najbolji mogući slučaj, da svaka sadrži tačno jednu nulu, krenuvši od gornjeg levog elementa matrice, brzo ćemo „istrošiti“ tih 15 nula, jer nam treba bar da bismo svakoj matrici pridružili „njenu“ nulu. Dakle, to je kontradikcija, pa postoji podmatrica koja ne sadrži nijednu nulu.

Ista nula može pripadati raznim matricama. Neće to biti sve različite nule. Drugačije to ide.

Uradiću po slučajevima.

Ako postoji 5 vrsta sa po najviše jednom nenula komponentom, izbaci preostalih 5 vrsta i one kolone koje sadrže nenule u tih 5 vrsta.

U suprotnom imaš bar 6 vrsta sa po bar dve nenule. Dakle, u preostale 4 vrste imaš najviše 3 nenule. Izaberi te 4 vrste još jednu od preostalih 6 vsta. Izbaci sve kolone koje u izabranim vrstama imaju nenulu.

Evo do kakvog sam rjesenja dosao.

Pocetnoj matrici formata 10x10 treba da se precrta (izbaci) 5 vrsta koje imaju najvise nula. Ako dve ili vise vrsta imaju jednak br. nula izbacujemo nasumicno jer nije bitno koja ostaje. Sada precrtamo svaku kolonu koja sadrzi nulu a koja nije prethodno precrtana. I na kraju ostaje trazena podmatrica koja je formata najmanje 5x5 a najvise 5x10

Hvala na pomoci

To rešenje se poklapa sa mojim, s tim što sam dao i dokaz da ostaje najmanje 5 kolona. OK, i sam si došao do ispravnog rešenja.