tassellazione cromatica

Messaggioda tony » 08/04/2006, 23:38

Mi era stato segnalato il testo di un recente post, che non riesco però a rintracciare sul forum.
Perciò lo ribatto qui, scusandomi se sto generando un doppione (che sarò lieto di eliminare se mi si indicherà il post "perso").

"Ogni punto del reticolo Z x Z è colorato con un colore scelto tra n >= 1 possibili.
Per quali n è sempre possibile determinare 2 punti dello stesso colore tali che la loro distanza sia maggiore di 100 e il segmento che li unisce non contenga altri punti del reticolo?"

Non sono sicuro di aver ben capito il problema, quel "sempre" mi confonde";
azzardo comunque una risposta: 8851 colori.

così taaanti ?
Un pittore divisionista puntinista impazzirebbe di gioia,
ma a me tremano le vene ai polsi!

Qualcuno vuol confermare/smentire/approfondire ?
tony
Average Member
Average Member
 
Messaggio: 790 di 873
Iscritto il: 11/11/2005, 00:47
Località: milano

Messaggioda tony » 09/04/2006, 17:10

ho ricalcolato con calma, scendendo a 8711 colori, e di lì non credo di potermi schiodare.

ma restano tutte le mie perplessità sulla comprensione del problema ...
tony
Average Member
Average Member
 
Messaggio: 791 di 873
Iscritto il: 11/11/2005, 00:47
Località: milano

Messaggioda Thomas » 10/04/2006, 15:36

Per ora mi limito a fare una osservazione, vedila come "approfondimento", Tony :wink: .

Elimino la condizione della distanza, questo forse renderà il problema banale, ma per ora...

Utilizzo questi:

Fatto1: la retta per i due punti $(x,y)$ e $(x',y')$ $in$ $ZxZ$ non contiene altri punti del reticolo $<=>$ $mcd(|x-x'|,|y-y'|)=1$.

Fatto2: supponiamo di avere a disposizione $n$ colori. Se troviamo $n+1$ punti t.c. a coppie verificano la condizione del fatto1, allora esistono 2 punti che verificano la condizione dell'esercizio "semplificato".
dim: infatti per il principio dei cassetti esistono 2 punti colorati uguali.

Vogliamo trovare un procedimento induttivo per fornire i punti necessari ad applicare il fatto2. I punti che si cercheranno saranno del tipo $(n,a_n)$, cioè l'ascissa è fissata e calcolo solo l'ordinata. Supponiamo di avere trovato i primi $k-1$ punti (li ordino secondo le ascisse). L'ordinata del $k_(esimo)$ sarà data dalla $Y$ che risolve il sistema:

$Y = 1 mod (k)$
$Y-a_1=1 mod (k-1)$
$Y-a_1-a2=1 mod (k-2)$
....
$Y-a_1-a_2-...-a_(k-1)=1 mod 1$

Questo sistema ha soluzioni (credo, è un pò di tempo che non lo vedo e non l'ho mai saputo bene a dire il vero :? ) per il teorema cinese del resto e rispetta le condizioni in quanto vale:

$a=1 mod b => mcd(a,b)=1$

Fine. In pratica avrei voluto dimostrare che quei 2 punti esistono sempre indipendentemente da ogni n, se eliminiamo la condizione sulla distanza. Cosa ne pensate? Secondo me ho fatto qualche errore, altrimenti c'è qualcosa che non mi torna :?
Ultima modifica di Thomas il 10/04/2006, 15:48, modificato 2 volte in totale.
Thomas
Senior Member
Senior Member
 
Messaggio: 438 di 1954
Iscritto il: 28/09/2002, 22:44

Messaggioda Thomas » 10/04/2006, 15:45

Ah... per quanto riguarda le difficoltà di interpretazione, io la vedo così Tony:

- Trovare tutti gli $n$ t.c. per qualsiasi colorazione fatta usando solamente $n$ colori sia possibile trovare i 2 punti che verificano la proprietà;

ti pare accettabile?
Thomas
Senior Member
Senior Member
 
Messaggio: 439 di 1954
Iscritto il: 28/09/2002, 22:44

Messaggioda Thomas » 12/04/2006, 22:21

Tony??
Thomas
Senior Member
Senior Member
 
Messaggio: 447 di 1954
Iscritto il: 28/09/2002, 22:44


Torna a Algebra, logica, teoria dei numeri e matematica discreta

Chi c’è in linea

Visitano il forum: @melia, caulacau e 12 ospiti