Newsgroup: it.hobby.enigmi
Titolo: Inversione di carte

Prendete un mazzo di n carte (n compreso tra 1 e un po' meno di infinito
:-) ), tutte coperte. Poi cominciate a fare la seguente serie di operazioni:
prendete la prima in alto, la girate e la rimettete sul mazzo; prendete poi
le prime due (compresa la prima appena girata), le girate e le mettete sul
mazzo; quindi le prime tre, ripetendo la stessa operazione e cosě via fino a
girarne n. A questo punto avete compiuto una mossa e vi ritroverete con le
carte un po' coperte e un po' scoperte. Ripetete tutta la suddetta serie di
operazioni per effettuare la mossa successiva e andate avanti cosě fino a
che il mazzo non ritorna tutto coperto.
Quante mosse occorrono per ogni valore di n?
Sono convinto che il problema non sia nuovo. Io perň non l'ho ancora
analizzato a fondo. Mi sono limitato a farne una simulazione al computer
verificando che ha delle caratteristiche interessanti. E' anche aperto a
possibili varianti: ci si potrebbe fermare quando le carte risultano tutte
girate dalla stessa parte e non necessariamente tutte coperte, e poi si
potrebbe considerare cosa ne č dell'ordine iniziale delle carte, ecc...
Ciao
Giorgio

 
Bye by SixaM 8-]


Non è così semplice. Ecco cosa succede con 9 carte. Ci vogliono 18 mosse a
riportarle allo stato originale. (Considera la carta 1 come quella in cima
al mazzo e le carte negative come carte scoperte). In realtà dopo 9 mosse ci
si ritrova con le carte tutte scoperte poi ci vogliono altre 9 mosse per
rimetterle coperte. In entrambi i casi le carte ritornano nell'ordine
iniziale.
1 2 3 4 5 6 7 8 9
-9 -7 -5 -3 -1 2 4 6 8
-8 -4 1 5 9 -7 -3 2 6
-6 3 -9 -1 8 -4 5 -7 2
-2 -5 -8 9 6 3 -1 -4 -7
7 1 -6 8 2 -5 9 3 -4
4 -9 -2 6 -7 1 8 -5 3
-3 -8 7 2 -4 -9 6 1 -5
5 -6 4 -7 3 -8 2 -9 1
-1 -2 -3 -4 -5 -6 -7 -8 -9
9 7 5 3 1 -2 -4 -6 -8
8 4 -1 -5 -9 7 3 -2 -6
6 -3 9 1 -8 4 -5 7 -2
2 5 8 -9 -6 -3 1 4 7
-7 -1 6 -8 -2 5 -9 -3 4
-4 9 2 -6 7 -1 -8 5 -3
3 8 -7 -2 4 9 -6 -1 5
-5 6 -4 7 -3 8 -2 9 -1
1 2 3 4 5 6 7 8 9
Ecco cosa succede con 10 carte:
1 2 3 4 5 6 7 8 9 10
-10 -8 -6 -4 -2 1 3 5 7 9
-9 -5 -1 4 8 -10 -6 -2 3 7
-7 2 10 -4 5 -9 -1 8 -6 3
-3 -8 9 4 -2 -7 10 5 -1 -6
6 -5 7 -4 8 -3 9 -2 10 -1
1 2 3 4 5 6 7 8 9 10
Ecco il numero di mosse per riportare le carte allo stato originale (tutte
coperte), per n che va da 1 a 16.
1: 2
2: 4
3: 3
4: 6
5: 10
6: 12
7: 4
8: 8
9: 18
10: 6
11: 11
12: 20
13: 18
14: 28
15: 5
16: 10
Ciao
Giorgio

 Non č cosě semplice. Ecco cosa succede con 9 carte. Ci vogliono 18 mosse a
[cut]
Aaahhh...ora ho capito! Ho considerato in modo diverso il tuo 'prendete 
poi le prime due (compresa la prima appena girata), le girate e le 
mettete sul mazzo'...ecco come veniva a me una mossa (5 carte, per 
semplicita', le negative sono quelle girate)
1 2 3 4 5
  -1 2 3 4 5
  1 -2 3 4 5
  -1 2 -3 4 5
  1 -2 3 -4 5
-1 2 -3 4 -5  (una mossa)
invece di 
1 2 3 4 5
  -1 2 3 4 5
  -2 1 3 4 5
  -3 -1 2 4 5 
  -4 -2 1 3 5
