Scacchiere, le amate

[Davide_Grossi]

Riciclo un problema che ho svolto ad una gara, è facile ma a mio parere anche carino:
<BR>
<BR>\"Determinare il numero minimo di caselle che possiamo segnare su una scacchiera 4x4 in modo tale che se eliminiamo 2 righe e 2 colonne qualsiasi rimane necessariamente almeno una casella tra quelle segnate\"

[FrancescoVeneziano]

A rischio di fare la figura dello stupido, do la risposta più ovvia:5
<BR>CaO (ossido di calcio)

[Davide_Grossi]

Sorry, but it\'s incorrect.
<BR>
<BR>P.S: non sono giochini della Bocconi, serve dimostrazione <IMG SRC="images/splatt_forum/icons/icon_biggrin.gif"> <IMG SRC="images/splatt_forum/icons/icon_biggrin.gif">
<BR>
<BR>Ciao!

[FrancescoVeneziano]

Ci riprovo.
<BR>
<BR>Con 7 si può fare:
<BR>xoxo
<BR>oxxo
<BR>xxoo
<BR>ooox
<BR>
<BR>Dimostriamo che non si può farlo con 6.
<BR>Se una riga (o colonna) contiene 4 segni, possiamo eliminarla, ed otterremmo una matrice 3*4, con 2 segni, che nella peggiore delle ipotesi sono su righe diverse, ma possiamo eliminarli ugualmente.
<BR>Se una riga (o colonna) contiene 3 segni, eliminandola otteniamo sempre una matrice 3*4 con 3 segni, che nella peggiore delle ipotesi sono su righe e colonne diverse, ma noi dobbiamo ancora cancellare una riga e due colonne, quindi possiamo eliminarli.
<BR>Di conseguenza, devono esistere 2 righe che contengano 2 segni l’una, cancellandole rimangono 2 segni, che vengono eliminati cancellando le colonne.
<BR>E con questo dovrei esserci, se hai una dimostrazione più “elegante” (e non ci vuole molto), vorrei conoscerla.
<BR>CaO (ossido di calcio)
<BR>