Coloriamo altre cose

Conteggi, probabilità, invarianti, logica, matematizzazione, ...
matpro98
Messaggi: 479
Iscritto il: 22 feb 2014, 18:42

Coloriamo altre cose

Messaggio da matpro98 »

Sia $P_1P_2\dots P_n$ un $n$-agono regolare ($n \geq 3$) e sia $O$ il suo centro. In quanti modi posso colorare ogni regione $OP_iP_{i+1}$ ($1 \leq i \leq n, \ n+1=1$) con $k$ colori in modo che due regioni adiacenti siano colorate diversamente?
Avatar utente
Sirio
Messaggi: 317
Iscritto il: 08 set 2016, 22:01

Re: Coloriamo altre cose

Messaggio da Sirio »

Qualche hint
Testo nascosto:
In quanti modi posso scegliere il colore della prima regione?
Testo nascosto:
In quanti modi posso scegliere il colore della seconda regione, una volta che ho scelto quello della prima?
Testo nascosto:
E tutte le altre regioni?
Testo nascosto:
Come sistemo il fatto che $n+1=1$?
$T=\sqrt{\dfrac l g 12\pi}$
matpro98
Messaggi: 479
Iscritto il: 22 feb 2014, 18:42

Re: Coloriamo altre cose

Messaggio da matpro98 »

Attento che a seconda di come sistemi l'ultimo hint potrebbe anche essere incompleta/sbagliata come soluzione
Vinci
Messaggi: 159
Iscritto il: 30 gen 2015, 18:38

Re: Coloriamo altre cose

Messaggio da Vinci »

Non ho molto tempo stasera per scriver la soluzione, ma giusto per sapere se lo ho fatto bene, per caso è
Testo nascosto:
$$k(k-1)^{n-2}(k-2)$$?
mr96
Messaggi: 151
Iscritto il: 05 gen 2015, 01:07

Re: Coloriamo altre cose

Messaggio da mr96 »

E qui mi sa che bisognerebbe invocare il buon Lasker... :lol: :lol:
matpro98
Messaggi: 479
Iscritto il: 22 feb 2014, 18:42

Re: Coloriamo altre cose

Messaggio da matpro98 »

Vinci ha scritto:Non ho molto tempo stasera per scriver la soluzione, ma giusto per sapere se lo ho fatto bene, per caso è
Testo nascosto:
$$k(k-1)^{n-2}(k-2)$$?
No, mi spiace.
mr96 ha scritto:E qui mi sa che bisognerebbe invocare il buon Lasker... :lol: :lol:
Non invochiamolo sempre, altrimenti si sente importante :lol: e poi non è un problema tanto impossibile da renderlo necessario :lol:
Avatar utente
Lasker
Messaggi: 440
Iscritto il: 02 mag 2013, 20:47
Località: Udine

Re: Coloriamo altre cose

Messaggio da Lasker »

Cavatevela da soli insomma.

PS: mr96 guarda che sei tu il mio mentore in campo burnside :lol:
"Una funzione generatrice è una corda da bucato usata per appendervi una successione numerica per metterla in mostra" (Herbert Wilf)

"La matematica è la regina delle scienze e la teoria dei numeri è la regina della matematica" (Carl Friedrich Gauss)

Sensibilizzazione all'uso delle potenti Coordinate Cartesiane, possano seppellire per sempre le orride baricentriche corruttrici dei giovani: cur enim scribere tre numeri quando se ne abbisogna di due?

PRIMA FILA TUTTI SBIRRI!
mr96
Messaggi: 151
Iscritto il: 05 gen 2015, 01:07

Re: Coloriamo altre cose

Messaggio da mr96 »

Lasker ha scritto:Cavatevela da soli insomma.

PS: mr96 guarda che sei tu il mio mentore in campo burnside :lol:
Certo... :roll: :roll:

Comunque sono riuscito a invocarlo davvero, mi sento potente 8)

@matpro: più che altro è circa sempre lo stesso il problema...
matpro98
Messaggi: 479
Iscritto il: 22 feb 2014, 18:42

Re: Coloriamo altre cose

Messaggio da matpro98 »

mr96 ha scritto:
Lasker ha scritto:Cavatevela da soli insomma.

PS: mr96 guarda che sei tu il mio mentore in campo burnside :lol:
Certo... :roll: :roll:

Comunque sono riuscito a invocarlo davvero, mi sento potente 8)

@matpro: più che altro è circa sempre lo stesso il problema...
Se ti riferisci al burnside, no:
Testo nascosto:
in questo caso non contano simmetrie e rotazioni :roll:
mr96
Messaggi: 151
Iscritto il: 05 gen 2015, 01:07

Re: Coloriamo altre cose

Messaggio da mr96 »

matpro98 ha scritto:
mr96 ha scritto:
Lasker ha scritto:Cavatevela da soli insomma.

