Embedded Files
Il gioco
Alcune rane e alcuni rospi sono seduti sui sassi di uno stagno: da una parte (diciamo a sinistra) ci sono le rane, dall'altra (a destra) i rospi e in mezzo c'è un sasso libero. Devono scambiarsi tutti di posto, quindi le rane a destra e i rospi a sinistra. Le mosse consentite sono il salto (S) di un solo sasso e il passaggio (P) al sasso adiacente, entrambe solo in avanti (non si torna indietro).
Proviamo a risolvere nei casi più semplici: partiamo con 1 rana e 1 rospo: è chiaro che occorrerà fare un passo, poi un salto e poi ancora un passo (PSP)
E se abbiamo 2 rane e 2 rospi? Chiaramente la prima mossa non sarà un salto (si resterebbe bloccati...)
Qui (sul sito del progetto NRICH dell'Università di Cambridge) trovate un gioco interattivo per fare prove più complicate (con numeri a piacere di rane e rospi)
Per i curiosi che vogliono la strategia risolutiva, diciamo che:
il numero minimo di mosse per spostare n rane e m rospi è n*m+n+m
precisamente occorrono n*m salti e n+m passi
Nel caso di stesso numero di rane e rospi (n rane e n rospi) queste sono le soluzioni:
Page updated
Google Sites
Report abuse