Si hanno a disposizione due tubi A e B aperti ad una sola estremità.
Il tubo A contiene 4 dischi sovrapposti di diametro pari a quello del tubo e il tubo B è vuoto.
I dischi sono numerati da 1 a 4 e sono inizialmente disposti in ordine crescente, con il disco 1 in fondo al tubo A e il disco 4 in cima.Si possono compiere 4 operazioni:
- Estrarre il disco in cima al tubo A ed inserirlo in cima al tubo B.
- Estrarre il disco in cima al tubo B ed inserirlo in cima al tubo A.
- Prendere il disco in cima a un tubo e tenerlo in mano. Si può avere in mano al più 1 disco alla volta.
- Supponendo di avere in mano un disco, lo si può inserire in cima ad uno dei due tubi.
Si chiede quale sia il minimo numero complessivo di operazioni dei tipi sopra indicati necessarie per muovere tutti i dischi dal tubo A al tubo B mantenendo l’ordine di partenza.
Nota che il trasferimento può essere fatto in diversi modi; la domanda richiede di indicare il numero minimo di operazioni necessarie.
Esempio
Se i dischi fossero solo due e il disco 2 fosse sopra al disco 1 nel tubo A allora la seguente sequenza di operazioni permette di effettuare il trasferimento dei dischi nel tubo B mantenendo l’ordine iniziale: un’operazione 3 (si prende un disco dal tubo A), seguita da un’operazione 1 e, infine, un’operazione 4.In questo caso è facile anche vedere che non è possibile effettuare il trasferimento con un minor numero di mosse e, quindi, il numero minimo è 3.Nota Bene: fai attenzione perché la domanda ha un punteggio molto alto e la risposta non è facile…