OliForum Matematico

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...)

Mi rimane solo un dubbio, una riga così ha quattro caselle bianche collegate?
NNBBNBBN
o serve che siano tutte collegate così:
NNBBBBNN
?

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 )

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

Provo..
Uno a fila/colonna è fisso senno se ne formano 7 collegati...quindi 7+8-1=14
Ma penso ci sia di meglio

@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?)

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

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"

@ 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

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

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?

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...

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

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...

La soluzione esatta è 11, ma lascio a voi dimostrare che è proprio il minimo e trovare tale configurazione

ma quindi una del genere è valida?

BBBNBBB
NNNBNNN

Perchè da come avevo capito non lo era

sì, è valida!