Poligoni regolari e colorazione dei lati

Conteggi, probabilità, invarianti, logica, matematizzazione, ...
acs
Messaggi: 25
Iscritto il: 18 lug 2013, 08:40

Poligoni regolari e colorazione dei lati

Messaggio da acs »

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.
Avatar utente
simone256
Messaggi: 452
Iscritto il: 07 mag 2012, 16:10
Località: Crema

Re: Poligoni regolari e colorazione dei lati

Messaggio da simone256 »

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... :cry: ... Prova a dare un'occhiata al link sopra! :wink:
$ \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
EvaristeG
Site Admin
Messaggi: 4896
Iscritto il: 01 gen 1970, 01:00
Località: Roma
Contatta:

Re: Poligoni regolari e colorazione dei lati

Messaggio da EvaristeG »

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
  • 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.
- i punti 1. e 2. rimangono veri per un poligono con un numero generico di lati;
- 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.
fph
Site Admin
Messaggi: 3956
Iscritto il: 01 gen 1970, 01:00
Località: in giro
Contatta:

Re: Poligoni regolari e colorazione dei lati

Messaggio da fph »

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. :shock:
--federico
[tex]\frac1{\sqrt2}\bigl(\left|\text{loves me}\right\rangle+\left|\text{loves me not}\right\rangle\bigr)[/tex]
wall98
Messaggi: 167
Iscritto il: 27 mar 2013, 11:23
Località: Roma

Re: Poligoni regolari e colorazione dei lati

Messaggio da wall98 »

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$
mi potresti chiarire il senso di rotazione non banale?

poi il resto tanto vale metterlo in spoiler, anche se non ha molto senso..
Testo nascosto:
@EvaristeG
2:
basta dire che dopo una rotazione di p elementi ritroviamo la stessa configurazione, quindi se la classe ha meno di p elementi, diciamo che ne ha X,essa dopo essere stata ripetuta k volte deve essere sulla configurazione iniziale,dove k è il numero di elementi, cioè $ xk=p $? (e questo è tranquillamente estendibile a un numero n)
3:
si dice che dato che il numero di elementi della classe divide p, essa puo essere o 1 o p, quindi dato che è minore di p, essa deve essere 1, cioè la configurazione banale?
n=pq lati:
possiamo semplicemente dire "prendiamo un qualsiasi elemento di una classe con p elementi, allora possiamo "separare questo elemento in q parti, q parti equivalenti", poiche q è il numero degli elementi ecc. (vedere la parte xk=p),a questo punto abbiamo finito, perche se abbiamo tutti elementi equivalenti con p lettere, allora ne prendiamo uno è abbiamo ottenuto un elemento di una colorazione a p lati, il bello è che cosi possiamo ottenere TUTTI - 2 gli elementi della nuova colorazione (tutti meno due perche se prendiamo le colorazioni banali, non possiamo ottenere in nessun modo,affiancando altri pezzi,un elemento di classe p). per esempio dato l'elemento $ bnnbnn $ appartenente ad una classe con 3 elementi,possiamo dividerlo in $ bnn,bnn $,e notiamo come data una configurazione del primo(aggiungendo o togliendo delle b),con una sola configurazione del secondo si ha che l'elemento che si forma è di classe 3 (questo fatto vale anche piu in generale per q elementi di lunghezza p,come si dimostra?),quindi abbiamo tutti gli elementi di una colorazione a 3 meno le due banali
@FPH
b)
ora dimostrazione bastar.. piuttosto scorretta del PTF, allora innanzitutto diciamo che $ \displaystyle \frac{a^p-a}{p}+a $ è il numero di modi per colorare con a colori un poligono con P primo lati (la dimostrazione è semplice,si basa sulla stessa idea di acs per due colori),che ovviamente è intero, allora anche $ \displaystyle \frac{a^p-a}{p} $ è intero, quindi $ \displaystyle a^p \equiv a \pmod{p} $ che è la tesi
a)
ora dimostriamo 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, per fare questo intanto diciamo che le sequenze non banali non possono appartenere a una classe con 1 elemento,se cosi fosse significa che con una rotazione si otterrebbe la stessa sequenza,assurdo! quindi dimostriamo che se la sequenza appartiene ad una classe con meno di n elementi, allora il numero di elementi nella classe divide n,cio è banalmente vero per lo stesso motivo di prima, cioè che dopo p rotazioni la sequenza sara la stessa di partenza, quindi il numero X di elementi nella classe deve essere del tipo $ xk=p $

Stupefacente quanto sia incasinata questa dimostrazione
Il problema non è il problema, il problema sei tu.
fph
Site Admin
Messaggi: 3956
Iscritto il: 01 gen 1970, 01:00
Località: in giro
Contatta:

Re: Poligoni regolari e colorazione dei lati

Messaggio da fph »

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]
wall98
Messaggi: 167
Iscritto il: 27 mar 2013, 11:23
Località: Roma

Re: Poligoni regolari e colorazione dei lati

Messaggio da wall98 »

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)?
Il problema non è il problema, il problema sei tu.
acs
Messaggi: 25
Iscritto il: 18 lug 2013, 08:40

Re: Poligoni regolari e colorazione dei lati

Messaggio da acs »

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.
fph
Site Admin
Messaggi: 3956
Iscritto il: 01 gen 1970, 01:00
Località: in giro
Contatta:

Re: Poligoni regolari e colorazione dei lati

Messaggio da fph »

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?
--federico
[tex]\frac1{\sqrt2}\bigl(\left|\text{loves me}\right\rangle+\left|\text{loves me not}\right\rangle\bigr)[/tex]
acs
Messaggi: 25
Iscritto il: 18 lug 2013, 08:40

Re: Poligoni regolari e colorazione dei lati

Messaggio da acs »

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.
acs
Messaggi: 25
Iscritto il: 18 lug 2013, 08:40

Re: Poligoni regolari e colorazione dei lati

Messaggio da acs »

Qualcuno può dirmi se il ragionamento è corretto oppure no.

Grazie per la pazienza.
fph
Site Admin
Messaggi: 3956
Iscritto il: 01 gen 1970, 01:00
Località: in giro
Contatta:

Re: Poligoni regolari e colorazione dei lati

Messaggio da fph »

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]
Ido Bovski
Messaggi: 232
Iscritto il: 07 mag 2012, 11:51

Re: Poligoni regolari e colorazione dei lati

Messaggio da Ido Bovski »

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}.$$
Gottinger95
Messaggi: 486
Iscritto il: 01 lug 2011, 22:52

Re: Poligoni regolari e colorazione dei lati

Messaggio da Gottinger95 »

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
Ido Bovski
Messaggi: 232
Iscritto il: 07 mag 2012, 11:51

Re: Poligoni regolari e colorazione dei lati

Messaggio da Ido Bovski »

Gottinger95 ha scritto:Dimostrazione molto elegante, complimenti. Posso chiederti cos'è l'inversione di Mobius?
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.
Rispondi