Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.

Zadatak sa matricom i submatricom

[es] :: Matematika :: Zadatak sa matricom i submatricom

[ Pregleda: 1805 | Odgovora: 6 ] > FB > Twit

Postavi temu Odgovori

Autor

Pretraga teme: Traži
Markiranje Štampanje RSS

number22
Bez

Član broj: 246412
Poruke: 44
*.opera-mini.net.



+1 Profil

icon Zadatak sa matricom i submatricom16.01.2010. u 10:37 - pre 175 meseci
Data je matrica formata 10x10 koja sadrzi tacno 15 elemenata jednakih nuli. Dokazati da postoji submatrica formata 5x5 koja ne sadrzi ni jednu nulu.
Probao sam raznim rasporedom nula i uvijek postoji bar jedna submatrica 5x5 bez nule. Ali ne znam kako da dokazem to...
 
Odgovor na temu

Cabo
Lokanje u bircuzu

Član broj: 10942
Poruke: 684
*.vdial.verat.net.



+5 Profil

icon Re: Zadatak sa matricom i submatricom16.01.2010. u 15:22 - pre 175 meseci
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 .
 
Odgovor na temu

Cabo
Lokanje u bircuzu

Član broj: 10942
Poruke: 684
*.vdial.verat.net.



+5 Profil

icon Re: Zadatak sa matricom i submatricom17.01.2010. u 16:34 - pre 174 meseci
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.
 
Odgovor na temu

Nedeljko
Nedeljko Stefanović

Član broj: 314
Poruke: 8632
*.ptt.rs.



+2791 Profil

icon Re: Zadatak sa matricom i submatricom17.01.2010. u 18:23 - pre 174 meseci
Ista nula može pripadati raznim matricama. Neće to biti sve različite nule. Drugačije to ide.
Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.
 
Odgovor na temu

Nedeljko
Nedeljko Stefanović

Član broj: 314
Poruke: 8632
212.200.65.*



+2791 Profil

icon Re: Zadatak sa matricom i submatricom17.01.2010. u 23:30 - pre 174 meseci
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.
Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.
 
Odgovor na temu

number22
Bez

Član broj: 246412
Poruke: 44
*.opera-mini.net.



+1 Profil

icon Re: Zadatak sa matricom i submatricom18.01.2010. u 15:22 - pre 174 meseci
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
 
Odgovor na temu

Nedeljko
Nedeljko Stefanović

Član broj: 314
Poruke: 8632
212.200.65.*



+2791 Profil

icon Re: Zadatak sa matricom i submatricom18.01.2010. u 16:57 - pre 174 meseci
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.
Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.
 
Odgovor na temu

[es] :: Matematika :: Zadatak sa matricom i submatricom

[ Pregleda: 1805 | Odgovora: 6 ] > FB > Twit

Postavi temu Odgovori

Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.