Olimpiadi cinesi 2007
Olimpiadi cinesi 2007
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...)
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!
No, non sono collegatejulio14 ha scritto:Mi rimane solo un dubbio, una riga così ha quattro caselle bianche collegate?
NNBBNBBN
o serve che siano tutte collegate così:
NNBBBBNN
?
il secondo caso si
(attenzione che non per forza devo essere in 4 anche di meno vanno bene )
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!
Provo..
Uno a fila/colonna è fisso senno se ne formano 7 collegati...quindi 7+8-1=14
Ma penso ci sia di meglio
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
@Cassa: Non va bene perchè nemmeno le caselle nere devono essere collegate...
(sempre se ho capito )
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?)
(sempre se ho capito )
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?)
Beh non è detto che se ce ne sono 5 sulla stessa riga siano per forza collegate...
Ad esempio:
Per obliguo intende a 45°..come l'alfiere per intenderci
Ad esempio:
Codice: Seleziona tutto
BBBBNBBB
BBBBNBBB
BBBNNBBB
BBBNBBBB
NNNNBNNN
BBNNBNBB
BBNBBNBB
Chissà perchè avevo letto "caselle bianche sulla stessa riga collegate"Cassa ha scritto:Beh non è detto che se ce ne sono 5 sulla stessa riga siano per forza collegate...
Ad esempio:
Per obliguo intende a 45°..come l'alfiere per intenderciCodice: Seleziona tutto
BBBBNBBB BBBBNBBB BBBNNBBB BBBNBBBB NNNNBNNN BBNNBNBB BBNBBNBB
- matemark90
- Messaggi: 67
- Iscritto il: 03 nov 2006, 20:02
- Località: la città del carnevale (RE)
@ 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
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.
Per tre cose vale la pena di vivere: la matematica, la musica e l'amore.
Re: Olimpiadi cinesi 2007
Un dubbio sulle obiezioni a Cassa... se valeva sia per il bianco sia per il nero, che bisogno c'era di specificare?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...)
"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)
- matemark90
- Messaggi: 67
- Iscritto il: 03 nov 2006, 20:02
- Località: la città del carnevale (RE)
@ Cassa: Per connessi intendi collegati vero?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.
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.
Per tre cose vale la pena di vivere: la matematica, la musica e l'amore.
si, mi sono spiegato male... mi riferisco solo ai bianchi naturalmente... ma questo non influenza più di tanto la soluzioneciascuna riga e su ciascun segmento obbliquo (a 45°) ci siano al massimo 4 caselle collegate fra di loro.
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...
Un pochino di meno...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
La soluzione esatta è 11, ma lascio a voi dimostrare che è proprio il minimo e trovare tale configurazione
Appassionatamente BTA 197!