17. Ceste di pesci (staffetta)

[sasha™]

Non so se va bene come problema, ma la mia scarsa fantasia non mi permette di fare di meglio. Salvo voler proporre quello delle mele!

Ci sono, disposte circolarmente intorno ad un lago, 12 ceste contenenti un pesce ciascuna. Si può spostare un pesce da una cesta ad un altra, purché si saltino esattamente due pesci (non due ceste) mentre lo si sposta (ciò vuol dire che si può saltare un numero qualsiasi di ceste vuote). È consentito spostare un solo pesce alla volta e muoversi solo in senso orario. Determinare il tragitto più breve tale che, al termine di questo, ci siano sei ceste con due pesci e sei ceste vuote, spostando solo sei pesci.

[staffo]

una domanda: ma se io ho nel senso in cui dovresi spostare il pesce la cesta davanti con un pesce e quella dopo con due pesci, cosa faccio, non posso fare il movimento o posso mettere il pesce nella cesta quella con i due pesci (cioè lo metto tra i due pesci della stessa cesta)?

[sasha™]

No, non puoi proprio spostare il pesce.

[staffo]

un'altra cosa, ma per tragitto più breve cosa intendi? il minot numero di pesci spostati, il minor numero di ceste slatate dai pesci, oppure devo supporre un uomo che sposti i pesci e deve tornare indietro a prenderseli?

[sasha™]

Be', le ceste sono messe in cerchio, e tu, che devi spostare i pesci, sei pigro e vuoi fare meno strada possibile... Ma puoi muoverti solo in senso orario.

[paga92aren]

Numero le ceste dalla 1 alla 12 in senso antiorario (risolvo il problema in senso antiorario e lo stesso vale per il senso orario)
1) si può fare in 25 mosse: 1-4, 5-8, 9-12, 3-6, 7-10, 11-2. (1-4 intendo che prendo il pesce nella cesta 1 e lo lascio nella 4)
2) Suppongo (wlog) che il primo pesce sia preso nella cesta 1 e lasciato nella cesta 4. Dopo un giro devo prendere o lasciare un pesce nella cesta 2 (altrimenti ci dovrò passare al giro dopo e fare almeno 25 passi). Se prendo un pesce salto la cesta 3 e ci dovrò tornare al terzo giro (>25 passi), se lascio un pesce nella cesto 2 allora il pesce proveniva dalla cesto 10, ha saltato la 11 e la 12 con un pesce e la 1 con zero pesci. Al secondo giro devo sistemare i pesci delle ceste 11 e 12 quindi atterro con un pesce nella 11 e prendo quello della 12 che salterà la cesta 1 (con 0 pesci) e la 2 (con due pesci) facendo più di 25 passi.

Questo ragionamento si generalizza facilmente con $4n$ ceste.
Spero che sia stato chiaro, senza un disegno è difficile....

e se le ceste fossero $4n+2$?

[sasha™]

Right. Non era difficile.
Aspetti il bonus (che ora non ho tempo, ma magari poi provo a fare) o proponi direttamente il prossimo?

[paga92aren]

Qui il prossimo problema