Newsgroup: it.hobby.enigmi
Titolo: Permutazioni Scalabili

N cavalieri si siedono attorno ad un tavolo rotondo.
Una permutazione circolare dei primi N numeri e' scritta sul tavolo (un 
numero in corrispondenza di ciascun posto).
A questo punto i cavalieri si rialzano e scalano verso sinistra di tanti 
posti come indicato dal proprio numero. Se non ci sono sovrapposizioni e 
tutti i cavalieri trovano il nuovo posto libero, avremo avuto una 
Permutazione Scalabile.
Per quali N questo e' posssibile ?
dario

"Dario Uri" ha scritto

Ho trovato una soluzione parziale
[spoiler]
.
.
.
.
.
.
.
.
Si trova facilmente che per N dispari è possibile. basta disporre i numeri
in ordine 1,2,3,...N.
In questo modo i cavalieri con posizione <N/2 troveranno raddoppiata la loro
posizione e andranno a occupare nell'ordine tutte le posizioni pari; gli
altri occuperanno nell'ordine le posizioni dispari.
Per esempio, per N=7:
7 6 5 4 3 2 1
g f e d C B A    posizioni iniziali
g C f B e A d    posizioni finali
Se N è pari la cosa non funziona, perché tutti finirebbero in posizioni
pari. Bisogna comunque vedere se è possibile con una permutazione diversa.
Mi pare di poter dimostrare che la cosa non è comunque possibile se N=2(mod
4).
Supponiamo di assegnare a ciascun posto una doppia etichetta: quella reale
(descritta nel problema) ed una virtuale, indicante la posizione ordinata
(1,2,...N) a partire da un'origine arbitraria.
I cavalieri con etichetta reale pari si spostano di un numero pari di
posizioni, quindi andranno a trovare un'etichetta virtuale che avrà la
stessa parità di quella di partenza.
I cavalieri con etichetta reale dispari troveranno invece un'etichetta
virtuale di parità opposta a quella di partenza.
Per non avere sovrapposizioni di posti, è necessario che gli spostamenti da
pari a dispari siano tanti quanti quelli da dispari a pari, quindi le
etichette virtuali dispari devono essere in numero pari (scusate il
bisticcio di parole), e le etichette totali N devono essere in numero
multiplo di quattro.
Ossia, per N pari, condizione necessaria perché la cosa funzioni è che N sia
multiplo di quattro.
Non è detto che la condizione sia anche sufficiente, anzi per N=4 la brute
foece mi dice che non è possibile.
La cosa è da approfondire.
ciao
paolo

 La cosa è da approfondire.
Ho approfondito, e, salvo errori, trovo che con N pari non si possono avere
permutazioni scalabili.
[spoiler]
.
.
.
.
.
.
.
.
.
Consideriamo un gruppo di K cavalieri che occupano le posizioni A, B,
C,...K, tali che da A ci si sposti a B, da B a C, ... da K ad A.
Considerato che il cavaliere N torna comunque alla posizione di partenza,
dopo aver fatto un giro completo del tavolo, per avere una permutazione
scalabile i rimanenti N-1 cavalieri dovranno necessariamente potersi
raggruppare in uno o più gruppi del tipo di quello A...K descritto, che
comunque non devono avere elementi in comune.
Sommando per ciascun gruppo gli archi AB, BC, ... KA, si ottiene un numero
intero di giri (da A ad A) e quindi la somma vale 0 (mod N). Anche la somma
di tutti i gruppi deve quindi essere 0 (mod N).
Ma la somma di tutti i gruppi corrisponde alla somma dei numeri 1, 2, ... N,
ossia
N*(N+1)/2
Si verifica che:
_ Se N è dispari, la somma è multipla di N.
_ Se N è pari, la somma vale (N/2) (mod N)
e quindi la permutazione non può essere scalabile.
s.e.o.o.
ciao
paolo

.

