Quizzino della domenica: Toblerone

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]

(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.)

12 comments

  1. 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 :-)

  2. 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”) :-)

  3. @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.

  4. (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)

  5. 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 !

  6. 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