Poligoni regolari e colorazione dei lati
Poligoni regolari e colorazione dei lati
Ho trovato su internet dei vecchi esercizi e ci sono alcuni che non riesco a risolvere. Questo lo vorrei proporre:
----- Testo
In quanti modi si possono colorare i lati di un esagono regolare colorando ciascun lato di bianco o di nero (due colorazioni sono considerate uguali se esiste una rotazione che le porta a coincidere)?
-----
ps - Credo che il problema è di più facile soluzione nel caso il numero dei lati del poligono coincide con un numero primo. In tal caso all'interno dell'insieme delle 2^5 possibili colorazioni trovo due classi di equivalenza con un solo elemento corrispondente alle colorazioni con tutti i lati bianchi o neri e altre classi con 5 elementi ciascuno (essendo 5 un numero primo, una rotazione completa da 5 colorazioni equivalenti) e quindi:
numero delle colorazioni = (2^5-2)/5+2
Nel caso dell'esagono credo che ci siano altre classi di equivalenza oltre a 1 e 6 (ho in testa una gran confusione).
Perdonatemi il linguaggio e tutti gli errori che ho commesso.
----- Testo
In quanti modi si possono colorare i lati di un esagono regolare colorando ciascun lato di bianco o di nero (due colorazioni sono considerate uguali se esiste una rotazione che le porta a coincidere)?
-----
ps - Credo che il problema è di più facile soluzione nel caso il numero dei lati del poligono coincide con un numero primo. In tal caso all'interno dell'insieme delle 2^5 possibili colorazioni trovo due classi di equivalenza con un solo elemento corrispondente alle colorazioni con tutti i lati bianchi o neri e altre classi con 5 elementi ciascuno (essendo 5 un numero primo, una rotazione completa da 5 colorazioni equivalenti) e quindi:
numero delle colorazioni = (2^5-2)/5+2
Nel caso dell'esagono credo che ci siano altre classi di equivalenza oltre a 1 e 6 (ho in testa una gran confusione).
Perdonatemi il linguaggio e tutti gli errori che ho commesso.
Re: Poligoni regolari e colorazione dei lati
Avevo letto un problema simile con anche un link con un teorema che chiariva un po' di idee...
viewtopic.php?f=16&t=17398
In ogni caso credo che la questione sui numeri primi sia corretta... Per quanto riguarda il problema dell'esagono credo che il procedimento migliore sia contare a mano le possibili colorazioni del poligono... Se ti capita un poligono di $ n $ lati... ... Prova a dare un'occhiata al link sopra!
viewtopic.php?f=16&t=17398
In ogni caso credo che la questione sui numeri primi sia corretta... Per quanto riguarda il problema dell'esagono credo che il procedimento migliore sia contare a mano le possibili colorazioni del poligono... Se ti capita un poligono di $ n $ lati... ... Prova a dare un'occhiata al link sopra!
$ \mbox{ }\mbox{ } $And God said : $ \displaystyle c^2 \mu_0 \varepsilon_0 =1 $,
and then there was light.
$ \mbox{ }\mbox{ } $Tsune ni shinen kufu seyo
and then there was light.
$ \mbox{ }\mbox{ } $Tsune ni shinen kufu seyo
Re: Poligoni regolari e colorazione dei lati
Lasciando perdere link che puntano a link, provate a ragionare così:
- prendiamo una colorazione $C$ (cioè una sequenza di bianco e nero, tipo $bnnbbnbn\ldots$) di un poligono; la domanda fondamentale è quante sono le colorazioni equivalenti a lei per rotazione?
- come intuito, se il poligono ha un numero primo di lati $p$, a parte le colorazioni "banali" (tutta bianca e tutta nera), le altre si dividono in classi di $p$ elementi; dimostriamo che
- per un poligono di $6$ lati, 2. implica che ci sono classi con 1,2,3,6 elementi; inoltre, le classi con 2 (con 3) elementi sono tante quante le colorazioni di un "poligono" con 2 (con 3) lati.
Infine, si può rifare tutto per un poligono con $pq$ lati, dove $p$ e $q$ sono primi, esattamente nello stesso modo.
- prendiamo una colorazione $C$ (cioè una sequenza di bianco e nero, tipo $bnnbbnbn\ldots$) di un poligono; la domanda fondamentale è quante sono le colorazioni equivalenti a lei per rotazione?
- come intuito, se il poligono ha un numero primo di lati $p$, a parte le colorazioni "banali" (tutta bianca e tutta nera), le altre si dividono in classi di $p$ elementi; dimostriamo che
- 1. se la classe di una colorazione $C$ ha meno di $p$ elementi, allora esiste una rotazione non banale che lascia invariata $C$
2. se la classe di una colorazione $C$ ha meno di $p$ elementi, allora tale numero di elementi divide $p$
3. le uniche classi con meno di $p$ elementi sono date dalle colorazioni banali.
- per un poligono di $6$ lati, 2. implica che ci sono classi con 1,2,3,6 elementi; inoltre, le classi con 2 (con 3) elementi sono tante quante le colorazioni di un "poligono" con 2 (con 3) lati.
Infine, si può rifare tutto per un poligono con $pq$ lati, dove $p$ e $q$ sono primi, esattamente nello stesso modo.
Re: Poligoni regolari e colorazione dei lati
Già che ci siamo, lascio qui anche questo:
a) dimostrare, come ha indicato il buon Sam qui sopra, che le colorazioni con $a$ colori di un poligono con $p$ lati, a parte quelle banali in cui tutto è dello stesso colore, si dividono in classi (equivalenti per rotazione) di $p$ elementi.
b) dedurne il piccolo teorema di Fermat.
a) dimostrare, come ha indicato il buon Sam qui sopra, che le colorazioni con $a$ colori di un poligono con $p$ lati, a parte quelle banali in cui tutto è dello stesso colore, si dividono in classi (equivalenti per rotazione) di $p$ elementi.
b) dedurne il piccolo teorema di Fermat.
--federico
[tex]\frac1{\sqrt2}\bigl(\left|\text{loves me}\right\rangle+\left|\text{loves me not}\right\rangle\bigr)[/tex]
[tex]\frac1{\sqrt2}\bigl(\left|\text{loves me}\right\rangle+\left|\text{loves me not}\right\rangle\bigr)[/tex]
Re: Poligoni regolari e colorazione dei lati
mi potresti chiarire il senso di rotazione non banale?EvaristeG ha scritto:1. se la classe di una colorazione $C$ ha meno di $p$ elementi, allora esiste una rotazione non banale che lascia invariata $C$
poi il resto tanto vale metterlo in spoiler, anche se non ha molto senso..
Testo nascosto:
Il problema non è il problema, il problema sei tu.
Re: Poligoni regolari e colorazione dei lati
L'idea è quella, ma non mi torna la tua affermazione che se hai una rotazione non banale (btw, non banale = diversa dall'identità) di lunghezza $k$, allora $k$ divide il numero di lati. Per esempio per un poligono on 6 lati, la colorazione BNBNBN viene lasciata invariata, per esempio, da una rotazione di lunghezza 4, e da una di lunghezza 12; ma né 12 né 4 sono divisori di 6.
--federico
[tex]\frac1{\sqrt2}\bigl(\left|\text{loves me}\right\rangle+\left|\text{loves me not}\right\rangle\bigr)[/tex]
[tex]\frac1{\sqrt2}\bigl(\left|\text{loves me}\right\rangle+\left|\text{loves me not}\right\rangle\bigr)[/tex]
Re: Poligoni regolari e colorazione dei lati
la cosa è molto grave, ormai scrivo le cose senza accorgermene, comunque fai finta che non abbia scritto quella roba, l'affermazione è che dopo n rotazioni abbiamo di nuovo la stessa sequenza, quindi se una classe ha un numero di elementi minore di n, esso deve dividere n perche dopo k volte che quella classe viene ripetuta, dobbiamo avere lo stesso effetto di una rotazione completa,cioè di n.
adesso m'è venuta anche la parte mancante:
dimostriamo quindi per q=2 e p generico, in questo caso prendiamo una qualsiasi sequenza per il primo elemento, quindi prendiamo poi una sequenza che rende l'elemento dato dalla concatenazione di classe p (l'esistenza è stata dimostrata in precedenza,mi pare), ora dimostriamo che questa è l'unica, allora innanzitutto diciamo che dopo p rotazioni dell'elemento concatenato otteniamo lo stesso, quindi ogni lettera va al posto di una successiva, ora fissata la prima sequenza, se andiamo a modificare una lettera della seconda non vale piu la condizione "ogni lettera va al posto di una successiva",quindi modificando solo una lettera non funziona, allora intuitivamente anche modificando piu lettere non funziona. Ora per estendere a un generico q si dovrebbe fare cosi: se non vale per la prima sequenza e un altra, allora non vale per la prima sequenza e per tutte le altre, anche se non consecutive proprio perche gli elementi in ogni caso devo essere equivalenti a meno dell'ordine.
Quanto sara sbagliata questa dimostrazione (se cosi si puo chiamare)?
adesso m'è venuta anche la parte mancante:
dimostriamo quindi per q=2 e p generico, in questo caso prendiamo una qualsiasi sequenza per il primo elemento, quindi prendiamo poi una sequenza che rende l'elemento dato dalla concatenazione di classe p (l'esistenza è stata dimostrata in precedenza,mi pare), ora dimostriamo che questa è l'unica, allora innanzitutto diciamo che dopo p rotazioni dell'elemento concatenato otteniamo lo stesso, quindi ogni lettera va al posto di una successiva, ora fissata la prima sequenza, se andiamo a modificare una lettera della seconda non vale piu la condizione "ogni lettera va al posto di una successiva",quindi modificando solo una lettera non funziona, allora intuitivamente anche modificando piu lettere non funziona. Ora per estendere a un generico q si dovrebbe fare cosi: se non vale per la prima sequenza e un altra, allora non vale per la prima sequenza e per tutte le altre, anche se non consecutive proprio perche gli elementi in ogni caso devo essere equivalenti a meno dell'ordine.
Quanto sara sbagliata questa dimostrazione (se cosi si puo chiamare)?
Il problema non è il problema, il problema sei tu.
Re: Poligoni regolari e colorazione dei lati
Premettendo che ho sollevato qualcosa che è più grande di me provo a riassumere quello che ho capito (?):
In un poligono di n lati, con n numero primo, la rotazione di 1 porta la colorazione a sovrapporsi a se stessa solamente nel caso di tutti i lati colorati di bianco o tutti i lati colorati di nero (le colorazioni banali), ma nel caso di n numero primo qualsiasi rotazione di k e riconducibile alla rotazione di 1 e pertanto tranne le 2 classi di equivalenza delle colorazioni banali che sono composte da 1 elemento ciascuno, tutte le altre sono cpmposte da n elementi.
Nel caso di un poligono con n lati dove n non è un numero primo, entrano in gioco i divisori. Nel caso dell'esagono 1, 2, 3 e 6.
Per cercare di dare una soluzione all'esercizio:
------ Calcolo le colorazioni di classe 6
ncolclas6 = 2^6 [insieme possib.coloraz.] - (2^3-2)[insieme coloraz.polig.3 lati (divis.2?)] - (2^2-2)[insieme coloraz.polig.2 lati (divisore 3?)]-2[coloraz.banali]/6
ncolclas6 = (64 - 6 -2 - 2)/6 = 9
------ Calcolo le colorazioni di classe 3 [poligono con 3 lati, in realtà divisore 2?]
ncolclas3 = (2^3-2)/3 = 2
------ Calcolo le colorazioni di classe 2 [poligono con 2 lati, in realtà divisore 3?]
ncolclas2 = (2^2-2)/2 = 1
----- Calcolo le colorazioni totali
ncolttotali = ncolclas6 + nolclas3 + nclclas2 + numero colorazioni banali = 9 + 2 + 1 + 2 = 14
Spero il mio ragionamento sia corretto anche se 14 mi sembra un pò poco. Grazie a tutti dell'aiuto.
In un poligono di n lati, con n numero primo, la rotazione di 1 porta la colorazione a sovrapporsi a se stessa solamente nel caso di tutti i lati colorati di bianco o tutti i lati colorati di nero (le colorazioni banali), ma nel caso di n numero primo qualsiasi rotazione di k e riconducibile alla rotazione di 1 e pertanto tranne le 2 classi di equivalenza delle colorazioni banali che sono composte da 1 elemento ciascuno, tutte le altre sono cpmposte da n elementi.
Nel caso di un poligono con n lati dove n non è un numero primo, entrano in gioco i divisori. Nel caso dell'esagono 1, 2, 3 e 6.
Per cercare di dare una soluzione all'esercizio:
------ Calcolo le colorazioni di classe 6
ncolclas6 = 2^6 [insieme possib.coloraz.] - (2^3-2)[insieme coloraz.polig.3 lati (divis.2?)] - (2^2-2)[insieme coloraz.polig.2 lati (divisore 3?)]-2[coloraz.banali]/6
ncolclas6 = (64 - 6 -2 - 2)/6 = 9
------ Calcolo le colorazioni di classe 3 [poligono con 3 lati, in realtà divisore 2?]
ncolclas3 = (2^3-2)/3 = 2
------ Calcolo le colorazioni di classe 2 [poligono con 2 lati, in realtà divisore 3?]
ncolclas2 = (2^2-2)/2 = 1
----- Calcolo le colorazioni totali
ncolttotali = ncolclas6 + nolclas3 + nclclas2 + numero colorazioni banali = 9 + 2 + 1 + 2 = 14
Spero il mio ragionamento sia corretto anche se 14 mi sembra un pò poco. Grazie a tutti dell'aiuto.
Re: Poligoni regolari e colorazione dei lati
Mi sembra tutto giusto, ma non sono ancora sicuro che abbiate capito al 100% l'idea dietro.
Giusto per capirci: se tu avessi per esempio un poligono con 18 lati, che forma avrebbe la prima delle tue equazioni? Quali termini dovrebbero comparire?
Di quello che ha scritto wall98: perché quindi in un poligono di 6 lati non posso avere una colorazione che si ripete dopo una rotazione lunga 4? Cosa succede in quel caso? Come si dimostra questa cosa in generale?
Giusto per capirci: se tu avessi per esempio un poligono con 18 lati, che forma avrebbe la prima delle tue equazioni? Quali termini dovrebbero comparire?
Di quello che ha scritto wall98: perché quindi in un poligono di 6 lati non posso avere una colorazione che si ripete dopo una rotazione lunga 4? Cosa succede in quel caso? Come si dimostra questa cosa in generale?
--federico
[tex]\frac1{\sqrt2}\bigl(\left|\text{loves me}\right\rangle+\left|\text{loves me not}\right\rangle\bigr)[/tex]
[tex]\frac1{\sqrt2}\bigl(\left|\text{loves me}\right\rangle+\left|\text{loves me not}\right\rangle\bigr)[/tex]
Re: Poligoni regolari e colorazione dei lati
In effetti a ragione fph, credo di aver capito a grandi linee il meccanismo, intravedo qualcosa che va oltre il risultato, ma non ho la teoria e forse la capacità di dimostrarlo (ho finito da poco la terza media e mi stò aiutando con degli appunti che ho trovato su internet)
Comunque nel caso con il poligono da 18 lati:
colposs18 = (2^18-[2^9-(2^3-2)-2]-[2^6-(2^3-2)-(2^2-2)-2]-[2^3-2]-[2ì2-2]-2)/18 (numero classi da 18
colposs18 = colposs18 + ((2^9-(2^3-2)-2)/9) (aggiungo le classi da 9)
colposs18 = colposs18 + ((2^6-(2^3-2)-(2^2-2)-2)/6) (aggiungo le classi da 6)
continuo aggiungendo i numeri delle classi da 3, da 2 e le 2 colorazioni banali e dovrei trovare:
colpos18 = 14532 + 56 + 9 + 2 + 1 + 2 = 14602
Il numero mi sembra grande, sicuramemente avrò commesso degli errori.
Comunque nel caso con il poligono da 18 lati:
colposs18 = (2^18-[2^9-(2^3-2)-2]-[2^6-(2^3-2)-(2^2-2)-2]-[2^3-2]-[2ì2-2]-2)/18 (numero classi da 18
colposs18 = colposs18 + ((2^9-(2^3-2)-2)/9) (aggiungo le classi da 9)
colposs18 = colposs18 + ((2^6-(2^3-2)-(2^2-2)-2)/6) (aggiungo le classi da 6)
continuo aggiungendo i numeri delle classi da 3, da 2 e le 2 colorazioni banali e dovrei trovare:
colpos18 = 14532 + 56 + 9 + 2 + 1 + 2 = 14602
Il numero mi sembra grande, sicuramemente avrò commesso degli errori.
Re: Poligoni regolari e colorazione dei lati
Qualcuno può dirmi se il ragionamento è corretto oppure no.
Grazie per la pazienza.
Grazie per la pazienza.
Re: Poligoni regolari e colorazione dei lati
Non ho verificato i calcoli, ma fino alle formule mi sembra tutto giusto!
--federico
[tex]\frac1{\sqrt2}\bigl(\left|\text{loves me}\right\rangle+\left|\text{loves me not}\right\rangle\bigr)[/tex]
[tex]\frac1{\sqrt2}\bigl(\left|\text{loves me}\right\rangle+\left|\text{loves me not}\right\rangle\bigr)[/tex]
-
- Messaggi: 232
- Iscritto il: 07 mag 2012, 11:51
Re: Poligoni regolari e colorazione dei lati
Propongo una soluzione al caso generale, con $a$ colori ed $n$ lati, senza far uso del lemma di Burnside, soltanto con strumenti olimpici.
Chiamiamo $P(n)$ il numero di colorazioni di un poligono di $n$ lati a meno di rotazioni. Data una stringa di colori (a scelta tra $a$), diciamo che una stringa ha periodo $d$ se $d$ è il minimo numero di rotazioni per tornare alla stringa iniziale. Si ha allora che il periodo di una stringa di lunghezza $n$ è un divisore di $n$ (infatti se dopo $d$ rotazioni si torna alla situazione iniziale vuol dire che le ultime due sottostringhe di lunghezza $d$ erano uguali, ma allora anche le ultime tre, e così via).
Chiamiamo $S(d)$ il numero di stringhe di periodo $d$. Abbiamo allora che
$$P(n)=\sum_{d|n} \frac{S(d)}{d}.$$
Poiché il numero di tutte le stringhe di lunghezza $n$ è $a^n$, si ha che
$$a^n=\sum_{d|n} S(d)$$
e per l'inversione di Möbius
$$S(d)=\sum_{\ell |d}\mu(\ell) a^{d/\ell}.$$
Pertanto
$$P(n)=\sum_{d|n}\frac{1}{d}\sum_{\ell |d}\mu(\ell) a^{d/\ell}=\frac{1}{n}\sum_{\ell |n}\left(\sum_{d|\ell}\mu(d)\frac{\ell}{d}\right)a^{n/\ell}.$$
L'ultima uguaglianza è conseguenza dell'associatività delle convoluzioni. Ricordiamo che $\ell=\sum_{d|\ell} \varphi(d)$ (per una dimostrazione vedi qui), allora nuovamente per l'inversione di Möbius
$$\varphi(\ell)=\sum_{d|\ell}\mu(d)\frac{\ell}{d}.$$
In conclusione
$$P(n)=\frac{1}{n}\sum_{\ell |n}\varphi(\ell)a^{n/\ell}.$$
Chiamiamo $P(n)$ il numero di colorazioni di un poligono di $n$ lati a meno di rotazioni. Data una stringa di colori (a scelta tra $a$), diciamo che una stringa ha periodo $d$ se $d$ è il minimo numero di rotazioni per tornare alla stringa iniziale. Si ha allora che il periodo di una stringa di lunghezza $n$ è un divisore di $n$ (infatti se dopo $d$ rotazioni si torna alla situazione iniziale vuol dire che le ultime due sottostringhe di lunghezza $d$ erano uguali, ma allora anche le ultime tre, e così via).
Chiamiamo $S(d)$ il numero di stringhe di periodo $d$. Abbiamo allora che
$$P(n)=\sum_{d|n} \frac{S(d)}{d}.$$
Poiché il numero di tutte le stringhe di lunghezza $n$ è $a^n$, si ha che
$$a^n=\sum_{d|n} S(d)$$
e per l'inversione di Möbius
$$S(d)=\sum_{\ell |d}\mu(\ell) a^{d/\ell}.$$
Pertanto
$$P(n)=\sum_{d|n}\frac{1}{d}\sum_{\ell |d}\mu(\ell) a^{d/\ell}=\frac{1}{n}\sum_{\ell |n}\left(\sum_{d|\ell}\mu(d)\frac{\ell}{d}\right)a^{n/\ell}.$$
L'ultima uguaglianza è conseguenza dell'associatività delle convoluzioni. Ricordiamo che $\ell=\sum_{d|\ell} \varphi(d)$ (per una dimostrazione vedi qui), allora nuovamente per l'inversione di Möbius
$$\varphi(\ell)=\sum_{d|\ell}\mu(d)\frac{\ell}{d}.$$
In conclusione
$$P(n)=\frac{1}{n}\sum_{\ell |n}\varphi(\ell)a^{n/\ell}.$$
-
- Messaggi: 486
- Iscritto il: 01 lug 2011, 22:52
Re: Poligoni regolari e colorazione dei lati
Dimostrazione molto elegante, complimenti. Posso chiederti cos'è l'inversione di Mobius?
\( \displaystyle \sigma(A,G) \ \ = \sum_{Y \in \mathscr{P}(A) } \dot{\chi_{|G|} } (Y) \) bum babe
-
- Messaggi: 232
- Iscritto il: 07 mag 2012, 11:51
Re: Poligoni regolari e colorazione dei lati
Beh, di certo non saprei enunciartela meglio di wiki, quindi vedi qui. Una dimostrazione ne è stata data anche su questo forum, click. Se poi ti interessa sulle dispense del Sato c'è un po' di teoria sulle convoluzioni di Dirichlet e anche una dimostrazione molto bella dell'inversione di Möbius.Gottinger95 ha scritto:Dimostrazione molto elegante, complimenti. Posso chiederti cos'è l'inversione di Mobius?