Un uomo entra una locanda con una catena d'oro e dice all'oste che pagherà un anello a notte
L'oste gli concede inoltre la possibilità di fare scambi tra i pezzi di catena ora in possesso dell'oste e quelli ancora in possesso dell'uomo (ad esempio il terzo giorno può prendere dall'oste la coppia di anelli che gli ha dato e dargli una terna di anelli uniti in cambio)
Per separare la sua catena l'uomo stacca singoli anelli da essa (ad esempio stacca il quarto da una catena da $10$ anelli e gli reestano $1$ anello singolo, $3$ uniti e altri $6$ uniti)
Dire quanti ne deve staccare al minimo per usufruire di tutta una catena da $7$ (cioè per pagare $7$ giorni) e dire qual'è la massima lunghezza $n$ di una catena di cui si può usufurire pienamente (cioè per pagare $n$ giorni) staccando $m$ anelli
14. Anelli e Catene
Re: 14. Anelli e Catene
Per pagare per $7$ giorni con una catena da $7$ anelli è sufficiente che stacchi il terzo anello, quindi basta una solo divisione:
Il primo giorno pagherà con il terzo anello, il secondo con la coppia da due, il terzo con la coppia da due più il singolo anello, il quarto con la catenella lunga quattro, il quinto con la catenella lunga quattro più il singolo, il sesto con la catenella lunga quattro e la coppia di anelli, e il settimo giorno può dare tutte e tre le parti che componevano la catenina da $7$ anelli.
Proviamo qualche $m$ per capire come procedere:
Supponiamo di avere un anello staccato, come posso mettere quelli intorno?
Il caso migliore è metterne $2$ da una parte e $4$ dall'altra, quindi $n_{1}=7 $.
Se $m=2$ ho due anelli singoli quindi posso metterne $3$ tra i due anelli $6$ Da una parte e $12$ dall'altra e quindi $n_{2}=23$.
Se $m=3$ posso metterne $4$ tra due anelli $8$ tra gli altri due e poi $16$ da una parte e $32$ Dall'altra e quindi $n_{3}=63$.
Proviamo a generalizzare:
Se ho $m$ anelli singoli $n_{m}=m+(m+1)+(m+m+1+1)+(4m+4)+(8m+8)+(16m+16)+...+2^{m}(m+1)=$
$=m+\left( m+1\right) \sum ^{m}_{i=0}2^{i}=$
$=m+\left( m+1\right) \left( 2^{m+1}-1\right)=\left( m+1\right) 2^{m+1}-1 $
E con questo dovrei aver concluso
Il primo giorno pagherà con il terzo anello, il secondo con la coppia da due, il terzo con la coppia da due più il singolo anello, il quarto con la catenella lunga quattro, il quinto con la catenella lunga quattro più il singolo, il sesto con la catenella lunga quattro e la coppia di anelli, e il settimo giorno può dare tutte e tre le parti che componevano la catenina da $7$ anelli.
Proviamo qualche $m$ per capire come procedere:
Supponiamo di avere un anello staccato, come posso mettere quelli intorno?
Il caso migliore è metterne $2$ da una parte e $4$ dall'altra, quindi $n_{1}=7 $.
Se $m=2$ ho due anelli singoli quindi posso metterne $3$ tra i due anelli $6$ Da una parte e $12$ dall'altra e quindi $n_{2}=23$.
Se $m=3$ posso metterne $4$ tra due anelli $8$ tra gli altri due e poi $16$ da una parte e $32$ Dall'altra e quindi $n_{3}=63$.
Proviamo a generalizzare:
Se ho $m$ anelli singoli $n_{m}=m+(m+1)+(m+m+1+1)+(4m+4)+(8m+8)+(16m+16)+...+2^{m}(m+1)=$
$=m+\left( m+1\right) \sum ^{m}_{i=0}2^{i}=$
$=m+\left( m+1\right) \left( 2^{m+1}-1\right)=\left( m+1\right) 2^{m+1}-1 $
E con questo dovrei aver concluso
Re: 14. Anelli e Catene
È giusta
Ma non mi è chiaro come giustifichi che la tua tecnica sia la migliore
Se me lo sono perso scusami!!
Ma non mi è chiaro come giustifichi che la tua tecnica sia la migliore
Se me lo sono perso scusami!!
Re: 14. Anelli e Catene
Provo ad essere più chiaro (lo sono stato pochissimo prima) allora:
se ho $m$ anelli allora ho $m+1$ posti in cui inserire catene di anelli.
A questo punto devo massimizzare gli elementi da mettere in questi posti vuoti (che chiamerò spazi per semplicitá): se non ho uno spazio in cui ho una catena lunga al massimo $m+1$ (Ovvero tutte sono maggiori) è ovvio che il "gioco" non funziona, quindi per massimizzare deve esserci un solo spazio con una catena lunga $m+1$ (Che è uguale alla somma delle catene di anelli di lunghezze inferiori più uno), per lo spazio successivo mi serve una catena che può essere lunga al massimo $2m+2$ (Analogamente a prima è la somma delle catene di anelli di lunghezze inferiori più uno)... E così via fino a $2^{m}(m+1)$. A questo punto faccio la somma di tutte e ottengo il risultato detto sopra.
Capisco che è poco chiaro, ma meglio di così non saprei spiegarmi (mea culpa)
se ho $m$ anelli allora ho $m+1$ posti in cui inserire catene di anelli.
A questo punto devo massimizzare gli elementi da mettere in questi posti vuoti (che chiamerò spazi per semplicitá): se non ho uno spazio in cui ho una catena lunga al massimo $m+1$ (Ovvero tutte sono maggiori) è ovvio che il "gioco" non funziona, quindi per massimizzare deve esserci un solo spazio con una catena lunga $m+1$ (Che è uguale alla somma delle catene di anelli di lunghezze inferiori più uno), per lo spazio successivo mi serve una catena che può essere lunga al massimo $2m+2$ (Analogamente a prima è la somma delle catene di anelli di lunghezze inferiori più uno)... E così via fino a $2^{m}(m+1)$. A questo punto faccio la somma di tutte e ottengo il risultato detto sopra.
Capisco che è poco chiaro, ma meglio di così non saprei spiegarmi (mea culpa)
Re: 14. Anelli e Catene
Ora va bene!!
Più che altro prima non hai esplicitato il fatto che se hai $m$ pezzi devi averne almeno uno di lunghezza al più $m+1$ e che devi averne esattamente uno esattamente con quella lunghezza per massimizzare e così via
Vai pure col prossimo!!
Più che altro prima non hai esplicitato il fatto che se hai $m$ pezzi devi averne almeno uno di lunghezza al più $m+1$ e che devi averne esattamente uno esattamente con quella lunghezza per massimizzare e così via
Vai pure col prossimo!!