Ordine di una permutazione $p$
Ciao a tutti!
Qualche giorno fa giocherellando con le fiches (o le chips) di poker con alcuni colleghi, è sorto un quesito (ed essendo io il matematico di turno sono stato incaricato di rispondere
).
Supponiamo di avere un numero pari $n$ di fiches, metà bianche e metà nere, e di dividerle in una pila bianca e una pila nera. Avvicinando le due pile l'una all'altra, con un gioco di abilità della mano, è possibile "mischiarle", ovvero creare un'unica pila di $n$ fiches composta in successione da una fiche bianca, una nera, una bianca, una nera, etc...
A parte l'abilità di riuscire a farlo con una mano, ci siamo chiesti cosa succede a iterare il procedimento, ovvero una volta ottenuta la nuova pila di $n$ fiches, tagliarla in due, avvicinare le due pile più piccole ottenute, e rimischiarle ottenendo ancora la pila di $n$ fiches.
Ho avvisato subito che prima o poi le fiches sarebbero tornate alla posizione di partenza, dato che la composizione di una permutazione $p$ con sè stessa è tale che $p^{\text{ord}(p)}=1_{\text{id}}$ ($p$ è la "mischiata" come descritto sopra).
Quello che però ci ha sorpreso è come varia l'ordine di $p$ al variare di $n$... riporto i risultati (ottenuti semplicemente provando) che abbiamo ottenuto per $n$ piccolo
\[
\begin{matrix}
n & \text{ord}(p) \\
2 & 1 \\
4 & 2 \\
6 & 4 \\
8 & 3 \\
10 & 6 \\
12 & 10
\end{matrix}
\]
In poco tempo abbiamo dedotto che se $n=2^k$, allora $\text{ord}(p)=k$, e per dedurre questo basta un po' di logica, senza nemmeno sapere cosa sia un gruppo. Quello che però non sono riuscito a spiegare è l'andamento così "strambo" (o almeno per me) del valore di $\text{ord}(p)$ al variare di $n$. Un altro passo che ho fatto (ma che non mi sembra molto utile) è dedurre la posizione dopo la mischiata di una fiche che inizialmente occupava la posizione $j$ nella pila di $n$ fiches. In formule
\[
p(j)=
\left\{
\begin{matrix}
2j-1 & \text{se } 1\leq j\leq n/2 \\
2j-n & \text{se } n/2+1 \leq j \leq n
\end{matrix}
\right.
\]
Qualcuno saprebbe illuminarmi? (prometto che sarò onesto e dirò ai miei colleghi di avervi chiesto aiuto )
Qualche giorno fa giocherellando con le fiches (o le chips) di poker con alcuni colleghi, è sorto un quesito (ed essendo io il matematico di turno sono stato incaricato di rispondere
).Supponiamo di avere un numero pari $n$ di fiches, metà bianche e metà nere, e di dividerle in una pila bianca e una pila nera. Avvicinando le due pile l'una all'altra, con un gioco di abilità della mano, è possibile "mischiarle", ovvero creare un'unica pila di $n$ fiches composta in successione da una fiche bianca, una nera, una bianca, una nera, etc...
A parte l'abilità di riuscire a farlo con una mano, ci siamo chiesti cosa succede a iterare il procedimento, ovvero una volta ottenuta la nuova pila di $n$ fiches, tagliarla in due, avvicinare le due pile più piccole ottenute, e rimischiarle ottenendo ancora la pila di $n$ fiches.
Ho avvisato subito che prima o poi le fiches sarebbero tornate alla posizione di partenza, dato che la composizione di una permutazione $p$ con sè stessa è tale che $p^{\text{ord}(p)}=1_{\text{id}}$ ($p$ è la "mischiata" come descritto sopra).
Quello che però ci ha sorpreso è come varia l'ordine di $p$ al variare di $n$... riporto i risultati (ottenuti semplicemente provando) che abbiamo ottenuto per $n$ piccolo
\[
\begin{matrix}
n & \text{ord}(p) \\
2 & 1 \\
4 & 2 \\
6 & 4 \\
8 & 3 \\
10 & 6 \\
12 & 10
\end{matrix}
\]
In poco tempo abbiamo dedotto che se $n=2^k$, allora $\text{ord}(p)=k$, e per dedurre questo basta un po' di logica, senza nemmeno sapere cosa sia un gruppo. Quello che però non sono riuscito a spiegare è l'andamento così "strambo" (o almeno per me) del valore di $\text{ord}(p)$ al variare di $n$. Un altro passo che ho fatto (ma che non mi sembra molto utile) è dedurre la posizione dopo la mischiata di una fiche che inizialmente occupava la posizione $j$ nella pila di $n$ fiches. In formule
\[
p(j)=
\left\{
\begin{matrix}
2j-1 & \text{se } 1\leq j\leq n/2 \\
2j-n & \text{se } n/2+1 \leq j \leq n
\end{matrix}
\right.
\]
Qualcuno saprebbe illuminarmi? (prometto che sarò onesto e dirò ai miei colleghi di avervi chiesto aiuto
)
Risposte
Mi pare che qualcosa di simile sia comparso, non molto tempo fa, nella sezione "Giochi" ...
Prova a guardare questa ...
Prova a guardare questa ...
Eh sì il problema mi sembra lo stesso... però non capisco se la risposta "NO" alla domanda b) deriva dal fatto che non ha trovato una formula generale oppure dal fatto che tale formula non può esistere.
Nel frattempo ho fatto un'ulteriore osservazione: per come è definita $p$, si ha che (non so se questo semplifica o complica le cose )
\[
p^k(j)=2^k j-\sum_{i=1}^k 2^{k-i}f(i)
\]
con
\[
f(i)=
\left\{
\begin{matrix}
1 & \text{se } 1\leq p^{i-1}(j) \leq n/2 \\
n & \text{se } n/2+1 \leq p^{i-1}(j) \leq n
\end{matrix}
\right.
.
\]
In pratica il problema è trovare $k$ tale che $p^k(j)=j$ per ogni $j=1,\ldots,n$.
Nel frattempo ho fatto un'ulteriore osservazione: per come è definita $p$, si ha che (non so se questo semplifica o complica le cose
)\[
p^k(j)=2^k j-\sum_{i=1}^k 2^{k-i}f(i)
\]
con
\[
f(i)=
\left\{
\begin{matrix}
1 & \text{se } 1\leq p^{i-1}(j) \leq n/2 \\
n & \text{se } n/2+1 \leq p^{i-1}(j) \leq n
\end{matrix}
\right.
.
\]
In pratica il problema è trovare $k$ tale che $p^k(j)=j$ per ogni $j=1,\ldots,n$.
Mi pare che intenda dire che "non esiste" ma prova a chiederglielo ... 
... in quel thread o direttamente ...
... in quel thread o direttamente ...
Ok 
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo