Indian Mathematical Olympiad 1996 - Problem 6
Indian Mathematical Olympiad 1996 - Problem 6
Sia data una matrice $ 2n \times 2n $ i cui elementi sono 0, 1 ed avente esattamente $ 3n $ zeri. Dimostrare che è possibile eliminare tutti gli zeri cancellando opportunamente $ n $ righe ed $ n $ colonne.
Poiché la matrice ha $ 2n $ righe e $ 3n $ zeri, ci sono almeno $ n $ zeri che si trovano in righe che contengono almeno un altro zero.
Cancelliamo quindi il maggior numero possibile di righe che contengono più di uno zero: poiché si possono cancellare al più $ n $ righe e ogni riga contiene almeno 2 zeri, in questo modo si eliminano almeno $ 2n $ zeri. Il numero di zeri rimanenti è compreso tra 0 e $ n $, perciò è possibile eliminarli completamente cancellando tutte le colonne che ne contengono almeno uno.
L'ho scritta un po' di fretta, ma spero che sia giusta.
Cancelliamo quindi il maggior numero possibile di righe che contengono più di uno zero: poiché si possono cancellare al più $ n $ righe e ogni riga contiene almeno 2 zeri, in questo modo si eliminano almeno $ 2n $ zeri. Il numero di zeri rimanenti è compreso tra 0 e $ n $, perciò è possibile eliminarli completamente cancellando tutte le colonne che ne contengono almeno uno.
L'ho scritta un po' di fretta, ma spero che sia giusta.
L'idea è molto buona, anche se forse va chiarita meglio... 
Un modo è considerare un elenco delle righe ordinato in modo che il numero di zeri che contengono sia (debolmente) crescente: ora, se nelle prime $ ~n $ righe ci fossero in totale più di $ ~n $ zeri, almeno una conterrebbe $ ~2 $ zeri (altrimenti il totale sarebbe $ ~\le n $), quindi ognuna le ultime $ ~n $ righe ne dovrebbe contenere almeno $ ~2 $ (per l'ipotesi fatta sull'elenco). Il totale di zeri sarebbe $ >n+2n=3n $, assurdo! Quindi le prime $ ~n $ righe hanno in totale al massimo $ ~n $ zeri e cancellando le ultime $ ~n $ righe
Un modo è considerare un elenco delle righe ordinato in modo che il numero di zeri che contengono sia (debolmente) crescente: ora, se nelle prime $ ~n $ righe ci fossero in totale più di $ ~n $ zeri, almeno una conterrebbe $ ~2 $ zeri (altrimenti il totale sarebbe $ ~\le n $), quindi ognuna le ultime $ ~n $ righe ne dovrebbe contenere almeno $ ~2 $ (per l'ipotesi fatta sull'elenco). Il totale di zeri sarebbe $ >n+2n=3n $, assurdo! Quindi le prime $ ~n $ righe hanno in totale al massimo $ ~n $ zeri e cancellando le ultime $ ~n $ righe Giulio C ha scritto:Il numero di zeri rimanenti è compreso tra 0 e n, perciò è possibile eliminarli completamente cancellando tutte le colonne che ne contengono almeno uno.
Viviamo intorno a un mare come rane intorno a uno stagno. (Socrate)
Ieri sera poi sono ritornato sul mio ragionamento e ho scritto la dimostrazione in modo un po' più "sensato".
Anch'io ero partito con l'idea dell'elenco delle righe per numero crescente di zeri, anche se mi ero concentrato più che altro nel cercare di dimostrare che si potevano eliminare almeno $ 2n $ zeri cancellando $ n $ righe, in modo da eliminare con sicurezza gli altri con le colonne. Effettivamente, scritta come l'hai proposta tu è decisamente più elegante
Anch'io ero partito con l'idea dell'elenco delle righe per numero crescente di zeri, anche se mi ero concentrato più che altro nel cercare di dimostrare che si potevano eliminare almeno $ 2n $ zeri cancellando $ n $ righe, in modo da eliminare con sicurezza gli altri con le colonne. Effettivamente, scritta come l'hai proposta tu è decisamente più elegante