Il lupo, la nonna, la frutta

Alla fine della storia di Cappuccetto Rosso al lupo viene risparmiata la vita, ma in cambio dovrà impegnarsi a diventare buono. Così il lupo da quel giorno in avanti decide di occuparsi della spesa della nonna. Un giorno la nonna lo manda al negozio dicendogli: prendimi quattro frutti tra mele, pere e banane; decidi tu quanti prenderne per ciascun tipo, l’importante è che in totale ce ne siano quattro, eventualmente anche tutti e quattro dello stesso tipo.

Il lupo ha 15 modi diversi per fare quel tipo di spesa. 15 si ottiene calcolando le combinazioni di 6 oggetti presi a gruppi di 2.

Domanda 1
Qual è il legame tra la formula e i parametri del problema?

Domanda 2
Qual è, alla luce della particolare formula utilizzata, un modo alternativo di formulare il problema iniziale?

Domanda 3
Se la nonna avesse chiesto al lupo di comprarle 9 frutti tra mele, pere, banane e albicocche in quanti modi diversi si sarebbe potuta fare quella spesa?

Domanda 4
Qual è la generalizzazione della formula al caso di n frutti di k tipi diversi?

Domanda 5
Con riferimento al problema iniziale, dal momento che le combinazioni di 6 oggetti a gruppi di 2 coincidono con le combinazioni di 6 oggetti a gruppi di 4, come si potrebbe riformulare il problema posto nel testo affinché sia più naturale risolverlo in questo secondo modo?

