40. Pedine colorate su scacchiera

[Triarii]

Ci sono delle pedine bianche e nere su qualche casella di una scacchiera $2n \times 2n$., con al più una pedina per casella. Prima, rimuoviamo ogni pedina nera che si trova nella stessa colonna di qualche pedina bianca. Successivamente rimuoviamo ogni pedina bianca che si trova nella stessa riga di una qualche pedina nera restante. Dimostrare che per qualche colore, rimangono al più $n^2$ pedine di questo colore.

[simone256]

scusa non ho capito
Se in una colonna ci sono pedine bianche al primo passo togli tutte le nere su questa colonna... al passo dopo nessuna pedina bianca può essere tolta per mancanza di nere

[Triarii]

Oddio che scemo Comunque ora ho editato, dovrebbe essere corretto

[simone256]

secondo dilemma:
Ma non abbiamo un minimo di pedine da mettere? se all'inizio ne metti un numero minore di n^2 per ogni colore alla fine comunque la soluzione non viene. Forse su ogni casella all'inizio c'è una e una sola pedina? Ma anche in questo caso forse non funziona Illuminami!
Poi magari sono io che non ho capito bene

[Triarii]

Dunque, se ne metti meno di $n^2$ di un dato colore , la tesi è banalmente verificata (infatti sicuramente non vado ad aggiungere pedine). Devi dimostrare che esiste almneo un colore tale che rimane con al massimo $n^2$ pedine.
Spero di aver capito quello che intendevi dire

[simone256]

Porca vacca che demente -.-

Della serie... Interpretiamo "al più" come "al meno"
Grazie

[simone256]

Chiamiamo $ a $ il numero di pedine nere alla fine e $ b $ il numero di pedine bianche.
Osservazione: se su una riga c'è una pedina di un colore allora per forza su tale riga non avremo pedine dell'altro colore (lo stesso dicasi per le colonne), altrimenti saremmo in contraddizione con uno dei due passi iniziali.
Se $ a\leq n^2 $ abbiamo finito altrimenti posto $ a>n^2 $ definiamo $ i $ il numero di righe su cui si trovano pedine nere e $ j $ il numero di colonne dove si trovano pedine nere. $ ij $ è il numero di incroci fra tali righe e colonne quindi $ a \leq ij $ perchè altrimenti una pedina nera non si troverebbe in un incrocio e quindi apparterrebbe ad una colonna o riga che non contiene pedine nere, assurdo.
Avremo quindi $ n^2<a\leq ij \leq (\frac{i+j}{2})^2 $ da cui $ i+j>2n $ e $ (2n-i)+(2n-j)<2n $. Ma $ (2n-i)(2n-j)\leq(\frac{(2n-i)+(2n-j)}{2})^2<n^2 $, ma $ (2n-i) $ e $ (2n-j) $ sono il massimo numero di righe e di colonne dove possono esserci pedine bianche e $ (2n-i)(2n-j) $ è il massimo numero di pedine bianche per la ragione sopra. Quindi in ogni caso avremo che $ b< n^2 $.

[Triarii]

Giusto A te il prossimo!