PS: mr96 guarda che sei tu il mio mentore in campo burnside :lol:
Certo... :roll: :roll:

Comunque sono riuscito a invocarlo davvero, mi sento potente 8)

@matpro: più che altro è circa sempre lo stesso il problema...
Se ti riferisci al burnside, no:
Testo nascosto:
in questo caso non contano simmetrie e rotazioni :roll:
Ah avevo interpretato male allora, ok dai allora possiamo farcela anche senza Lasker :lol:
Avatar utente
Gerald Lambeau
Messaggi: 335
Iscritto il: 17 mag 2015, 13:32
Località: provincia di Lucca

Re: Coloriamo altre cose

Messaggio da Gerald Lambeau »

Potrei fortemente essere nel torto, ma può darsi che sia
Testo nascosto:
$(k-1)^n+(1-k)\cdot(-1)^{n-1}$
?
"If only I could be so grossly incandescent!"
matpro98
Messaggi: 479
Iscritto il: 22 feb 2014, 18:42

Re: Coloriamo altre cose

Messaggio da matpro98 »

Gerald Lambeau ha scritto:Potrei fortemente essere nel torto, ma può darsi che sia
Testo nascosto:
$(k-1)^n+(1-k)\cdot(-1)^{n-1}$
?
Giusto, ma io (opinione puramente personale) scriverei il secondo addendo in un altro modo; ciò non toglie che il risultato sia quello
Avatar utente
Gerald Lambeau
Messaggi: 335
Iscritto il: 17 mag 2015, 13:32
Località: provincia di Lucca

Re: Coloriamo altre cose

Messaggio da Gerald Lambeau »

Ottimo, domani scrivo la soluzione.
"If only I could be so grossly incandescent!"
Avatar utente
Gerald Lambeau
Messaggi: 335
Iscritto il: 17 mag 2015, 13:32
Località: provincia di Lucca

Re: Coloriamo altre cose

Messaggio da Gerald Lambeau »

Testo nascosto:
Cominciamo con una bella bigezione: vogliamo contare il numero di parole lunghe $n$ lettere, ciascuna scelta da un insieme di $k$ lettere date, tali che due lettere consecutive siano diverse e la prima e l'ultima lettera siano diverse. Ovviamente, dato un $n$-agono a ogni modo buono di colorare può essere assegnata una parola buona e viceversa, inoltre come sappiamo dalle ipotesi due configurazioni ottenibili per simmetria e/o rotazione l'una dall'altra, ma che a cose normali hanno almeno una regione colorata diversamente, sono da considerarsi distinte, quindi non avremo il problema di contare dei doppioni usando le lettere, dunque stiamo contando la cosa giusta!
Sia $B_n$ il numero di parole buone di $n$ lettere, e $C_n$ il numero di parole di $n$ lettere che non hanno lettere consecutive uguali, ma che hanno la prima e l'ultima lettera uguali.
Quanto vale $B_{n+1}$? Possiamo scegliere in $k-2$ modi la lettera da aggiungere a una delle $B_n$ parole buone ($-2$ perché dev'essere diversa da quella che prima era l'ultima e che ora sarà la penultima e dalla prima), oppure $k-1$ modi di scegliere la lettera da aggiungere a una delle $C_n$ parole non buone ($-1$ perché dev'essere diversa da quella che prima era l'ultima e che ora sarà la penultima e dalla prima, ma essendo in questo caso la stessa si toglie solo $1$ e non $2$), per un conto totale di $B_{n+1}=(k-2)B_n+(k-1)C_n$.
E $C_{n+1}$ quanto vale? Non possiamo formarlo dai $C_n$, altrimenti avrebbe l'ultima e la penultima lettera uguali, quindi dobbiamo formarlo dai $B_n$, e siccome la prima lettera dev'essere uguale all'ultima non abbiamo scelta, quindi $C_{n+1}=B_n$.
Dunque ci ricaviamo che $B_{n+1}=(k-2)B_n+(k-1)B_{n-1}$, inoltre è intuitivo che $B_3=k(k-1)(k-2)$ e possiamo, usando le relazioni trovate, tirar fuori che $B_4=k(k^3-4k^2+6k-3)$, dunque vi risparmio la risoluzione di questa ricorsione e vi scrivo subito che $B_n=(k-1)^n+(k-1)\cdot(-1)^n$ (ieri mi era venuto un risultato impostato in maniera diversa perché avevo fatto una ricorsione shiftata).
"If only I could be so grossly incandescent!"
Vinci
Messaggi: 159
Iscritto il: 30 gen 2015, 18:38

Re: Coloriamo altre cose

Messaggio da Vinci »

Mi interessa sapere come si risolve questa ricorsione, puoi scriverlo per favore, o indicarmi una lezione dei senior dove viene spiegato come risolvere ricorsioni del genere?
Rispondi