Le sei rane
Passatempo estivo ... 
Su una striscia orizzontale suddivisa in sette caselle ponete $6$ pedine (le "rane") numerate dall'uno al sei in ordine crescente da sinistra a destra lasciando vuota la prima casella a sinistra.
Lo scopo del gioco è quello di invertire l'ordine delle rane, disponendole dalla sei alla uno da sinistra a destra lasciando vuota alla fine la prima casella a sinistra.
Le rane si muovono una alla volta, nell'ordine che preferite, in due modalità: o spostandosi nella casella vuota adiacente oppure saltando una delle rane vicine sempreché la casella di arrivo sia vuota.
Qual è il numero minimo di mosse possibile? Quali sono queste mosse?
Cordialmente, Alex
Su una striscia orizzontale suddivisa in sette caselle ponete $6$ pedine (le "rane") numerate dall'uno al sei in ordine crescente da sinistra a destra lasciando vuota la prima casella a sinistra.
Lo scopo del gioco è quello di invertire l'ordine delle rane, disponendole dalla sei alla uno da sinistra a destra lasciando vuota alla fine la prima casella a sinistra.
Le rane si muovono una alla volta, nell'ordine che preferite, in due modalità: o spostandosi nella casella vuota adiacente oppure saltando una delle rane vicine sempreché la casella di arrivo sia vuota.
Qual è il numero minimo di mosse possibile? Quali sono queste mosse?
Cordialmente, Alex
Risposte
Buongiorno
Meno ...
Però ... bel lavoro e che pazienza!
Non è necessario comunque fare una tabellina del genere, è sufficiente elencare le rane nell'ordine in cui si muovono, non ci sono ambiguità ...
Cordialmente, Alex
Però ... bel lavoro e che pazienza!
Non è necessario comunque fare una tabellina del genere, è sufficiente elencare le rane nell'ordine in cui si muovono, non ci sono ambiguità ...
Cordialmente, Alex
Grazie per la pazienza 
La tabella in realtà l'ho usata solo perché ero davanti al pc e non avevo un foglio per annotare dove finivano di volta in volta le ranocchiette - né la voglia di cercarne uno
La tabella in realtà l'ho usata solo perché ero davanti al pc e non avevo un foglio per annotare dove finivano di volta in volta le ranocchiette - né la voglia di cercarne uno
A mente si fanno 'ste cose, a mente!
Comunque ti capisco, anch'io "abuso" di Excel pur di non fare cose ...
Cordialmente, Alex
Comunque ti capisco, anch'io "abuso" di Excel pur di non fare cose ...
Cordialmente, Alex
Buongiorno,
la tecnica più veloce mi sembra quella di alternare ai salti uno spostamento in questo modo:
3 salti a sinistra, un passo a destra, due salti a destra, un passo a sinistra e cosi via per un totale di 21 mosse.
Per maggior chiarezza:
partenza: _ 1 2 3 4 5 6
1a mossa: 2 1 _ 3 4 5 6
2a mossa: 2 1 4 3 _ 5 6
3a mossa: 2 1 4 3 6 5 _
4a mossa: 2 1 4 3 6 _ 5
5a mossa: 2 1 4 _ 6 3 5
6a mossa: 2 _ 4 1 6 3 5
7a mossa: _ 2 4 1 6 3 5
8a mossa: 4 2 _ 1 6 3 5
9a mossa: 4 2 6 1 _ 3 5
10a mossa: 4 2 6 1 5 3 _
11a mossa: 4 2 6 1 5 _ 3
12a mossa: 4 2 6 _ 5 1 3
13a mossa: 4 _ 6 2 5 1 3
14a mossa: _ 4 6 2 5 1 3
15a mossa: 6 4 _ 2 5 1 3
16a mossa: 6 4 5 2 _ 1 3
17a mossa: 6 4 5 2 3 1 _
18a mossa: 6 4 5 2 3 _ 1
19a mossa: 6 4 5 _ 3 2 1
20a mossa: 6 _ 5 4 3 2 1
21a mossa: _ 6 5 4 3 2 1
c'è di meglio?
saluti
Melba
la tecnica più veloce mi sembra quella di alternare ai salti uno spostamento in questo modo:
3 salti a sinistra, un passo a destra, due salti a destra, un passo a sinistra e cosi via per un totale di 21 mosse.
Per maggior chiarezza:
partenza: _ 1 2 3 4 5 6
1a mossa: 2 1 _ 3 4 5 6
2a mossa: 2 1 4 3 _ 5 6
3a mossa: 2 1 4 3 6 5 _
4a mossa: 2 1 4 3 6 _ 5
5a mossa: 2 1 4 _ 6 3 5
6a mossa: 2 _ 4 1 6 3 5
7a mossa: _ 2 4 1 6 3 5
8a mossa: 4 2 _ 1 6 3 5
9a mossa: 4 2 6 1 _ 3 5
10a mossa: 4 2 6 1 5 3 _
11a mossa: 4 2 6 1 5 _ 3
12a mossa: 4 2 6 _ 5 1 3
13a mossa: 4 _ 6 2 5 1 3
14a mossa: _ 4 6 2 5 1 3
15a mossa: 6 4 _ 2 5 1 3
16a mossa: 6 4 5 2 _ 1 3
17a mossa: 6 4 5 2 3 1 _
18a mossa: 6 4 5 2 3 _ 1
19a mossa: 6 4 5 _ 3 2 1
20a mossa: 6 _ 5 4 3 2 1
21a mossa: _ 6 5 4 3 2 1
c'è di meglio?
saluti
Melba
Brava Melba, ben fatto! 
Il minimo sono proprio $21$ mosse e la sequenza è quella; la riscrivo in un formato più compatto: $2, 4, 6, 5, 3, 1$ (da ripetere altre due volte), $2, 4, 6$.
Qual è il numero minimo di mosse nel caso generale di $n$ rane? E come si trova la relativa sequenza?
Cordialmente, Alex
Il minimo sono proprio $21$ mosse e la sequenza è quella; la riscrivo in un formato più compatto: $2, 4, 6, 5, 3, 1$ (da ripetere altre due volte), $2, 4, 6$.
Qual è il numero minimo di mosse nel caso generale di $n$ rane? E come si trova la relativa sequenza?
Cordialmente, Alex
Mi pare si debbano distinguere i due casi:
se n è pari: (n+1).n/2
se n è dispari: (n+1). n/2+n-2 cioè (n-1).(n+4)/2
è possibile riunire tutto in un'unica formula?
Melba
se n è pari: (n+1).n/2
se n è dispari: (n+1). n/2+n-2 cioè (n-1).(n+4)/2
è possibile riunire tutto in un'unica formula?
Melba
Se ho ben interpretato quello che hai scritto cioè così:
- se $n$ è pari allora le mosse sono $(n(n+1))/2 $
- se $n$ è dispari allora le mosse sono $(n(n+1))/2+n-2$ ovvero $((n-1)(n+4))/2$
allora la formula per $n$ pari va bene mentre quella per $n$ dispari non va bene.
Che io sappia non esiste una formula unica ...
Cordialmente, Alex
- se $n$ è pari allora le mosse sono $(n(n+1))/2 $
- se $n$ è dispari allora le mosse sono $(n(n+1))/2+n-2$ ovvero $((n-1)(n+4))/2$
allora la formula per $n$ pari va bene mentre quella per $n$ dispari non va bene.
Che io sappia non esiste una formula unica ...
Cordialmente, Alex
Effettivamente per 3 rane la formula non funziona perché è possibile farlo in 5 mosse, però dalle 5 rane in su mi sembra giusta: 5 rane, 18 mosse; 7 rane, 33 mosse (oltre non sono andato). Non è così?
Melba
Melba
No, meno ...
ok, dovrei esserci arrivato:
per 3 rane 5 mosse, per 5 rane 16 mosse, per 7 rane 31 mosse, quindi per n dispari: n(n+1)/2 + n - 4
per 3 rane 5 mosse, per 5 rane 16 mosse, per 7 rane 31 mosse, quindi per n dispari: n(n+1)/2 + n - 4
E qual è la procedura/algoritmo per determinare le mosse?
Cordialmente, Alex
Scusa, ma finora non ho avuto tempo.
Quando il numero delle rane è pari la procedura consiste nel muovere prima le pari in ordine crescente, poi le dispari in ordine decrescente, oppure prima le dispari in ordine crescente poi le pari in ordine decrescente, per due cicli e mezzo.
Quando il numero delle rane è dispari però questo procedimento non funziona ...
Quando il numero delle rane è pari la procedura consiste nel muovere prima le pari in ordine crescente, poi le dispari in ordine decrescente, oppure prima le dispari in ordine crescente poi le pari in ordine decrescente, per due cicli e mezzo.
Quando il numero delle rane è dispari però questo procedimento non funziona ...
Scusarti di che cosa? Ognuno risponde se e quando vuole, non ci sono obblighi ... 
Le procedure sono due, una per $n$ pari ed una per $n$ dispari, come per trovare il numero di mosse.
La tua procedura per $n$ pari è quasi giusta: per la precisione la sequenza delle mosse inizia con tutti i pari in ordine ascendente seguita da tutti i dispari in ordine discendente, questa sequenza (pari+dispari) è da ripetere $n/2$ volte per poi concludere con tutti i pari in ordine ascendente.
Le procedure sono due, una per $n$ pari ed una per $n$ dispari, come per trovare il numero di mosse.
La tua procedura per $n$ pari è quasi giusta: per la precisione la sequenza delle mosse inizia con tutti i pari in ordine ascendente seguita da tutti i dispari in ordine discendente, questa sequenza (pari+dispari) è da ripetere $n/2$ volte per poi concludere con tutti i pari in ordine ascendente.
Si è quello che intendevo anch'io, considerando un ciclo come composto da due fasi, una riguardante i numeri pari, l'altra i dispari, si compiono due cicli e mezzo. Però si può anche iniziare con i dispari, ad es. per sei rane così:
partenza: _ 1 2 3 4 5 6
1a mossa: 1 _ 2 3 4 5 6
2a mossa: 1 3 2 _ 4 5 6
3a mossa: 1 3 2 5 4 _ 6
4a mossa: 1 3 2 5 4 6 _
5a mossa: 1 3 2 5 _ 6 4
6a mossa: 1 3 _ 5 2 6 4
7a mossa: _ 3 1 5 2 6 4
8a mossa: 3 _ 1 5 2 6 4
9a mossa: 3 5 1 _ 2 6 4
10a mossa: 3 5 1 6 2 _ 4
11a mossa: 3 5 1 6 2 4 _
12a mossa: 3 5 1 6 _ 4 2
13a mossa: 3 5 _ 6 1 4 2
14a mossa: _ 5 3 6 1 4 2
15a mossa: 5 _ 3 6 1 4 2
16a mossa: 5 6 3 _ 1 4 2
17a mossa: 5 6 3 4 1 _ 2
18a mossa: 5 6 3 4 1 2 _
19a mossa: 5 6 3 4 _ 2 1
20a mossa: 5 6 _ 4 3 2 1
21a mossa: _ 6 5 4 3 2 1
quindi le soluzioni sono due, ma sono le sole possibili?
Saluti
Melba
partenza: _ 1 2 3 4 5 6
1a mossa: 1 _ 2 3 4 5 6
2a mossa: 1 3 2 _ 4 5 6
3a mossa: 1 3 2 5 4 _ 6
4a mossa: 1 3 2 5 4 6 _
5a mossa: 1 3 2 5 _ 6 4
6a mossa: 1 3 _ 5 2 6 4
7a mossa: _ 3 1 5 2 6 4
8a mossa: 3 _ 1 5 2 6 4
9a mossa: 3 5 1 _ 2 6 4
10a mossa: 3 5 1 6 2 _ 4
11a mossa: 3 5 1 6 2 4 _
12a mossa: 3 5 1 6 _ 4 2
13a mossa: 3 5 _ 6 1 4 2
14a mossa: _ 5 3 6 1 4 2
15a mossa: 5 _ 3 6 1 4 2
16a mossa: 5 6 3 _ 1 4 2
17a mossa: 5 6 3 4 1 _ 2
18a mossa: 5 6 3 4 1 2 _
19a mossa: 5 6 3 4 _ 2 1
20a mossa: 5 6 _ 4 3 2 1
21a mossa: _ 6 5 4 3 2 1
quindi le soluzioni sono due, ma sono le sole possibili?
Saluti
Melba
Non saprei dirti se siano le sole possibili ma credo di sì ...
Comunque, quando intendevo che fosse "quasi giusta" non mi riferivo "all'inversione" dei pari con i dispari (bravo!
) ma al numero di cicli: "due e mezzo" è un caso particolare (quando $n=4$) non quello generale che invece è $n/2$; difatti nel caso delle sei rane i cicli sono "tre e mezzo"; contali ... 
Cordialmente, Alex
Comunque, quando intendevo che fosse "quasi giusta" non mi riferivo "all'inversione" dei pari con i dispari (bravo!
) ma al numero di cicli: "due e mezzo" è un caso particolare (quando $n=4$) non quello generale che invece è $n/2$; difatti nel caso delle sei rane i cicli sono "tre e mezzo"; contali ... Cordialmente, Alex
Hai ragione, giusto: n/2 + mezzo ciclo.
Quando le rane sono dispari, però, la procedura sembra piuttosto strana. Per 5 rane ho trovato questa soluzione:
partenza: _ 1 2 3 4 5
1a mossa: 2 1 _ 3 4 5
2a mossa: 2 1 4 3 5
3a mossa: 2 1 4 _ 3 5
4a mossa: 2 _ 4 1 3 5
5a mossa: 2 4 _ 1 3 5
6a mossa: 2 4 3 1 _ 5
7a mossa: 2 4 3 _ 1 5
8a mossa: 2 4 3 5 1 _
9a mossa: 2 4 3 5 _ 1
10a mossa: 2 4 _ 5 3 1
11a mossa: _ 4 2 5 3 1
12a mossa: 4 _ 2 5 3 1
13a mossa: 4 5 2 _ 3 1
14a mossa: 4 5 2 3 _ 1
15a mossa: 4 5 _ 3 2 1
16a mossa: _ 5 4 3 2 1
è giusta?
Melba
Quando le rane sono dispari, però, la procedura sembra piuttosto strana. Per 5 rane ho trovato questa soluzione:
partenza: _ 1 2 3 4 5
1a mossa: 2 1 _ 3 4 5
2a mossa: 2 1 4 3 5
3a mossa: 2 1 4 _ 3 5
4a mossa: 2 _ 4 1 3 5
5a mossa: 2 4 _ 1 3 5
6a mossa: 2 4 3 1 _ 5
7a mossa: 2 4 3 _ 1 5
8a mossa: 2 4 3 5 1 _
9a mossa: 2 4 3 5 _ 1
10a mossa: 2 4 _ 5 3 1
11a mossa: _ 4 2 5 3 1
12a mossa: 4 _ 2 5 3 1
13a mossa: 4 5 2 _ 3 1
14a mossa: 4 5 2 3 _ 1
15a mossa: 4 5 _ 3 2 1
16a mossa: _ 5 4 3 2 1
è giusta?
Melba
Hai ragione, giusto: n/2 + mezzo ciclo.
Quando le rane sono dispari, però, la procedura sembra piuttosto strana. Per 5 rane ho trovato questa soluzione:
partenza: _ 1 2 3 4 5
1a mossa: 2 1 _ 3 4 5
2a mossa: 2 1 4 3 _ 5
3a mossa: 2 1 4 _ 3 5
4a mossa: 2 _ 4 1 3 5
5a mossa: 2 4 _ 1 3 5
6a mossa: 2 4 3 1 _ 5
7a mossa: 2 4 3 _ 1 5
8a mossa: 2 4 3 5 1 _
9a mossa: 2 4 3 5 _ 1
10a mossa: 2 4 _ 5 3 1
11a mossa: _ 4 2 5 3 1
12a mossa: 4 _ 2 5 3 1
13a mossa: 4 5 2 _ 3 1
14a mossa: 4 5 2 3 _ 1
15a mossa: 4 5 _ 3 2 1
16a mossa: _ 5 4 3 2 1
non saprei ricavarne una "regola"
Melba
Quando le rane sono dispari, però, la procedura sembra piuttosto strana. Per 5 rane ho trovato questa soluzione:
partenza: _ 1 2 3 4 5
1a mossa: 2 1 _ 3 4 5
2a mossa: 2 1 4 3 _ 5
3a mossa: 2 1 4 _ 3 5
4a mossa: 2 _ 4 1 3 5
5a mossa: 2 4 _ 1 3 5
6a mossa: 2 4 3 1 _ 5
7a mossa: 2 4 3 _ 1 5
8a mossa: 2 4 3 5 1 _
9a mossa: 2 4 3 5 _ 1
10a mossa: 2 4 _ 5 3 1
11a mossa: _ 4 2 5 3 1
12a mossa: 4 _ 2 5 3 1
13a mossa: 4 5 2 _ 3 1
14a mossa: 4 5 2 3 _ 1
15a mossa: 4 5 _ 3 2 1
16a mossa: _ 5 4 3 2 1
non saprei ricavarne una "regola"
Melba
Quella sequenza è "giusta" nel senso che le mosse sono corrette e il loro numero è il minimo possibile, ma non segue peraltro la regola che conosco; da ciò credo di potere dedurre che le sequenze risolutive non sono uniche anche se le procedure che ho scritto facilitano la loro costruzione.
Di seguito scrivo quella per $n$ dispari (la metto sotto spoiler cosi se vuoi, puoi continuare a cercarla tranquillamente )
Cordialmente, Alex
Di seguito scrivo quella per $n$ dispari (la metto sotto spoiler cosi se vuoi, puoi continuare a cercarla tranquillamente
)Cordialmente, Alex
Sicuramente la tua procedura per le rane dispari è più regolare della mia, che è "indescrivibile".
Riconsiderando il caso delle rane pari si potrebbe prendere in considerazione non la successione delle rane ma dei posti, ossia descrivere la procedura in questo modo: liberare prima tutti posti "pari" in ordine ascendente (ossia da sinistra a destra), poi i dispari in ordine discendente (ossia da destra a sinistra) per un numero di volte pari a n/2. Ad esempio nel caso di sei rane abbiamo 7 posti, nella posizione di partenza è libero il primo con la prima mossa si libera il 2° (spostando la rana 1 dal 2° posto al 1°), con la seconda il 4° e così via. In questo modo avremmo la sequenza di posti liberi 2, 4, 6, 7, 5, 3, 1 per tre volte.
Si potrebbe vedere la cosa anche come successione regolare di un ciclo di mosse distinguendo fra passo, quando la rana si sposta in un posto accanto a quello da cui parte, e salto, quando la rana deve saltare quella che le sta vicino. In questo caso avremmo sempre tre cicli composti ciascuno da una fase ascendente (passo, salto, salto, passo) e una discendente (salto, salto, salto).
partenza: _ 1 2 3 4 5 6
1a mossa: 1 _ 2 3 4 5 6 passo
2a mossa: 1 3 2 _ 4 5 6 salto
3a mossa: 1 3 2 5 4 _ 6 salto
4a mossa: 1 3 2 5 4 6 _ passo
5a mossa: 1 3 2 5 _ 6 4 salto
6a mossa: 1 3 _ 5 2 6 4 salto
7a mossa: _ 3 1 5 2 6 4 salto
___________________________________________________
8a mossa: 3 _ 1 5 2 6 4 passo
9a mossa: 3 5 1 _ 2 6 4 salto
10a mossa: 3 5 1 6 2 _ 4 salto
11a mossa: 3 5 1 6 2 4 _ passo
12a mossa: 3 5 1 6 _ 4 2 salto
13a mossa: 3 5 _ 6 1 4 2 salto
14a mossa: _ 5 3 6 1 4 2 salto
___________________________________________________
15a mossa: 5 _ 3 6 1 4 2 passo
16a mossa: 5 6 3 _ 1 4 2 salto
17a mossa: 5 6 3 4 1 _ 2 salto
18a mossa: 5 6 3 4 1 2 _ passo
19a mossa: 5 6 3 4 _ 2 1 salto
20a mossa: 5 6 _ 4 3 2 1 salto
21a mossa: _ 6 5 4 3 2 1 salto
Ovviamente si può partire con il salto e avremo allora nella fase ascendente salto, salto, salto, in quella discendente passo, salto, salto, passo
partenza: _ 1 2 3 4 5 6
1a mossa: 2 1 _ 3 4 5 6 salto
2a mossa: 2 1 4 3 _ 5 6 salto
3a mossa: 2 1 4 3 6 5 _ salto
4a mossa: 2 1 4 3 6 _ 5 passo
5a mossa: 2 1 4 _ 6 3 5 salto
6a mossa: 2 _ 4 1 6 3 5 salto
7a mossa: _ 2 4 1 6 3 5 passo
__________________________________________________
8a mossa: 4 2 _ 1 6 3 5 salto
9a mossa: 4 2 6 1 _ 3 5 salto
10a mossa: 4 2 6 1 5 3 _ salto
11a mossa: 4 2 6 1 5 _ 3 passo
12a mossa: 4 2 6 _ 5 1 3 salto
13a mossa: 4 _ 6 2 5 1 3 salto
14a mossa: _ 4 6 2 5 1 3 passo
___________________________________________________
15a mossa: 6 4 _ 2 5 1 3 salto
16a mossa: 6 4 5 2 _ 1 3 salto
17a mossa: 6 4 5 2 3 1 _ salto
18a mossa: 6 4 5 2 3 _ 1 passo
19a mossa: 6 4 5 _ 3 2 1 salto
20a mossa: 6 _ 5 4 3 2 1 salto
21a mossa: _ 6 5 4 3 2 1 passo
Penso che per le rane pari queste siano le uniche due procedure nel minor numero di mosse.
Il fatto che nel caso delle rane dispari la procedura sia più complicata e non unica mi fa pensare che il problema sarebbe più preciso se chiedesse di mettere le rane nell'ordine inverso, lasciando libera la casella di sinistra per le rane pari e quella di destra per le dispari. In questo caso il numero minimo di mosse per le dispari sarebbe ugualmente n/2 (n + 1), come per le pari, e la procedura analoga, ad esempio per 7 rane:
partenza: _ 1 2 3 4 5 6 7
1a mossa: 1 _ 2 3 4 5 6 7 passo
2a mossa: 1 3 2 _ 4 5 6 7 salto
3a mossa: 1 3 2 5 4 _ 6 7 salto
4a mossa: 1 3 2 5 4 7 6 _ salto
5a mossa: 1 3 2 5 4 7 _ 6 passo
6a mossa: 1 3 2 5 _ 7 4 6 salto
7a mossa: 1 3 _ 5 2 7 4 6 salto
8a mossa: _ 3 1 5 2 7 4 6 salto
_______________________________________________________
9a mossa: 3 _ 1 5 2 7 4 6 passo
10a mossa: 3 5 1 _ 2 7 4 6 salto
11a mossa: 3 5 1 7 2 _ 4 6 salto
12a mossa: 3 5 1 7 2 6 4 _ salto
13a mossa: 3 5 1 7 2 6 _ 4 passo
14a mossa: 3 5 1 7 _ 6 2 4 salto
15a mossa: 3 5 _ 7 1 6 2 4 salto
16a mossa: _ 5 3 7 1 6 2 4 salto
17a mossa: 5 _ 3 7 1 6 2 4 passo
18a mossa: 5 7 3 _ 1 6 2 4 salto
_______________________________________________________
19a mossa: 5 7 3 6 1 _ 2 4 salto
20a mossa: 5 7 3 6 1 4 2 _ salto
21a mossa: 5 7 3 6 1 4 _ 2 passo
22a mossa: 5 7 3 6 _ 4 1 2 salto
23a mossa: 5 7 _ 6 3 4 1 2 salto
24a mossa: _ 7 5 6 3 4 1 2 salto
25a mossa: 7 _ 5 6 3 4 1 2 passo
26a mossa: 7 6 5 _ 3 4 1 2 salto
27a mossa: 7 6 5 4 3 _ 1 2 salto
28a mossa : 7 6 5 4 3 2 1 _ salto
Saluti
Melba
Riconsiderando il caso delle rane pari si potrebbe prendere in considerazione non la successione delle rane ma dei posti, ossia descrivere la procedura in questo modo: liberare prima tutti posti "pari" in ordine ascendente (ossia da sinistra a destra), poi i dispari in ordine discendente (ossia da destra a sinistra) per un numero di volte pari a n/2. Ad esempio nel caso di sei rane abbiamo 7 posti, nella posizione di partenza è libero il primo con la prima mossa si libera il 2° (spostando la rana 1 dal 2° posto al 1°), con la seconda il 4° e così via. In questo modo avremmo la sequenza di posti liberi 2, 4, 6, 7, 5, 3, 1 per tre volte.
Si potrebbe vedere la cosa anche come successione regolare di un ciclo di mosse distinguendo fra passo, quando la rana si sposta in un posto accanto a quello da cui parte, e salto, quando la rana deve saltare quella che le sta vicino. In questo caso avremmo sempre tre cicli composti ciascuno da una fase ascendente (passo, salto, salto, passo) e una discendente (salto, salto, salto).
partenza: _ 1 2 3 4 5 6
1a mossa: 1 _ 2 3 4 5 6 passo
2a mossa: 1 3 2 _ 4 5 6 salto
3a mossa: 1 3 2 5 4 _ 6 salto
4a mossa: 1 3 2 5 4 6 _ passo
5a mossa: 1 3 2 5 _ 6 4 salto
6a mossa: 1 3 _ 5 2 6 4 salto
7a mossa: _ 3 1 5 2 6 4 salto
___________________________________________________
8a mossa: 3 _ 1 5 2 6 4 passo
9a mossa: 3 5 1 _ 2 6 4 salto
10a mossa: 3 5 1 6 2 _ 4 salto
11a mossa: 3 5 1 6 2 4 _ passo
12a mossa: 3 5 1 6 _ 4 2 salto
13a mossa: 3 5 _ 6 1 4 2 salto
14a mossa: _ 5 3 6 1 4 2 salto
___________________________________________________
15a mossa: 5 _ 3 6 1 4 2 passo
16a mossa: 5 6 3 _ 1 4 2 salto
17a mossa: 5 6 3 4 1 _ 2 salto
18a mossa: 5 6 3 4 1 2 _ passo
19a mossa: 5 6 3 4 _ 2 1 salto
20a mossa: 5 6 _ 4 3 2 1 salto
21a mossa: _ 6 5 4 3 2 1 salto
Ovviamente si può partire con il salto e avremo allora nella fase ascendente salto, salto, salto, in quella discendente passo, salto, salto, passo
partenza: _ 1 2 3 4 5 6
1a mossa: 2 1 _ 3 4 5 6 salto
2a mossa: 2 1 4 3 _ 5 6 salto
3a mossa: 2 1 4 3 6 5 _ salto
4a mossa: 2 1 4 3 6 _ 5 passo
5a mossa: 2 1 4 _ 6 3 5 salto
6a mossa: 2 _ 4 1 6 3 5 salto
7a mossa: _ 2 4 1 6 3 5 passo
__________________________________________________
8a mossa: 4 2 _ 1 6 3 5 salto
9a mossa: 4 2 6 1 _ 3 5 salto
10a mossa: 4 2 6 1 5 3 _ salto
11a mossa: 4 2 6 1 5 _ 3 passo
12a mossa: 4 2 6 _ 5 1 3 salto
13a mossa: 4 _ 6 2 5 1 3 salto
14a mossa: _ 4 6 2 5 1 3 passo
___________________________________________________
15a mossa: 6 4 _ 2 5 1 3 salto
16a mossa: 6 4 5 2 _ 1 3 salto
17a mossa: 6 4 5 2 3 1 _ salto
18a mossa: 6 4 5 2 3 _ 1 passo
19a mossa: 6 4 5 _ 3 2 1 salto
20a mossa: 6 _ 5 4 3 2 1 salto
21a mossa: _ 6 5 4 3 2 1 passo
Penso che per le rane pari queste siano le uniche due procedure nel minor numero di mosse.
Il fatto che nel caso delle rane dispari la procedura sia più complicata e non unica mi fa pensare che il problema sarebbe più preciso se chiedesse di mettere le rane nell'ordine inverso, lasciando libera la casella di sinistra per le rane pari e quella di destra per le dispari. In questo caso il numero minimo di mosse per le dispari sarebbe ugualmente n/2 (n + 1), come per le pari, e la procedura analoga, ad esempio per 7 rane:
partenza: _ 1 2 3 4 5 6 7
1a mossa: 1 _ 2 3 4 5 6 7 passo
2a mossa: 1 3 2 _ 4 5 6 7 salto
3a mossa: 1 3 2 5 4 _ 6 7 salto
4a mossa: 1 3 2 5 4 7 6 _ salto
5a mossa: 1 3 2 5 4 7 _ 6 passo
6a mossa: 1 3 2 5 _ 7 4 6 salto
7a mossa: 1 3 _ 5 2 7 4 6 salto
8a mossa: _ 3 1 5 2 7 4 6 salto
_______________________________________________________
9a mossa: 3 _ 1 5 2 7 4 6 passo
10a mossa: 3 5 1 _ 2 7 4 6 salto
11a mossa: 3 5 1 7 2 _ 4 6 salto
12a mossa: 3 5 1 7 2 6 4 _ salto
13a mossa: 3 5 1 7 2 6 _ 4 passo
14a mossa: 3 5 1 7 _ 6 2 4 salto
15a mossa: 3 5 _ 7 1 6 2 4 salto
16a mossa: _ 5 3 7 1 6 2 4 salto
17a mossa: 5 _ 3 7 1 6 2 4 passo
18a mossa: 5 7 3 _ 1 6 2 4 salto
_______________________________________________________
19a mossa: 5 7 3 6 1 _ 2 4 salto
20a mossa: 5 7 3 6 1 4 2 _ salto
21a mossa: 5 7 3 6 1 4 _ 2 passo
22a mossa: 5 7 3 6 _ 4 1 2 salto
23a mossa: 5 7 _ 6 3 4 1 2 salto
24a mossa: _ 7 5 6 3 4 1 2 salto
25a mossa: 7 _ 5 6 3 4 1 2 passo
26a mossa: 7 6 5 _ 3 4 1 2 salto
27a mossa: 7 6 5 4 3 _ 1 2 salto
28a mossa : 7 6 5 4 3 2 1 _ salto
Saluti
Melba
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo