cesenatico 1991

Conteggi, probabilità, invarianti, logica, matematizzazione, ...
Rispondi
Avatar utente
Reginald
Messaggi: 137
Iscritto il: 24 gen 2009, 15:52
Località: Trento

cesenatico 1991

Messaggio da Reginald » 16 feb 2010, 18:13

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
Ci sono due errori che si possono fare lungo la via verso la verità...non andare fino in fondo, e non iniziare.
Confucio

ndp15
Messaggi: 598
Iscritto il: 18 gen 2007, 19:01

Messaggio da ndp15 » 16 feb 2010, 20:04

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

ndp15
Messaggi: 598
Iscritto il: 18 gen 2007, 19:01

Messaggio da ndp15 » 04 mar 2010, 22:28

Up dato che sarei interessato alla soluzione.

Gogo Livorno
Messaggi: 99
Iscritto il: 14 gen 2010, 14:56
Località: Livorno

Messaggio da Gogo Livorno » 08 mar 2010, 00:05

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
Messaggi: 13
Iscritto il: 14 gen 2011, 20:50

Re: cesenatico 1991

Messaggio da Strangeloop » 12 mar 2011, 16:28

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
Messaggi: 358
Iscritto il: 31 lug 2010, 10:35

Re: cesenatico 1991

Messaggio da paga92aren » 12 mar 2011, 17:00

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
Messaggi: 13
Iscritto il: 14 gen 2011, 20:50

Re: cesenatico 1991

Messaggio da Strangeloop » 12 mar 2011, 17:11

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
Messaggi: 358
Iscritto il: 31 lug 2010, 10:35

Re: cesenatico 1991

Messaggio da paga92aren » 12 mar 2011, 17:24

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
Messaggi: 13
Iscritto il: 14 gen 2011, 20:50

Re: cesenatico 1991

Messaggio da Strangeloop » 12 mar 2011, 17:31

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
Messaggi: 542
Iscritto il: 01 gen 2011, 23:52
Località: Provincia di Milano

Re: cesenatico 1991

Messaggio da Mist » 13 mar 2011, 21:48

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 :?
"Se [...] non avessi amore, non sarei nulla."
1Cor 13:2

"[...] e se io non so pentirmi del passato, la libertà è un sogno"
Soren Kierkegaard, Aut-Aut, Ed. Mondadori, pag. 102

Avatar utente
julio14
Messaggi: 1206
Iscritto il: 11 dic 2006, 18:52
Località: Pisa

Re: cesenatico 1991

Messaggio da julio14 » 13 mar 2011, 23:24

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.
"L'unica soluzione è (0;0;0)" "E chi te lo dice?" "Nessuno, ma chi se ne fotte"
[quote="Tibor Gallai"]Alla fine, anche le donne sono macchine di Turing, solo un po' meno deterministiche di noi.[/quote]
Non sono un uomo Joule!!!

Strangeloop
Messaggi: 13
Iscritto il: 14 gen 2011, 20:50

Re: cesenatico 1991

Messaggio da Strangeloop » 16 mar 2011, 17:50

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 :(

Rispondi