Olimpiadi cinesi 2007

Conteggi, probabilità, invarianti, logica, matematizzazione, ...
Rispondi
Avatar utente
mod_2
Messaggi: 726
Iscritto il: 18 ago 2007, 20:26
Località: In fondo a destra

Olimpiadi cinesi 2007

Messaggio da mod_2 » 25 apr 2008, 14:51

Sia data una scacchiera di dimensioni $ $7*8 $ con tutte le caselle colorate di bianco all'inizio.
Due caselle colorate di bianco si dicono collegate se hanno in comune un lato o un vertice.
Qual è il numero minimo di caselle che devono essere colorate di nero affinché le caselle bianche rimanenti siano tutte collegate e che su ciascusa colonna, ciascuna riga e su ciascun segmento obbliquo (a 45°) ci siano al massimo 4 caselle collegate fra di loro.

(spero di esermi spiegato...)
Appassionatamente BTA 197!

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

Messaggio da julio14 » 25 apr 2008, 16:11

Mi rimane solo un dubbio, una riga così ha quattro caselle bianche collegate?
NNBBNBBN
o serve che siano tutte collegate così:
NNBBBBNN
?
"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!!!

Avatar utente
mod_2
Messaggi: 726
Iscritto il: 18 ago 2007, 20:26
Località: In fondo a destra

Messaggio da mod_2 » 25 apr 2008, 20:37

julio14 ha scritto:Mi rimane solo un dubbio, una riga così ha quattro caselle bianche collegate?
NNBBNBBN
o serve che siano tutte collegate così:
NNBBBBNN
?
No, non sono collegate
il secondo caso si
(attenzione che non per forza devo essere in 4 anche di meno vanno bene :wink: )

Esempio
NNBBNBBN
NNNBBNNN

le 6 caselle bianche sono collegate fra di loro per un vertice e per un lato, ma se guardi riga per riga, e colonna per colonna, non hai più di 4 collegate fra di loro
Appassionatamente BTA 197!

Avatar utente
Cassa
Messaggi: 236
Iscritto il: 28 mar 2006, 21:48
Località: Genova

Messaggio da Cassa » 26 apr 2008, 08:55

Provo..
Uno a fila/colonna è fisso senno se ne formano 7 collegati...quindi 7+8-1=14

Codice: Seleziona tutto

BBBBNBBB
BBBBNBBB
BBBBNBBB
BBBBNBBB
NNNNNNNN
BBBBNBBB
BBBBNBBB
Ma penso ci sia di meglio
:roll:

Alex89
Messaggi: 366
Iscritto il: 29 gen 2006, 16:57

Messaggio da Alex89 » 26 apr 2008, 09:01

@Cassa: Non va bene perchè nemmeno le caselle nere devono essere collegate...
(sempre se ho capito :P )
Tornando alle configurazioni, da quel che ho capito non ne posso colorare meno di 28 altrimenti per i piccioni su una riga avrei 5 caselle bianche (che devono essere collegate per ipotesi). D'altro canto, questa configurazione con 28 caselle nere

NNNNBBBB
BBBBNNNN
NNNNBBBB
BBBBNNNN
NNNNBBBB
BBBBNNNN
NNNNBBBB

dovrebbe andare (cosa intendevi con segmento obliquo?)

Avatar utente
Cassa
Messaggi: 236
Iscritto il: 28 mar 2006, 21:48
Località: Genova

Messaggio da Cassa » 26 apr 2008, 09:21

Beh non è detto che se ce ne sono 5 sulla stessa riga siano per forza collegate...
Ad esempio:

Codice: Seleziona tutto

BBBBNBBB
BBBBNBBB
BBBNNBBB
BBBNBBBB
NNNNBNNN
BBNNBNBB
BBNBBNBB
Per obliguo intende a 45°..come l'alfiere per intenderci

Alex89
Messaggi: 366
Iscritto il: 29 gen 2006, 16:57

Messaggio da Alex89 » 26 apr 2008, 09:45

Cassa ha scritto:Beh non è detto che se ce ne sono 5 sulla stessa riga siano per forza collegate...
Ad esempio:

Codice: Seleziona tutto

BBBBNBBB
BBBBNBBB
BBBNNBBB
BBBNBBBB
NNNNBNNN
BBNNBNBB
BBNBBNBB
Per obliguo intende a 45°..come l'alfiere per intenderci
Chissà perchè avevo letto "caselle bianche sulla stessa riga collegate" :P

Avatar utente
matemark90
Messaggi: 67
Iscritto il: 03 nov 2006, 20:02
Località: la città del carnevale (RE)

Messaggio da matemark90 » 26 apr 2008, 16:33

@ Cassa: a parte il fatto che alex89 non aveva capito bene il problema, secondo me la sua obiezione vale lo stesso... la seconda griglia che hai postato rispetta tutte le ipotesi ma hai annerito 17 caselle.
Poi il fatto che ce ne debbano essere almeno uno per colonna ed almeno uno per riga non vuol dire che ce ne sono almeno 14 (ad esempio se la griglia fosse 5*5 basterebbe annerire una diagonale)

