Newsgroup: it.hobby.enigmi
Titolo: mappe da colorare incrementalmente

Discutendo di colorazioni a proposito di polimini su it.hobby.enigmi
mi e' venuto in mente questo problema del quale ho solo una
soluzione parziale.
E' ben noto che tutte le mappe si possono colorare con al
piu' 4 colori. (teorema dei 4 colori, etc.etc.)
Cosa succede se invece la mappa mi viene fornita
da un avversario una regione alla volta e devo scegliere
il colore volta per volta senza poter tornare indietro?
E' chiaro che se scelgo a caso e ho fortuna potrei comunque
trovare una 4-colorazione.
Allora per rendere il problema meno aleatorio
immagino di usare un algoritmo "greedy", ovvero ogni
volta coloro la  nuova regione con il primo colore che e'
compatibile con i suoi vicini (assumo che ci sia un ordinamento tra i
colori).
Ci si puo' chiedere in questo caso quanti colori sono
necessari per colorare una mappa.
La risposta e' : arbitrari (se vi va potete provare a buttare giu' uno
schema di dimostrazione
prima di vedere la mia).
La seconda domanda, alla quale non so rispondere
e': quale e' il numero minimo di regioni in una mappa
che puo' forzarmi ad usare un certo numero di colori?
Se il problema vi interessa ho fatto un po' di disegni
chiarificatori e uno schema per la dimostrazione del fatto che si puo'
forzare un numero arbitrario di colori:
http://www.iread.it/colora.php
Troverete anche le mappe col minor numero di regioni
che forzano l'uso di 5, 6, e 7 colori.
Ma, e questo e' il problema, c'e' una formula o una
costruzione che mi da il numero minimale di regioni
in una mappa che mi forza ad usare K colori?
ciao,
g.

 
http://www.iread.it/colora.php
Mi sembra, pero', che il discorso potrebbe cambiare se per "regioni"
intendiamo polimini di ordine N su reticolo quadrato. Per N=1 direi
che bastano 2 colori. Per N=2 (domini) dovrebbero bastare 4 colori. Se
tanto mi da' tanto, dovrebbero bastare M colori (con M finito) per
ogni N. Bah...
Ciao
Livio


Eh, penso anche io, visto che il polimino di area N
penso abbia al massimo perimetro 2N+2 quindi non puo' confinare
con piu' di 2N+2 altri colori diversi, quindi direi che M<=2N+3
ma quasi sicuramente molto meno, perche' non si possono comunque
costruire tutte le possibili topologie.
Comunque bisogna pensarci, come diceva qualcuno "it isn't trivial!"...
ciao,
g.

 Comunque bisogna pensarci, come diceva qualcuno "it isn't trivial!"...
:o)
Noto ancora che c'e' differenza se consentiamo di costruire la mappa
aggiungendo polinimi disconnessi o se si obbliga ad "attaccare" il
polimino aggiunto almeno per un lato unitario. Direi che nel primo
caso il numero dei colori aumenta almeno di uno per N=1 e N=2.
Insomma, hai ragione, bisogna pensarci!
Ciao
Livio

Chenickname ha scritto:


Si potrebbe indire una gara per trovare i massimi in ogni singolo caso.
Incomincerei dal caso piu' semplice, cioe' da quello in cui bisogni
"attaccare" il polimino aggiunto. Potrebbe suonare cosi':
Per ogni N si formi una mappa incrementale con polimini di ordine N,
aggiungendo un polimino qualunque alla volta, confinante con il gruppo
precedente per almeno un lato unitario, senza lasciare buchi. Il polimino
aggiunto deve essere colorato con il primo colore disponibile di una
sequenza ordinata di colori. Il gioco consiste nel forzare il massimo
numero di colori con il minimo numero di pezzi.
Nel link esempi per N=2 e N=3, gia' un po' pensati :o), ma probabilmente
battibili.
Ciao
Livio
Guarda l'immagine cliccando 
http://attach.mynl.it/img?id=MTAwOTg
-- 
questo articolo e` stato inviato via web dal servizio gratuito 
http://www.newsland.it/news
 segnala gli abusi ad 
ab...@newsland.it

 battibili.
Belli! Appena ho un po' di tempo e di tranquillita' faccio una paginetta 
web e sfido quelli di alt.math.recreational che hanno risposto
positivamente al problema della colorazione greedy
(io mi sa che faccio solo l'arbitro...)
ciao,
g.

 (io mi sa che faccio solo l'arbitro...)
Te', mi sa che come al solito troverai un algoritmo che ci frega tutti! :o)
Ciao
Livio
Guarda l'immagine cliccando 
http://attach.mynl.it/img?id=MTAwOTk


Aggiungo uno schema di pentamini che forza dieci colori.
Ciao
Livio
Guarda l'immagine cliccando 
http://attach.mynl.it/img?id=MTAxMDg


 Guarda l'immagine cliccando 
http://attach.mynl.it/img?id=MTAxMDg
Accidenti! Sei una macchina!
(Mi fa piacere che il problemino ti abbia preso...)
Posso copiare le figure (eventualmente modificandole lievemente)
e pubblicarle in una paginetta?
ciao,
g.

 e pubblicarle in una paginetta?
Naturalmente si', non chiedermelo neppure.
Occhio, pero', stai pronto a rifarle perche' credo che siano
perfettibili.
Inoltre son fatte "a mano". Le ho controllate due volte ma... non si
sa mai.
Ciao
Livio