Guarda cosa ti sembra questa velocissima per i dispari:
Ogni N dispari e` senz'altro scalabile, infatti considerando
inizialmente la posizione naturale: 1,2,3,..,n si vede che:
A)	n-i -> n-2i		per i da 0 a (n+1)/2
B)	n-i -> n-[2i modulo(n)]	per i restanti fino alla fine.
e si vede che i numeri A son tutti dispari e diversi, mentre
invece i numeri B son tutti i rimanenti pari.
esempio:
A)
5->5
4->3
3->1
B)
2-> 5-6 = 5-1 = 4
1->2
Ma per i pari non so.. d'altra parte la tua sembra OK:-)
-- 
Ci sentiamo, |  Remigio Zedda  || Attenzione! campo "From:" alterato
ciao Remigio |                 ||  ==>   E-mail: 
remi...@tiscali.it
-------------|     ..si` d'accordo.. ma con la Deb e` un'altra cosa!
/* Linux 2.2.19pre17 su Debian GNU/Linux 2.2 Potato */

 invece i numeri B son tutti i rimanenti pari.
Ho guardato anch'io il problema, e credo di poter generalizzare questo risultato.
(1) tutte le disposizioni della forma
posizione_di_k = t*k(mod n) per qualunque t=1..N-2 sono soluzioni
messa cosi' non si capisce nulla, ma es. N=5
1 2 3 4 5 t=1
3 1 4 2 5 t=2
2 4 1 3 5 t=3
e' piu' chiaro, no ?
t=1 da' la soluzione del buon Paolo, t=2 le tue.
Nella realta' esistono molte piu' soluzioni e non riconducibili a schemi,
gia' per N=7 (bforce) le soluzioni 'fioccano'.
(2) Per qualunque soluzione ne esiste una 'duale'
che si ottiene se per ogni ciclo presente se "se ne inverte 
il senso di percorrenza", piu' difficile da spiegare che fare :
esempio N=7
5 2 6 1 3 4 7 si puo' vedere che c'e' un ciclo da 6, 5-->4-->6-->..., che diventa
4 1 3 5 6 2 7 col ciclo ribaltato 2<--4<--3<--...
Le soluzioni di (1) sono duali tra loro, e ce n'e' una (e solo una tra *tutte*,
e' facile verificarlo) auto-duale, che e' quella per t=(N-1)/2.
(3) Per qualsiasi N dispari il numero di soluzioni totali e' dispari
(Questa la lascio ai volenterosi)
(4) la probabilita' che una perm. circolare presa a caso sia anche scalabile
e' stimabile grossolanamente come e^(-N)
Ciao^2.

 invece i numeri B son tutti i rimanenti pari.
Ho guardato anch'io il problema, e credo di poter generalizzare questo risultato.
(1) tutte le disposizioni della forma
posizione_di_k = t*k(mod n) per qualunque t=1..N-2 sono soluzioni
messa cosi' non si capisce nulla, ma es. N=5
1 2 3 4 5 t=1
3 1 4 2 5 t=2
2 4 1 3 5 t=3
e' piu' chiaro, no ?
t=1 da' la soluzione del buon Paolo, t=N-2 le tue.


 invece i numeri B son tutti i rimanenti pari.
Ho guardato anch'io il problema, e credo di poter generalizzare questo risultato.
(1) tutte le disposizioni della forma
posizione_di_k = t*k(mod n) per qualunque t=1..N-2 sono soluzioni
messa cosi' non si capisce nulla, ma es. N=5
1 2 3 4 5 t=1
3 1 4 2 5 t=2
2 4 1 3 5 t=3
e' piu' chiaro, no ?
t=1 da' la soluzione del buon Paolo, mentre t=2 le tue.


 e' facile verificarlo) auto-duale, che e' quella per t=(N-1)/2.
Non e' vero, ne esistono altre.
Questa soluzione auto-duale pero' esiste sempre.
Ciao^2, SE&O.

scalabili per N multiplo di 3 :-(
Da me viene anche adesso, guarda con 9: 
Tipo B:
1..2
2..4
3..6
4..8
Tipo A:
5..1
6..3
7..5
8..7
9..9
forse non avevo scritto del tutto chiaro:-(
poi stasera con calma guardo le tue espressioni:-)


 9..9
se ho compreso bene viene
1 2 3 4 5 6 7 8 9
5 1 6 2 7 3 8 4 9
che non e' scalabile : il 3 ed il 9 collidono
(Sto scaoppando, spero sia giusta :-(( )