Esercizio di calcolo combinatorio
Ciao a tutti 
questo quesito mi è stato posto da un amico che frequenta le scuole superiori. Io purtroppo non ho mai studiato seriamente il calcolo combinatorio (fortunatamente il prossimo semestre ho un intero corso di probabilità e statistica che saprà porvi rimedio). Mi vergogno un po' ad ammetterlo, ma non riesco a risolverlo..
Il testo dell'esercizio è il seguente:
16 persone devono prendere un treno. 8 di queste persone hanno in tasca una moneta da 50 centesimi, le altre 8 hanno una moneta da un euro. Il biglietto del treno costa 50 centesimi. Inizialmente la cassa della biglietteria è vuota, e quindi non può dare resto. In quanti modi possibili possono mettersi in fila queste persone affinchè tutti possano ricevere il biglietto e il relativo resto?
Io ho ragionato in questo modo: indico con 0 le persone che hanno una moneta da 50 centesimi, con 1 le persone che hanno una moneta da 1 euro.
Abbiamo una sequenza di 16 cifre. La prima cifra deve necessariamente essere uno 0 e l'ultima un 1, quindi ne rimangono 14. Date quindi n persone, in generale devo quindi riordinarne n-2. Se proviamo a fare il conto supponendo di avere meno persone (ad esempio 4, o 6) si può arrivare al risultato direttamente calcolando il numero possibile di riordinamenti. Nel caso di 4 persone, le uniche combinazioni possibili sono 0101 e 0011. Volevo quindi trovare una formula generale che mi permettesse di risolvere il problema, e $ 2^((n/2-1) $, n pari, mi sembrava funzionasse (con n=2,4,6,8 funziona). Ovviamente questo non significa nulla, e dovrei dimostrarlo in generale (o almeno fino a n=16, ma il conto diretto diventa pallosissimo
), ma non saprei come farlo.. forse per induzione?
Un altro metodo sarebbe quello di far ricorso alla probabilità di eventi dipendenti l'uno dell'altro, ma qui brancolo nel buio.. come vi ho detto, sono molto poco ferrato sull'argomento.
Aiuti sono ben accetti.
questo quesito mi è stato posto da un amico che frequenta le scuole superiori. Io purtroppo non ho mai studiato seriamente il calcolo combinatorio (fortunatamente il prossimo semestre ho un intero corso di probabilità e statistica che saprà porvi rimedio). Mi vergogno un po' ad ammetterlo, ma non riesco a risolverlo..
Il testo dell'esercizio è il seguente:
16 persone devono prendere un treno. 8 di queste persone hanno in tasca una moneta da 50 centesimi, le altre 8 hanno una moneta da un euro. Il biglietto del treno costa 50 centesimi. Inizialmente la cassa della biglietteria è vuota, e quindi non può dare resto. In quanti modi possibili possono mettersi in fila queste persone affinchè tutti possano ricevere il biglietto e il relativo resto?
Io ho ragionato in questo modo: indico con 0 le persone che hanno una moneta da 50 centesimi, con 1 le persone che hanno una moneta da 1 euro.
Abbiamo una sequenza di 16 cifre. La prima cifra deve necessariamente essere uno 0 e l'ultima un 1, quindi ne rimangono 14. Date quindi n persone, in generale devo quindi riordinarne n-2. Se proviamo a fare il conto supponendo di avere meno persone (ad esempio 4, o 6) si può arrivare al risultato direttamente calcolando il numero possibile di riordinamenti. Nel caso di 4 persone, le uniche combinazioni possibili sono 0101 e 0011. Volevo quindi trovare una formula generale che mi permettesse di risolvere il problema, e $ 2^((n/2-1) $, n pari, mi sembrava funzionasse (con n=2,4,6,8 funziona). Ovviamente questo non significa nulla, e dovrei dimostrarlo in generale (o almeno fino a n=16, ma il conto diretto diventa pallosissimo
), ma non saprei come farlo.. forse per induzione?Un altro metodo sarebbe quello di far ricorso alla probabilità di eventi dipendenti l'uno dell'altro, ma qui brancolo nel buio.. come vi ho detto, sono molto poco ferrato sull'argomento.
Aiuti sono ben accetti.
Risposte
[xdom="giammaria"]Mi sembra un problema abbastanza complicato e quindi sposto in Scervelliamoci un po'[/xdom]
Non saprei come impostare il problema, ma la tua formula non mi pare che regga: con $n=6$ io trovo 5 soluzioni, e precisamente 010101, 010011, 001011, 001101, 000111. Non regge neanche per $n=8$, per cui, salvo errori, trovo 13 soluzioni.
Ho notato una cosa, ma non è detto che sia valida in generale: posto $n=2m$ ed indicando con $C_m$ il numero di possibilità, i dati finora ottenuti (a cui aggiungo $C_1=1$) soddisfano alla formula di ricorrenza
$C_m=2C_(m-1)+((m-1)(m-2))/2" "$ (con $m>=2$)
Non saprei come impostare il problema, ma la tua formula non mi pare che regga: con $n=6$ io trovo 5 soluzioni, e precisamente 010101, 010011, 001011, 001101, 000111. Non regge neanche per $n=8$, per cui, salvo errori, trovo 13 soluzioni.
Ho notato una cosa, ma non è detto che sia valida in generale: posto $n=2m$ ed indicando con $C_m$ il numero di possibilità, i dati finora ottenuti (a cui aggiungo $C_1=1$) soddisfano alla formula di ricorrenza
$C_m=2C_(m-1)+((m-1)(m-2))/2" "$ (con $m>=2$)
Si tratta di questo http://it.wikipedia.org/wiki/Numero_di_Catalan
In particolare l'esempio: numero di cammini che collegano due vertici opposti di un quadrato quadrettato senza mai superare la diagonale. Se ci pensi è lo stesso problema visto che qua devi fare in modo che quelli che danno $50$ centesimi siano sempre almeno quanto quelli che danno $1$ euro. (E che quindi il numero di passi verso destra deve essere sempre maggiore o uguale di quelli verso l'alto, ovvero non va mai superata la diagonale).
In particolare l'esempio: numero di cammini che collegano due vertici opposti di un quadrato quadrettato senza mai superare la diagonale. Se ci pensi è lo stesso problema visto che qua devi fare in modo che quelli che danno $50$ centesimi siano sempre almeno quanto quelli che danno $1$ euro. (E che quindi il numero di passi verso destra deve essere sempre maggiore o uguale di quelli verso l'alto, ovvero non va mai superata la diagonale).
In effetti rivedendo quella formula che ho scritto, non funziona.. studiare troppa analisi evidentemente mi ha fatto male.
Per cercare di capirci qualcosa, ho cercato di arrivarci mediante l'uso della forza.. ovvero con un brutale calcolo al computer. Ho impostato il problema come una sorta di diagramma ad albero, scrivendo tutte le possibili combinazioni, e quindi cercando quali soddisfano la nostra richiesta (resto per tutti).
Mi sono saltate fuori 12870 strade (e ce lo potevamo aspettare, è $ ( (16), (8) ) $ ) , di cui 1430 sono buone. 1430 è la nostra risposta quindi.. ma perchè? come posso arrivarci matematicamente?
Per cercare di capirci qualcosa, ho cercato di arrivarci mediante l'uso della forza.. ovvero con un brutale calcolo al computer. Ho impostato il problema come una sorta di diagramma ad albero, scrivendo tutte le possibili combinazioni, e quindi cercando quali soddisfano la nostra richiesta (resto per tutti).
Mi sono saltate fuori 12870 strade (e ce lo potevamo aspettare, è $ ( (16), (8) ) $ ) , di cui 1430 sono buone. 1430 è la nostra risposta quindi.. ma perchè?
come posso arrivarci matematicamente?
Non ho capito se hai letto il link di sopra. Comunque il risultato in generale è \(\displaystyle \frac{1}{n+1}\binom{2n}{n} \).
Dove in questo caso $n=8$.
Il problema lo puoi rivedere in questo modo:
Hai una griglia $8 \times 8$ con quadrati di lato $1$ e hai una moneta sullo spigolo in basso a sinistra. Di volta in volta puoi spostarla di $1$ o verso l'alto o verso destra. In quanti modi puoi farla arrivare al vertice in alto a destra senza mai farla passare sopra la diagonale?
Lo puoi rivedere in questo modo perchè ad ogni movimento a destra associ il pagamento di $50$ centesimi e ad ogni movimento in alto associ il pagamento di $1$ euro. Se la moneta non supera mai la diagonale vuol dire che i movimenti a destra sono sempre in numero maggiore o uguale di quelli verso l'alto, dunque le monete da $50$ centesimi che hanno dato sono sempre maggiori o uguali di quelle da $1$ euro, dunque hai sempre resto da dare. Il risultato di questo problema è \(\displaystyle \frac{1}{9}\binom{16}{8} = 1430\).
Premetto che non conosco un modo particolarmente bello per dimostrarlo.
So che usando la ricorrenza puoi scrivere su ogni nodo della griglia un numero che indica quanti sono i percorsi che partendo dal vertice in basso a sinistra raggiungono quel nodo senza mai superare la diagonale. Questo numero è dato dalla somma del numero scritto sul nodo alla sua sinistra più quello scritto nella sua casella sottostante. (Infatti il numero di modi con cui puoi raggiungere un nodo è dato dal numero di modi con cui puoi raggiungere quello sottostante più il numero di modi con cui puoi raggiungere quello alla sua sinistra).
In particolare tutti i numeri sui nodi della prima riga saranno $1$. E a te interessa il numero scritto nel vertice in alto a destra che è la soluzione del problema.
Mi pare che con qualche osservazione la griglia poteva essere scomposta in due griglie con la stessa legge ricorsiva in modo che la differenza tra i numeri scritti sui nodi di una griglia con i numeri scritti sui corrispondenti nodi dell'altra griglia dava il risultato che c'era sul corrispondente nodo della griglia iniziale.
Ma queste due griglie nuove erano due triangoli di tartaglia di cui uno mi pare traslato. Quindi i valori sui vari nodi erano tutti coefficienti binomiali e di conseguenza il valore su un nodo della griglia iniziale era dato dalla differenza tra due coefficienti binomiali. Non a caso il risultato è dato da \( \displaystyle \binom{2n}{n}-\binom{2n}{n-1} = \frac{1}{n+1}\binom{2n}{n}\)
Probabilmente qua http://en.wikipedia.org/wiki/Catalan_number si trova qualche dimostrazione bella
Dove in questo caso $n=8$.
Il problema lo puoi rivedere in questo modo:
Hai una griglia $8 \times 8$ con quadrati di lato $1$ e hai una moneta sullo spigolo in basso a sinistra. Di volta in volta puoi spostarla di $1$ o verso l'alto o verso destra. In quanti modi puoi farla arrivare al vertice in alto a destra senza mai farla passare sopra la diagonale?
Lo puoi rivedere in questo modo perchè ad ogni movimento a destra associ il pagamento di $50$ centesimi e ad ogni movimento in alto associ il pagamento di $1$ euro. Se la moneta non supera mai la diagonale vuol dire che i movimenti a destra sono sempre in numero maggiore o uguale di quelli verso l'alto, dunque le monete da $50$ centesimi che hanno dato sono sempre maggiori o uguali di quelle da $1$ euro, dunque hai sempre resto da dare. Il risultato di questo problema è \(\displaystyle \frac{1}{9}\binom{16}{8} = 1430\).
Premetto che non conosco un modo particolarmente bello per dimostrarlo.
So che usando la ricorrenza puoi scrivere su ogni nodo della griglia un numero che indica quanti sono i percorsi che partendo dal vertice in basso a sinistra raggiungono quel nodo senza mai superare la diagonale. Questo numero è dato dalla somma del numero scritto sul nodo alla sua sinistra più quello scritto nella sua casella sottostante. (Infatti il numero di modi con cui puoi raggiungere un nodo è dato dal numero di modi con cui puoi raggiungere quello sottostante più il numero di modi con cui puoi raggiungere quello alla sua sinistra).
In particolare tutti i numeri sui nodi della prima riga saranno $1$. E a te interessa il numero scritto nel vertice in alto a destra che è la soluzione del problema.
Mi pare che con qualche osservazione la griglia poteva essere scomposta in due griglie con la stessa legge ricorsiva in modo che la differenza tra i numeri scritti sui nodi di una griglia con i numeri scritti sui corrispondenti nodi dell'altra griglia dava il risultato che c'era sul corrispondente nodo della griglia iniziale.
Ma queste due griglie nuove erano due triangoli di tartaglia di cui uno mi pare traslato. Quindi i valori sui vari nodi erano tutti coefficienti binomiali e di conseguenza il valore su un nodo della griglia iniziale era dato dalla differenza tra due coefficienti binomiali. Non a caso il risultato è dato da \( \displaystyle \binom{2n}{n}-\binom{2n}{n-1} = \frac{1}{n+1}\binom{2n}{n}\)
Probabilmente qua http://en.wikipedia.org/wiki/Catalan_number si trova qualche dimostrazione bella
In effetti non avevo visto il tuo link. Direi che le dimostrazioni n°2 e 3 della pagina della wikipedia inglese sono abbastanza semplici da capire. Grazie mille
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo