40. Pedine colorate su scacchiera
40. Pedine colorate su scacchiera
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.
Ultima modifica di Triarii il 04 feb 2014, 20:08, modificato 1 volta in totale.
"We' Inge!"
LTE4LYF
LTE4LYF
Re: 40. Pedine colorate su scacchiera
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
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
$ \mbox{ }\mbox{ } $And God said : $ \displaystyle c^2 \mu_0 \varepsilon_0 =1 $,
and then there was light.
$ \mbox{ }\mbox{ } $Tsune ni shinen kufu seyo
and then there was light.
$ \mbox{ }\mbox{ } $Tsune ni shinen kufu seyo
Re: 40. Pedine colorate su scacchiera
Oddio che scemo Comunque ora ho editato, dovrebbe essere corretto
"We' Inge!"
LTE4LYF
LTE4LYF
Re: 40. Pedine colorate su scacchiera
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
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
$ \mbox{ }\mbox{ } $And God said : $ \displaystyle c^2 \mu_0 \varepsilon_0 =1 $,
and then there was light.
$ \mbox{ }\mbox{ } $Tsune ni shinen kufu seyo
and then there was light.
$ \mbox{ }\mbox{ } $Tsune ni shinen kufu seyo
Re: 40. Pedine colorate su scacchiera
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
Spero di aver capito quello che intendevi dire
"We' Inge!"
LTE4LYF
LTE4LYF
Re: 40. Pedine colorate su scacchiera
Porca vacca che demente -.-
Della serie... Interpretiamo "al più" come "al meno"
Grazie
Della serie... Interpretiamo "al più" come "al meno"
Grazie
$ \mbox{ }\mbox{ } $And God said : $ \displaystyle c^2 \mu_0 \varepsilon_0 =1 $,
and then there was light.
$ \mbox{ }\mbox{ } $Tsune ni shinen kufu seyo
and then there was light.
$ \mbox{ }\mbox{ } $Tsune ni shinen kufu seyo
Re: 40. Pedine colorate su scacchiera
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 $.
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 $.
$ \mbox{ }\mbox{ } $And God said : $ \displaystyle c^2 \mu_0 \varepsilon_0 =1 $,
and then there was light.
$ \mbox{ }\mbox{ } $Tsune ni shinen kufu seyo
and then there was light.
$ \mbox{ }\mbox{ } $Tsune ni shinen kufu seyo