Annerendo caselle

[edriv]

In una tabella m x n alcune caselle sono annerite. Se in una riga o in una colonna solo una casella rimane bianca, posso annerire anche quella.

Se continuando di questo passo posso annerire tutte le caselle, quante erano come minimo le caselle inizialmente annerite?

[darkcrystal]

Vorrei dimostrare che è (m-1)(n-1). Senz'altro bastano: infatti prendo un rettangolo (m-1) x (n-1) tutto nero e ho vinto perchè alla prima mossa posso annerire tutte quelle restanti tranne 1... che annerisco alla mossa dopo.

Per mostrare che servono: casi piccoli a mano, insegna la combinatoria.
Sia poi $ N(m,n) $ il minimo numero di caselle nere che servono per la $ m \times n $

Notiamo ora che se ho una combinazione di neri che mi permette di annerire tutto, allora levando una qualunque riga o colonna il rettangolo che resta funziona ancora (cioè, riesco ancora ad annerirlo tutto)
Allora scompongo un rettangolo $ m \times n $ che funzioni con N caselle nere, supposto $ m \geq n $, in un rettangolo $ (m-1) \times n $ e la riga con il massimo numero di caselle nere. Diciamo M questo massimo. Per "ipotesi induttiva" (sulla somma delle dimensioni della matrice) ho allora che $ N \geq N \left( (m-1),n) + M=(m-2)(n-1)+M $ che vorrei $ \geq (m-1)(n-1) $. Devo perciò dimostrare che $ M \geq n-1 $.

Solo che sono arrivato qua e mi sono reso conto che non torna per le tabelle quadrate... ma ormai ho scritto tutta sta roba e perciò la posto

Dalle relazioni precedenti sappiamo che $ mM \geq N \geq (m-2)(n-1)+M \Rightarrow M \geq \frac{m-2}{m-1}(n-1) $.
Se m>n, allora si ha $ M \geq (n-1)-1+1/n $, ed essendo M intero deve essere M=n-1 (almeno).
A presto (spero) per il caso m=n.
Ciau!

P.S. Bel problema!

[edriv]

Son contento che sia un bel problema perchè mi è tipo venuto in mente mentre stavo pensando a chissà cosa addormentandomi, e per qualche motivo me ne sono ricordato il giorno dopo. Quando l'ho postato non avevo neanche una soluzione

Comunque, sintetizzando un po', c'è almeno una riga [o colonna] che all'inizio ha solo una casella bianca, altrimenti il gioco si ferma. Togliendo questa, è facile capire che il rettangolo rimanente deve cavarsela da solo. Per induzione si vede che questo ragionamento porta proprio alla stima $ ~ (m-1)(n-1) $ caselle nere, valore che è sicuramente sufficiente.

[darkcrystal]

Lol ok stavo venendo a scrivere che m'ero accorto dell'esistenza del mio fantomatico M ma vedo che mi hai preceduto
Comunque ancora complimenti per il problema!