Torre di Hanoi

[iademarco]

Affrontando questi problemi, ho trovato qualche difficoltà (ovvero non mi esce) nel fare il 21
Problem:
Antonio ha costruito una torre di Hanoi con otto dischi (di misura diversa)
e 4 pioli denominati A, B, C, D. Si diverte a disporre in vari modi i dischi
nei 4 pioli dandosi le seguenti regole:
1. Non si può disporre un disco sopra uno più piccolo;
2. L'unico piolo che può restare vuoto è il D;
3. I dischi più bassi dei vari pioli devono essere disposti in ordine
decrescente.
In quanti modi diversi Antonio può disporre i dischi?

Grazie anticipatamente della/e risposte

[karlosson_sul_tetto]

Affrontando questi problemi, ho trovato qualche difficoltà (ovvero non mi esce) nel fare il 21
Problem:
Antonio ha costruito una torre di Hanoi con otto dischi (di misura diversa)
e 4 pioli denominati A, B, C, D. Si diverte a disporre in vari modi i dischi
nei 4 pioli dandosi le seguenti regole:
1. Non si può disporre un disco sopra uno più piccolo;
2. L'unico piolo che può restare vuoto è il D;
3. I dischi più bassi dei vari pioli devono essere disposti in ordine
decrescente.
In quanti modi diversi Antonio può disporre i dischi?

Grazie anticipatamente della/e risposte

A me sembra troppo semplice:abbiamo $ $3$ $ diversi modi di disporre il $ $1°$ $ disco,$ $3$ $ per il $ $2°$ $ e via dicendo;cosi avremo:$ 3^8 $ che equivale a:$ $6561$ $.
Mi sa che ho sbagliato:è troppo facile.

[iademarco]

A me sembra troppo semplice
Mi sa che ho sbagliato:è troppo facile.

Ed infatti hai sbagliato
La prima regola per non sbagliare un problema, è leggere bene il testo!

2. L'unico piolo che può (ma anche no!!) restare vuoto è il D;

E poi con $ 3^8 $ conti anche il caso in cui vanno tutti in A, e B e C rimangono vuoti, e questo non è ammesso

[karlosson_sul_tetto]

A me sembra troppo semplice
Mi sa che ho sbagliato:è troppo facile.

Ed infatti hai sbagliato
La prima regola per non sbagliare un problema, è leggere bene il testo!

2. L'unico piolo che può (ma anche no!!) restare vuoto è il D;

E poi con $ 3^8 $ conti anche il caso in cui vanno tutti in A, e B e C rimangono vuoti, e questo non è ammesso

Ah,grazie per avvermi corretto!

[Tibor Gallai]

Io di primo acchito l'ho calcolato con questa formula (che può essere un hint):

$ $\frac{4^8 - 4\cdot 3^8 + 6\cdot 2^8 - 4}{24} + \frac{3^8 - 3\cdot 2^8 + 3}{6} = 2667 $

Potrebbe anche esistere un modo più semplice di ricavarlo...

[iademarco]

$ $\frac{4^8 - 4\cdot 3^8 + 6\cdot 2^8 - 4}{24} + \frac{3^8 - 3\cdot 2^8 + 3}{6} = 2667 $

Innanzitutto grazie della pronta risposta
Ora vediamo un po' se ho capito:
$ 4^8 - 4\cdot 3^8 + 6\cdot 2^8 - 4 $
questi dovrebbero essere i modi di mettere gli 8 dischi nei 4 pioli, con almeno un disco in ognuno, e poi fratto 24 perchè se non lo facessimo, conteremmo 2 volte questo
A(1-2) B(3-4-5) C(6-7) D(8 )
e questo
A(1-2) B(3-4-5) C(8 ) D(6-7)
(con A B C D i 4 pioli e 12345678 i dischi)
...
$ \frac{3^8 - 3\cdot 2^8 + 3}{6} = 2667 $ e qui si contano i modi di mettere i dischi nei 3 pioli A B C, con almeno un disco in ognuno, e fratto 6 per lo stesso motivo di prima...
però a mio parere il problema è un po' ambiguo:

Antonio ha costruito una torre di Hanoi con otto dischi (di misura diversa)
e 4 pioli denominati A, B, C, D.

Il fatto che nomina i 4 pioli, mi fa capire che 2 configurazioni di questo tipo:
A(1-2) B(3-4-5) C(6-7) D(8 )
A(1-2) B(3-4-5) C(8 ) D(6-7)
si devono considerare diverse
Ora le cose sono tre:
1) ho sbagliato ad interpretare la tua soluzione
o
2) ho sbagliato ad interpretare il problema
o
3) il problema non è del tutto chiaro

[Tibor Gallai]

Dunque. Il fatto che i pioli abbiano delle lettere significa che le 2 configurazioni che hai scritto sono distinte. Altrimenti il testo avrebbe parlato di 4 pioli senza denominarli, o meglio ancora avrebbe trasferito il problema in un contesto completamente diverso, e comunque avrebbe scritto chiaramente che le configurazioni sono da considerarsi a meno dell'ordine delle torri.

Quindi sì, direi che hai sbagliato ad interpretare la mia soluzione. Ora però non ricordo più cosa ho pensato per risolverlo, se vuoi ci ripenso un attimo.

[Tibor Gallai]

Ok, ho riguardato: nel problema c'è la regola 3, secondo cui "i dischi più bassi dei vari pioli devono essere disposti in ordine decrescente". Forse avevi dimenticato questa regola.

[iademarco]

Ok, ho riguardato: nel problema c'è la regola 3, secondo cui "i dischi più bassi dei vari pioli devono essere disposti in ordine decrescente". Forse avevi dimenticato questa regola.

Ma caaaaaavolo!!! Non l'avevo dimenticata la 3° regola, l'avevo semplicemente fraintesa, cioè avevo (stupidamente) capito la stessa cosa della 1° regola...e infatti mi chiedevo per quale motivo 2 regole fossero uguali (e forse era anche per questo che la soluzione non mi usciva)

Comunque ora è tutto chiarissimo, grazie 1000