9 commenti (+aggiungi il tuo?)

  1. Nautilus
    Apr 28, 2019 @ 12:05:38

    Nessuno faccia il furbo chiamandosi fuori con una qualche scusa 🙂

  2. Lele
    Apr 29, 2019 @ 03:42:48

    Mi spiace, ho judo.

  3. Nautilus
    Apr 29, 2019 @ 09:06:21

    @ Lele

    Ecco, questo potrebbe essere un post di raccolta di scuse, alla fine 🙂

  4. shevathas
    Mag 01, 2019 @ 14:39:12

    io, ragionando in maniera costruttiva-ricorsiva, ho trovato una formula empirica che lega n e k, Num = Coef.Binom(n+k-1, k-1) ma non ho capito perché funzioni.

  5. Nautilus
    Mag 01, 2019 @ 15:56:57

    @ shevathas

    Nella maggior parte dei casi in combinatoria la cosa più difficile non è l’applicazione delle formule (che in fondo sono piuttosto semplici, se non addirittura banali), ma la modellizzazione del problema.

    Il quiz che ho descritto in questo post rientra nella categoria che possiamo definire sistemazione di n oggetti indistinguibili in k scompartimenti diversi.
    Lo so, mi sono messo di un certo impegno per mascherarlo sufficientemente bene, visto che spesso mi dite che propongo quesiti troppo semplici 🙂
    Su due piedi potresti infatti pensare che la casistica che ho appena descritto non c’entra nulla con il problema iniziale. Invece c’entra.

    Immagina di avere un armadio in cui puoi sistemare a tuo piacere i ripiani interni (molti armadi sono proprio così). Se hai k – 1 ripiani puoi creare al massimo k scomparti. Dico “al massimo” perché potresti decidere di attaccare tra loro i ripiani in modo da ridurre gli scomparti. Negli scomparti ci vai poi a sistemare degli asciugamani (i nostri frutti).

    Riferiamoci al problema da me posto. Le mele, le pere e le banane sono come gli asciugamani che vanno nei vari scomparti. Ecco perché nella formula la parte bassa del coefficiente binomiale è k – 1. Se metti due ripiani distanziati tra loro (per ora non importa di quanto) crei tre scomparti (nei quali sistemare mele, pere e banane), ma puoi anche decidere, ad esempio, di annullare lo spazio tra i due così da comprimere – fino a farlo sparire – lo scomparto centrale destinato alle pere; oppure puoi decidere di mettere entrambi i ripiani in alto così da far sparire sia lo scomparto superiore (destinato alle mele) che quello centrale (destinato alle pere); oppure… be’, ci siamo capiti.
    Ovviamente puoi anche invertire l’ordine e dire che le banane vanno in alto, le pere in mezzo e le mele in basso; questo non è importante (basta scegliere uno dei due ordinamenti possibili).

    Ora, così come puoi decidere di annullare lo spazio tra i ripiani puoi anche regolarlo per farci stare uno, due, tre, … asciugamani, cioè frutti nel nostro caso.

    In pratica funziona così. Ci sono quattro frutti (o quattro asciugamani) che possiamo rappresentare come:

    FFFF

    Da qualche parte, tra un frutto e l’altro, puoi inserire delle barrette e gestire tutte le casistiche possibili (ne riporto alcune a titolo d’esempio):

    FFF|F| (3 mele, 1 pera, 0 banane)
    F|FF|F (1 mela, 2 pere, 1 banana)
    ||FFFF (0 mele, 0 pere, 4 banane)

    A questo punto, una volta compresa la modellizzazione del problema (che – come ho detto – è la vera cosa difficile) tutto si riduce a mettere dei separatori che ci diano tutte le combinazioni possibili.

    Quanti frutti (asciugamani, oggetti) ho? 4. Quanti tipi di frutti (scomparti, oggetti diversi) ho? 3. Bene, la risposta alla seconda domanda mi dice che per avere tre scomparti mi servono due ripiani (barrette), e questo diventa il denominatore del coefficiente binomiale. Ciò stabilito aggiungo il numero di barrette a n e ho sistemato anche il numeratore.

    In termini più meccanici: 1. modellizzo il problema, 2. trovo il numero di barrette che mi servono, 3. determino numeratore e denominatore del coefficiente binomiale, 4. eseguo il calcolo.

    Il tipo di quiz proposto fa sembrare gli oggetti (i frutti) distinguibili tra loro, ma in realtà non lo sono. Come se un frutto fosse inizialmente indifferenziato e diventa mela, pera o banana “solo” quando lo metto nel suo scomparto. In fondo è come se ho degli asciugamani tutti identici che puoi diventano quelli di mamma, quelli di papà e quelli della figlia “solo” quando li metto nel giusto scomparto.

    Insomma: 1. l’ho fatta un po’ lunga, 2. spero che c’hai capito qualcosa, 3. spero sopratutto che hai capito la potenza del metodo 🙂

  6. Nautilus
    Mag 01, 2019 @ 16:01:52

    @ shevathas

    Di fatto hai risposto (anche senza fare calcoli banali) alle domande 1, 3 e 4. La risposta alla domanda 2 l’ho data praticamente io. Resta da dare la risposta alla domanda 5.

  7. shevathas
    Mag 02, 2019 @ 12:04:51

    la spiegazione è abbastanza chiara, anche se ho ancora un poco di difficoltà a capire la modellizzazione. ci devo pensare un poco sopra…

  8. Nautilus
    Mag 02, 2019 @ 12:40:28

    @ shevathas

    Tranquillo, intanto (domani) me ne vado un paio di giorni nell’astigiano per un po’ di relax 😀

  9. Mauro
    Mag 02, 2019 @ 15:11:05

    Scusa ma ero rimasto bloccato in aereo senza Internet 😛

Rispondi

Inserisci i tuoi dati qui sotto o clicca su un'icona per effettuare l'accesso:

Logo WordPress.com

Stai commentando usando il tuo account WordPress.com. Chiudi sessione /  Modifica )

Google photo

Stai commentando usando il tuo account Google. Chiudi sessione /  Modifica )

Foto Twitter

Stai commentando usando il tuo account Twitter. Chiudi sessione /  Modifica )

Foto di Facebook

Stai commentando usando il tuo account Facebook. Chiudi sessione /  Modifica )

Connessione a %s...