cesenatico 1991

[Reginald]

Ho trovato questo bel problemino..
Si consideri una scacchiera 8x8 con le caselle colorate di 2 diversi colori rispettando questa regola:
ogni colonna ed ogni riga contiene 4 caselle nere e 4 caselle bianche

Dimostrare che il numero di coppie di caselle contigue bianche è uguale al numero di coppie di caselle continue nere

[ndp15]

Due caselle si dicono contigue se hanno un lato in comune.
Ora ci provo

[ndp15]

Up dato che sarei interessato alla soluzione.

[Gogo Livorno]

Ci provo, non è immediata la soluzione.

- Consideriamo la scacchiera 8x8, e immaginiamo di doverla colorare di nero e di bianco come proposto dal problema.

- Consideriamo la riga 1, e coloriamo casualmente 4 caselle di nero (le altre in bianco).

- Adesso consideriamo la riga 2, e coloriamo ancora una volta casualmente 4 caselle di nero (le altre in bianco).

- Notiamo che in ogni caso le coppie di caselle contigue disposte verticalmente (dunque con caselle appartenenti a righe diverse) sono dello stesso numero, in quanto: se le caselle nere della riga 2 sono tutte sopra le nere della riga 1 abbiamo 4 coppie di nero e 4 di bianco, se ce ne sono solo 3 abbiamo 3 coppie nere e 3 bianche, eccetera eccetera (il fatto che ci sia una bianca su una nera implica che ci sia anche una nera su una bianca, dato che sono dello stesso numero, e così via).

- Procedendo con lo stesso ragionamento, si arriva a dire che per ogni coppia di righe il numero di coppie di caselle dello stesso colore disposte verticalmente è uguale: ciò implica che sia uguale il numero complessivo di coppie di caselle dello stesso colore disposte verticalmente su tutta la scacchiera (è la somma di tutti i precedenti).

- Adesso ruotiamo tutta la scacchiera di 90 gradi: adesso, per quanto detto prima, dovrà essere uguale il numero di coppie di caselle dello stesso colore disposte orizzontalmente.

- Ma, dato che le condizioni per il riempimento sono esattamente le stesse fra righe e colonne, possiamo tranquillamente applicare il ragionamento precedente per le colonne che dopo la rotazione sono diventate righe, arrivando a concludere che è uguale il numero di coppie di caselle dello stesso colore disposte verticalmente.

- Ma se sono uguali il numero di coppie di caselle dello stesso colore disposte orizzontalmente e il numero di coppie di caselle dello stesso colore disposte verticalmente, la loro somma sarà ancora uguale.

- Da cui la tesi.

Buttato di fuori?

[Strangeloop]

Mi scuso, per l'up, non so se è ben accetto in questo forum... Ho fatto questo problema e vorrei accertarmi della correttezza della mia soluzione: da ogni configurazione si può ottenere quella della scacchiera classica scambiando coppie di caselle di colore diverso sulla stessa riga o colonna, perchè su ognuna abbiamo sempre quattro caselle nere e quattro bianche come nella configurazione che vogliamo raggiungere. Ogni scambio di questo tipo però non modifica la differenza tra il numero di coppie contigue, perchè per ogni colore le coppie di caselle dello stesso colore diventano miste e viceversa per quelle inizialmente miste. Poichè la configurazione finale la tesi vale (banalmente non ci sono coppie di caselle dello stesso colore), doveva valere anche per quella iniziale

[paga92aren]

Se ho capito bene tu vuoi scambiare due caselle della stessa riga (o colonna) di colore diverso, ma sulle colonne (o righe) delle due caselle cambiate il numero di caselle bianche e nere diventa 3 e 5. Quindi ottieni un'altra tabella che non soddisfa le condizioni del problema. Sono stato chiaro?

[Strangeloop]

Si, ma a me non interessa che le configurazioni intermedie rispettino le ipotesi. So che con una sequenza finita di mosse posso arrivare alla configurazione che mi interessa, analizzo le proprietà delle mosse e trovo un invariante. In realtà all'inizio avevo pensato al fatto che ogni configurazione si può ottenere dalla scacchiera originale bilanciando adeguatamente ogni scambio, ma non riuscendo a dimostrare questo fatto mi risultava un'induzione falsa.

[paga92aren]

ora ho capito cosa hai fatto e mi sembra giusto (in una dimostrazione per le gare devi fare tutti i casi quando scambi le due caselle o spiegarlo in modo generale e preciso)

[Strangeloop]

Ad esempio? Basta dire che scelgo di fare gli scambi o solo sulle righe o solo sulle colonne? In questo modo faccio vedere che posso arrivare alla scacchiera tradizionale, perchè una volta che ho fatto uno scambio su una colonna non ho più la possibilità di realizzare due righe della configurazione finale con scambi sulle righe

[Mist]

Avrei fatto anche io come strangeloop, qualcuno può scrivere se ne ha voglia una dimostrazione rigorosa da gara ben fatta ? non saprei come dirlo bene bene

[julio14]

Mi pare mal spiegato il fatto che la differenza fra il numero di caselle contigue bianche e quello delle caselle contigue nere non cambia. In particolare mi pare falso: ad esempio siano P e Q due caselle così disposte (B sta su un angolo, entrambi stanno su un lato esterno)

B
P B
B
N
Q B

se P è bianca e Q è nera, abbiamo 3 coppie bianche e 1 nera, 3-1=2. Viceversa, se Q è bianca e P è nera, abbiamo 1 coppia bianca e 0 nere, 1-0=1.

[Strangeloop]

Hai ragione, succede perchè le caselle da scambiare che hai fatto vedere tu non hanno lo stesso numero di lati in comune con altre caselle. Si potrebbe ovviare al problema scambiando solo caselle che verificano quest'ultima proprietà, se non fosse che così escluderemmo le configurazioni che hanno le caselle tutte di un colore agli angoli o tre di un colore e una dell'altro. Non trovo nulla per salvare la mia dimostrazione