Le rane e i rospi

1. Il gioco "Rane e rospi"
Tre rospi sono situati sulle prime 3 caselle (a sinistra) di una striscia formata da 7 caselle quadrate.
Tre rane occupano invece le ultime 3 caselle (a destra).
In mezzo c'è una casella vuota.

Lo scopo del gioco è di trasferire le rane nelle caselle occupate dai rospi e i rospi nelle caselle occupate dalle rane.

javascript originale di Paul Nahay

Potete giocare direttamente al computer oppure utilizzare due tipi di monete o di segnalini su uno schema disegnato.

Ecco un disegno dello schema iniziale

rospo

rospo

rospo

rana

rana

rana

Le regole del gioco
I rospi possono muoversi solo verso destra, senza tornare indietro.
Le rane possono muoversi solo verso sinistra, senza tornare indietro.
Ogni casella può essere occupata da un solo animale.

Le mosse consentite sono il Passo e il Salto
Il Passo è il passaggio da una casella a quella immediatamente successiva, naturalmente solo se è quella vuota.

Ecco un esempio di passo effettuato da una rana.

Il Salto è il passaggio alla casella vuota saltando una casella occupata da un animale di genere differente. Un rospo può saltare una rana e viceversa.

Ecco un esempio di salto effettuato da un rospo.

...Sembra facile...

Nella versione generale di questo gioco si hanno n rane, m rospi e n+m+1 caselle.

Nota storica.
Il gioco probabilmente risale al 1700 ma il primo a fornire una soluzione del caso generale fu Lucas in L'Arithmétique Amusante, 1895. Prob. XXXV: Le bal des crapauds et des grenouilles.
Egli illustra i casi 2-2, 3-3, 4-4 e il caso generale n-n, mostrando che può essere risolto in n(n+2) mosse, n^2 salti e 2n passi.

2. Bicchieri vuoti e bicchieri pieni
Abbiamo 3 bicchieri pieni d'acqua (P) e tre bicchieri vuoti (V) disposti in fila nell'ordine: PPPVVV

Possiamo versare il contenuto di un bicchiere in un altro bicchiere.
In una sola mossa dobbiamo ottenere la seguente configurazione: PVPVPV.

Risposte & riflessioni

1. Il gioco "Rane e rospi"
Nel caso generale n-m, il gioco può essere risolto in mn+m+n mosse: mn Salti e m+n Passi.

Ciascuno dei n rospi deve muoversi di m+1 posti verso destra.
Ciascuna delle m rane devono muoversi di n+1 posti verso sinistra.
In tutto i Passi sarebbero quindi n(m+1) + m(n+1).
Tuttavia in un Salto, una pedina si sposta di 2 posizioni. Ma quanti sono i salti?
Ciascuna pedina deve scavalcare (o essere scavalcata da) esattamente una volta una pedina di tipo diverso. I Salti sono dunque mn.
Possiamo anche vedere un Salto come uno scambio di orientamento: rana-rospo -> rospo-rana.
Quindi le mosse, in tutto sono:

n(m+1) + m(n+1) - mn

mn+m+n

Il gioco ha due soluzioni, perché si può cominciare da destra o da sinistra.

Se costruiamo la stringa delle mosse come una sequenza di S (Salti) e P (Passi) si ha che:
a) se m=n, le stringhe corrispondenti alle due soluzioni sono uguali
b) Inoltre le stringhe delle due soluzioni sembrano essere sempre palindrome palindrome.
E' vero? Qualcuno sa dimostrare perché?

Ad ogni mossa del gioco, per la mossa successiva, ci possono essere quattro possibilità: SS oppure PP oppure SP oppure PS.
Ecco alcuni consigli per risolvere il gioco:

1. Salto-Salto è una configurazione fatale, evitatela: qualsiasi dei due Salti scegliete, alla mossa seguente sarete bloccati.

2. Se dovete scegliere fra un Salto e un Passo, scegliete sempre il Salto. Altrimenti sarete bloccati dopo il Passo.

3. Se dovete scegliere fra due Passi scegliete quello dei due che non vi porta alla configurazione Salto-Salto.

2. Bicchieri vuoti e bicchieri pieni

Sito Web realizzato da Gianfranco Bo