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!
