Conoscete il teorema dei quattro colori? Afferma che una mappa può sempre essere colorata usando quattro soli colori distinti, senza che due regioni dello stesso colore abbiano un tratto di confine in comune (un punto è permesso). Il teorema è stato enunciato nella seconda metà del secolo XIX, ma si dovette aspettare il 1977 per averne una dimostrazione… che richiede una quantità assurda di conti al computer.
Nel caso di Flood Fill non vi si chiede di dimostrare il teorema, ma semplicemente di colorare alcune mappe usando il minor numero di colori possibile. Purtroppo, anche se vengono assegnate delle stelle se si risparmiano colori, non ho visto da nessuna parte un modo per contare le stelle vinte e/o sapere se si poteva fare di meglio. Ad ogni buon conto, buona colorazione!
P.S.: il sito apre una finestra su http://www.paradoxide.com/ – ho dato un’occhiata al sorgente e mi pare setti solo Google Analytics, ma i paranoici potrebbero bloccare il sito e/o evitare di giocare.
(via Passion for Puzzles)
Ultimo aggiornamento: 2009-11-08 07:00
Non so se c’e’ materia per scriverci un post di divulgazione matematica, ma mi piacerebbe leggere cosa ne pensi delle dimostrazioni di teoremi che usano ‘brute force’ al calcolatore, e del perche’ sono appunto accettate come dimostrazioni.
@maxxfi: boh, non so quanto riuscirei a dire. In due parole: sono brutte ma valide.
Per sapere se nu determinato livello e’ stato risolto col numero minimo di colori possibile basta selezionere “levels”.
@maxxfi: le dimostrazioni al calcolatore sono come le altre: solo che invece di caso 1, caso 2, e caso 3, arrivano fino al caso 1500, e allora si preferisce far fare l’analisi caso-per-caso a un calcolatore.
In altre parole: si dimostra che se tutte le carte nella lista delle 1500 (il numero è naturalmente tirato a caso) sono colorabili con quattro colori, allora tutte le carte sono colorabili con quattro colori; la verifica dei 1500 casi particolari viene poi svolta al calcolatore.
I miei figli hanno passato un’ora a litigare davanti al computer per questo gioco, e posso scrivere questi commenti solo perché li ho spediti a fare i compiti con la forza.
maxxfi, mettiamola così: per quanto ne so nessuno ha mai controllato effettivamente che i conti fatti al computer siano corretti. epperò due gruppi indipendenti di ricerca hanno prodotto due dimostrazioni (entrambe al computer) nel corso degli ultimi 30 anni, e in entrambi i casi il codice del computer era open-source, quindi chiunque è libero di trovare un errore (e infatti degli errorini sono stati trovati e corretti).
la questione filosofica probabilmente si può riassumere nella domanda: da quando in qua in una dimostrazione matematica l’onere della prova spetta all’accusa (il lettore/referee) e non alla difesa (l’autore)? è un po’ perverso che solo perché la mia prova dura 5 stramiliardi di pagine nessuno mi possa dir niente.
(è anche vero che parecchie dimostrazioni “manuali” sono ugualmente incomprensibili (perché troppo lunghe e complesse) per una tipica mente umana: l’esempio classico è il teorema di classificazione dei gruppi finiti, ma anche il teorema dei minori di robertson-seymour non scherza:
http://en.wikipedia.org/wiki/Classification_of_finite_simple_groups
http://en.wikipedia.org/wiki/Robertson%E2%80%93Seymour_theorem
una riflessione un po’ provocatoria ma interessante su questi temi la puoi trovare in un libro di e.b. davies:
http://books.google.de/books?id=mpwtwZ9pJg8C&dq=science+through+the+looking+glass+davies&source=gbs_navlinks_s)
@maxxfi, @delio: alla fine ho scritto un pipponcino al riguardo, ma uscirà mercoledì perché sono pigro :-)
Ecco, infatti e’ la questione filosofica che mi lascia un po’ perplesso.
Vabbe’ mi metto pigramente ad aspettare la pubblicazione del mercoledi’ :-)
Niente come un paio di decenni di ricerca in matematica per far passare ogni interesse per la filosofia soggiacente. IMHO, ovviamente.
@barbara: non avendo mai fatto ricerca in matematica, io posso permettermi questi lussi :-)
barbara, un po’ hai ragione, ma la questione è molto terra terra: quando fai un corso di teoria dei grafi, lo chiami “teorema dei quattro colori” o “congettura dei quattro colori”? io opto per la prima, ma una scelta va fatta.
@delio: si è parlato per secoli dell’Ultimo Teorema di Fermat, su…