Io ho trovato (sempre se ho capito giusto io, dato che questo problema si presta a fraintendimenti) una griglia che ne annerisce 12 ma non ho una vera dimostrazione per affermare che è il minimo

Codice: Seleziona tutto

BBBNBBB
BBBNBBB
BBNBBBB
BBBBNNN
NNNBBBB
BBBBNBB
BBBNBBB
BBBNBBB
Hasta la Carla... SIEMPRE!!!
Per tre cose vale la pena di vivere: la matematica, la musica e l'amore.

Avatar utente
Cassa
Messaggi: 236
Iscritto il: 28 mar 2006, 21:48
Località: Genova

Messaggio da Cassa » 26 apr 2008, 18:43

Non la tua griglia non è valida perchè tutti i bianchi sono connessi fra loro e quindi ci sono più di 4 bianchi connessi(anche se non direttamente)nella stessa riga

Avatar utente
Gatto
Messaggi: 487
Iscritto il: 25 nov 2007, 16:36
Località: Roma

Re: Olimpiadi cinesi 2007

Messaggio da Gatto » 26 apr 2008, 19:16

mod_2 ha scritto:Sia data una scacchiera di dimensioni $ $7*8 $ con tutte le caselle colorate di bianco all'inizio.
Due caselle colorate di bianco si dicono collegate se hanno in comune un lato o un vertice.
Qual è il numero minimo di caselle che devono essere colorate di nero affinché le caselle bianche rimanenti siano tutte collegate e che su ciascusa colonna, ciascuna riga e su ciascun segmento obbliquo (a 45°) ci siano al massimo 4 caselle collegate fra di loro.

(spero di esermi spiegato...)
Un dubbio sulle obiezioni a Cassa... se valeva sia per il bianco sia per il nero, che bisogno c'era di specificare?
"Fu chiaro sin dall'inizio che ogni qual volta c'era un lavoro da fare, il gatto si rendeva irreperibile." (George Orwell - La fattoria degli animali)

Avatar utente
matemark90
Messaggi: 67
Iscritto il: 03 nov 2006, 20:02
Località: la città del carnevale (RE)

Messaggio da matemark90 » 26 apr 2008, 19:21

mod_2 ha scritto:Qual è il numero minimo di caselle che devono essere colorate di nero affinché le caselle bianche rimanenti siano tutte collegate e che su ciascusa colonna, ciascuna riga e su ciascun segmento obbliquo (a 45°) ci siano al massimo 4 caselle collegate fra di loro.
@ Cassa: Per connessi intendi collegati vero?
Le caselle bianche devono essere tutte collegate, poi nel secondo messaggio, se ho capito bene, mod_2 risponde proprio a quello che hai detto tu.

@ Gatto: secondo me perchè non ti interessa se sono collegate o no le caselle nere e le condizioni sono richieste solo su quelle bianche comunque non cambierebbe nulla non specificare...
Hasta la Carla... SIEMPRE!!!
Per tre cose vale la pena di vivere: la matematica, la musica e l'amore.

Avatar utente
mod_2
Messaggi: 726
Iscritto il: 18 ago 2007, 20:26
Località: In fondo a destra

Messaggio da mod_2 » 26 apr 2008, 20:26

ciascuna riga e su ciascun segmento obbliquo (a 45°) ci siano al massimo 4 caselle collegate fra di loro.
si, mi sono spiegato male... mi riferisco solo ai bianchi naturalmente... ma questo non influenza più di tanto la soluzione:wink:
Cassa ha scritto:Non la tua griglia non è valida perchè tutti i bianchi sono connessi fra loro e quindi ci sono più di 4 bianchi connessi(anche se non direttamente)nella stessa riga

E invece è valida, quello che è richiesto è appunto che tutti i bianchi siano collegati (per lato o eventualmente per vertice) ma che su ogni riga, colonna, segmento obbliquo, non si siano più di 4 collegati

es.
BBBBN
BBBNN
...
In tutto abbiamo 7 B collegati ma se guardi solo la prima riga, o solo la seconda riga hai nel primo caso solo 4 B collegati, nel secondo 3 B, Idem le colonne e gli obbliqui

Spero che questa volta mi sono spiegato...
Io ho trovato (sempre se ho capito giusto io, dato che questo problema si presta a fraintendimenti) una griglia che ne annerisce 12 ma non ho una vera dimostrazione per affermare che è il minimo
Un pochino di meno... :wink:
La soluzione esatta è 11, ma lascio a voi dimostrare che è proprio il minimo e trovare tale configurazione
Appassionatamente BTA 197!

Avatar utente
Cassa
Messaggi: 236
Iscritto il: 28 mar 2006, 21:48
Località: Genova

Messaggio da Cassa » 27 apr 2008, 10:46

ma quindi una del genere è valida?

BBBNBBB
NNNBNNN

Perchè da come avevo capito non lo era :roll:

Avatar utente
mod_2
Messaggi: 726
Iscritto il: 18 ago 2007, 20:26
Località: In fondo a destra

Messaggio da mod_2 » 27 apr 2008, 14:11

sì, è valida!
Appassionatamente BTA 197!

Rispondi