-5 -3 -1 2 4 (una mossa)
 
Bye by SixaM 8-]


Uh... in effetti la tua era un'interpretazione lecita, non ho specificato
abbastanza bene. Intendevo appunto dire che il mazzetto di 2, 3, ecc. carte
va girato come un tutt'uno.
Ciao
Giorgio

 Quante mosse occorrono per ogni valore di n?
Non ho una formula generale, però per ogni n posso facilmente
calcolare quante mosse occorrono per riportare il tutto alllo stato
iniziale. In pratica ogni mossa è costituito da una permutazione e una
serie di inversioni di carte.
prendiamo il caso che hai mostrato di n=10
  1, 2, 3, 4, 5, 6, 7, 8, 9,10   diventa
-10,-8,-6,-4,-2, 1, 3, 5, 7, 9
per sapere quante di queste permutazioni dobbiamo applicare prima di
tornare allo stato iniziale dobbiamo isolare i "cicli", ovvero quelle
porzioni di permutazione che riportano una carta nella posizione
originale. Seguiamo il destino della carta 1. Al primo passo si
troverà in posizione 10 (invertita), poi in posizione 9, dalla quale
passerà alla 7, poi alla 3, alla 6 (inversione) e poi di nuovo nella
posizione di partenza. Il ciclo può essere rappresentato come:
(1,-10,9,7,3,-6)
Dopo sei mosse la carta 1 tornerà a casa con due inversioni (quindi di
nuovo coperta), così anche la carta 10 che percorrerà il circuito
10,9,7,3,6,1 e le altre quattro carte del ciclo.
Le carte che restano fanno parte dei cicli (2,-8,5) e (-4). Il primo
ha lunghezza 3 con una inversione, per cui di fatto lunghezza 6, il
secondo lunghezza 1 con inversione, quindi 2. Il m.c.m. tra 6 e 2 è 6,
che è il numero di mosse richiesto.
Per n=12 c'è un ciclo da 10 con (1,-12,11,9,5,-4,-6,-2,-10,7) con 5
inversioni (lunghezza effettiva 20) ed un ciclo da 2 (3,-8) di
lunghezza effettiva 4. Il mcm è 20, quindi 20 mosse.
Si possono trovare regole generali per prevedere il numero e la
lunghezza dei cicli?
--
Ciao, Silv:o)


E' proprio qui il punto.
Se partiamo da una situazione iniziale con, ad esempio 7 carte, notiamo che
dopo una mossa la sequenza diventa:
prima:    1 2 3 4 5 6 7
dopo:    -7 -5 -3 -1 2 4 6
Con n dispari la prima carta va sempre a finire al centro e le altre si
dispongono alternativamente ai fianchi; inoltre le dispari si girano.
Generalizzando, sempre per n dispari, troviamo che la posizione della carta,
che inizialmente occupa la posizione x, diventa:
se x dispari:    (n+1)/2-(x-1)/2
se x pari:        (n+1)/2+x/2
(Per semplicità non tengo conto del segno per rappresentare la carta
scoperta, ma non dovrebbe essere difficile aggiungere qualche valore
assoluto per gestirlo; spero di non avere fatto errori, ma non importa. Per
n pari, la cosa è analoga, va solo aggiustata con qualche + o - 1 qua e là.)
Quindi quello che ho appena scritto rappresenta la funzione di
trasformazione f(x) che porta dalla posizione attuale di una carta alla
posizione successiva.
Se parto da x = 1, trovo f(1) = 4; poi se calcolo f(4) trovo 6, a sua volta
f(6) dà 7, quindi f(7) dà 1.
Dal punto di vista di una soluzione "meccanica" il problema è risolto. Si
tratta a questo punto di contare quante volte si applica la funzione per
tornare al valore iniziale per tutti gli x compresi tra 1 e n e poi con i
calcoli di mcm che dice Silvio si trova la soluzione. A dire il vero non so
se sia necessario applicare il mcm, forse è sufficiente trovare la sequenza
più lunga e forse la sequenza più lunga è sempre quella che parte da 1. Non
ho fatto alcuna verifica, quindi potrei dire delle sciocchezze.
Ma vorrei sapere se il problema ha una soluzione più "matematica". Data una
qualunque funzione f(x), parametrica su n, è possibile stabilire non
empiricamente quante volte la devo chiamare nella forma f(f(f(....f(x)))),
per ritornare al valore iniziale x? Io non ne ho la minima idea. :-)
Ciao
Giorgio