Coloriamo altre cose

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

Coloriamo altre cose

Messaggio da matpro98 » 09 nov 2016, 19:45

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: 198
Iscritto il: 08 set 2016, 22:01

Re: Coloriamo altre cose

Messaggio da Sirio » 09 nov 2016, 20:18

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: 401
Iscritto il: 22 feb 2014, 18:42

Re: Coloriamo altre cose

Messaggio da matpro98 » 09 nov 2016, 20:27

Attento che a seconda di come sistemi l'ultimo hint potrebbe anche essere incompleta/sbagliata come soluzione

Vinci
Messaggi: 149
Iscritto il: 30 gen 2015, 18:38

Re: Coloriamo altre cose

Messaggio da Vinci » 09 nov 2016, 21:06

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: 123
Iscritto il: 05 gen 2015, 01:07

Re: Coloriamo altre cose

Messaggio da mr96 » 09 nov 2016, 21:18

E qui mi sa che bisognerebbe invocare il buon Lasker... :lol: :lol:

matpro98
Messaggi: 401
Iscritto il: 22 feb 2014, 18:42

Re: Coloriamo altre cose

Messaggio da matpro98 » 09 nov 2016, 21:28

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: 329
Iscritto il: 02 mag 2013, 20:47
Località: Udine

Re: Coloriamo altre cose

Messaggio da Lasker » 09 nov 2016, 21:29

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: 123
Iscritto il: 05 gen 2015, 01:07

Re: Coloriamo altre cose

Messaggio da mr96 » 09 nov 2016, 21:35

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: 401
Iscritto il: 22 feb 2014, 18:42

Re: Coloriamo altre cose

Messaggio da matpro98 » 09 nov 2016, 21:43

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: 123
Iscritto il: 05 gen 2015, 01:07

Re: Coloriamo altre cose

Messaggio da mr96 » 09 nov 2016, 21:44

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:

Gerald Lambeau
Messaggi: 290
Iscritto il: 17 mag 2015, 13:32

Re: Coloriamo altre cose

Messaggio da Gerald Lambeau » 09 nov 2016, 22:24

Potrei fortemente essere nel torto, ma può darsi che sia
Testo nascosto:
$(k-1)^n+(1-k)\cdot(-1)^{n-1}$
?
"Non ho rispetto per i miei superiori, figurati se ho rispetto per i miei pari: il rispetto di un uomo lo merita solo chi è a lui inferiore."
Cit. Marco (mio vero nome)

The Game.

Ci sono cose che non si possono confutare; per tutto il resto, c'è la fisica.

matpro98
Messaggi: 401
Iscritto il: 22 feb 2014, 18:42

Re: Coloriamo altre cose

Messaggio da matpro98 » 09 nov 2016, 22:30

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

Gerald Lambeau
Messaggi: 290
Iscritto il: 17 mag 2015, 13:32

Re: Coloriamo altre cose

Messaggio da Gerald Lambeau » 09 nov 2016, 22:51

Ottimo, domani scrivo la soluzione.
"Non ho rispetto per i miei superiori, figurati se ho rispetto per i miei pari: il rispetto di un uomo lo merita solo chi è a lui inferiore."
Cit. Marco (mio vero nome)

The Game.

Ci sono cose che non si possono confutare; per tutto il resto, c'è la fisica.

Gerald Lambeau
Messaggi: 290
Iscritto il: 17 mag 2015, 13:32

Re: Coloriamo altre cose

Messaggio da Gerald Lambeau » 10 nov 2016, 15:52

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).
"Non ho rispetto per i miei superiori, figurati se ho rispetto per i miei pari: il rispetto di un uomo lo merita solo chi è a lui inferiore."
Cit. Marco (mio vero nome)

The Game.

Ci sono cose che non si possono confutare; per tutto il resto, c'è la fisica.

Vinci
Messaggi: 149
Iscritto il: 30 gen 2015, 18:38

Re: Coloriamo altre cose

Messaggio da Vinci » 13 nov 2016, 19:04

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

Chi c’è in linea

Visitano il forum: Nessuno e 2 ospiti