Avete presente il Toblerone? La struttura è quella di tanti prismi triangolari attaccati tra di loro. Immaginate di avere una barretta formata da n pezzi e di volerla mangiare in un modo particolare, staccando – sempre dallo stesso lato – un certo numero di pezzi e mangiandoveli tutti insieme. Se siete golosi, vi mangerete tutta la barretta in un colpo solo; se siete morigerati, vi durerà n volte, perché toglierete un pezzetto singolo per volta. Bene: in quanti modi diversi potete terminare la barretta? Naturalmente mangiare prima un pezzo e poi due è considerato diverso da mangiarne prima due e poi uno.
![[Toblerone]](https://i0.wp.com/xmau.com/wp/notiziole/wp-content/uploads/sites/6/2020/02/q437a.png?resize=362%2C53&ssl=1)
(un aiutino lo trovate sul mio sito, alla pagina http://xmau.com/quizzini/p437.html; la risposta verrà postata lì il prossimo mercoledì. Problema ispirato da Math StackExchange.)
Mi sembra sia la partizione di n, è un ToblEulerone?
Per quanto ne so non esiste una formula chiusa (a parte quella asintotica di Ramanujan) e il valore si calcola con una relazione di ricorrenza, come pare suggerisca l’aiutino.
no, non è il numero di partizioni. Per il resto, nel caso 2xn una formula chiusa l’ho trovata; l’ho messa nel post scriptum, per il problema ho usato excel persino io :-)
In realtà, se non la leggo male, questa versione del problema è molto più semplice e non serve neanche la ricorsività per risolverlo (mio aiutino: “stars and bars”) :-)
@LightKnight: grazie per lo stars and bars!
Dopo aver sacrificato parecchi Tobleroni sull’altare della scienza, fatto anch’io i conti con Excel, e chiesto a Knuth (TAoCP 4A, pag. 308, esercizio n. 12) dovrebbero esserci 2^(n-1) modi di mangiare la barretta.
(uffa, mi sono accorto che stavo pensando a un altro problema di “mangiamento cioccolato”, che però non finirà qui nei quizzini. Non considerate il mio commento precedente)
Ho letto la risposta, ma non capisco bene a cosa si appoggia l’induzione per cui per K pezzi ci siano 2^(K-1) casi. :|
parti da n=2, dove hai due casi (mangi tutto assieme oppure un pezzo per volta)
Credo di esserci arrivato …
Per N=1 risulta 1
Per N=2 risulta 2
Per N generico sommiano i risultati precedenti piu’ 1,
ed essendo partiti da 1 e 2, otteniamo la potenza di 2 successiva.
Con l’induzione fatico sempre …
Grazie !
Arrivo molto in ritardo ma mi faceva piacere illustrare una maniera completamente diversa di risolvere il problemino (nonostante io adori le soluzioni per induzione).
Considerate la fila di N pezzi abbiamo (N-1) separatori.
pezzi: OOO…..OOO
posizione dei separatori: ^ ^ ^….^ ^ ^
I modi di mangiare il Toblerone sono quindi tutte le possibili combinazioni per cui rompo/non rompo i singoli *separatori*. Quindi abbiamo 2^(N-1) combinazioni possibili.
Ciao ciao
Scusate, vedo che nel “disegnino” si è persa la spaziatura, ignoratelo pure, spero che si capisca comunque. Sorry
ottima risoluzione! (poi ognuno ha le sue preferenze: io per esempio sono un fan della ricorsione)
Sì, è quello che intendevo quando ho scritto “stars and bars”. Grazie per averlo esplicitato :-D