Dannato problema combinatorico

Conteggi, probabilità, invarianti, logica, matematizzazione, ...
Rispondi
Talete
Messaggi: 745
Iscritto il: 05 giu 2014, 13:47
Località: Riva del Garda

Dannato problema combinatorico

Messaggio da Talete »

Nicola (che è un mio amico) ha $m$ biglie, alcune colorate e altre no. Sia $n\le m$. Ci sono $a_1$ biglie colorate con il colore $c_1$, $a_2$ biglie colorate con il colore $c_2$ e così via fino ad $a_n$ biglie colorate con il colore $c_n$, di modo che $a_1+a_2+\ldots+a_n\le m$. Le biglie rimanenti (anche eventualmente nessuna) sono incolori. Nicola mette le sue $m$ biglie in un sacchetto e poi ne estrae $p$ con $n\le p\le m$.

(i) Calcolare la probabilità che nelle $p$ biglie estratte ce ne sia almeno una del colore $c_i$ per ogni $1\le i\le n$.

(ii) L'eventualità del caso (i) non accade. Nicola dunque decide di fare questo algoritmo: considera le $p$ biglie estratte. Tra queste considera quelle colorate con il colore $c_i$ con $1\le i\le n$. Se non ce n'è nessuna, non fa niente. Se ce n'è almeno una, prende tutte le biglie di quel colore tranne una e le distrugge. Nicola fa questo processo per ogni $i$ tra $1$ ed $n$. Poi distrugge tutte le eventuali biglie incolori, sempre tra quelle estratte. Nicola ora ha distrutto $d$ biglie, con $p-n+1\le d\le p$ (dato che se $d$ fosse minore di $p-n$, rimarrebbero $n$ biglie di colori diversi, dunque sarebbe soddisfatta l'ipotesi del caso (i), che avevamo esclusa). Ora Nicola estrae altre $d$ biglie e le mette insieme alle $p-d$ estratte prima e non distrutte. Calcolare la probabilità che in queste $d+(p-d)$ biglie ce ne sia almeno una del colore $c_i$ per ogni $1\le i\le n$.

Sono disponibile a chiarimenti e delucidazioni, perché il problema non è facile da formalizzare (almeno secondo me). Me l'ha posto il mio amico Nicola, appunto, e da un po' ci stavamo pensando e siamo giunti ad un'ipotesi sulla soluzione.
"Sei il Ballini della situazione" -- Nikkio
"Meriti la menzione di sdegno" -- troppa gente
"Sei arrivato 69esimo? Ottima posizione!" -- Andrea M. (che non è Andrea Monti, come certa gente pensa)
"Se ti interessa stanno inventando le baricentriche elettroniche, che dovrebbero aiutare a smettere..." -- Bernardo
Avatar utente
karlosson_sul_tetto
Messaggi: 1452
Iscritto il: 10 set 2009, 13:21
Località: Napoli

Re: Dannato problema combinatorico

Messaggio da karlosson_sul_tetto »

i)
Testo nascosto:
Calcolo la probabilità richiesta con il principo di inclusione-esclusione:
è 1-probabilità che il colore $c_i$ non venga preso+probabilità che né $c_i$ né $c_j$ vengano presi...

$1-\sum\limits_{1\leq i \leq n} \binom{m-c_i}{p}+\sum\limits_{1\leq i<j \leq n} \binom{m-c_j}{p}\binom{m-c_i}{p}-\ldots (-1)^n \prod\limits_1^n \binom{m-c_i}{p}$

Dove si usa il binomiale esteso, scritto come polinomio $\binom{a}{b}=\frac{a\cdot (a-1) \cdot \ldots \cdot (a-b+1)}{b!}$ o nel caso specifico di questo esercizio $\binom{a}{b}=0$ se $a<b$
Per il secondo punto: si chiede la probabilità che per un'estrazione del "primo" tipo, la seconda contenga tutti i colori o la probabilità che facendo questa sequenza di mosse dall'inizio si ottengano tutti i colori?
Ultima modifica di karlosson_sul_tetto il 30 nov 2015, 16:12, modificato 1 volta in totale.
"Inequality happens"
---
"Chissa se la fanno anche da asporto"
Talete
Messaggi: 745
Iscritto il: 05 giu 2014, 13:47
Località: Riva del Garda

Re: Dannato problema combinatorico

Messaggio da Talete »

Grazie per il primo punto ;)

Per il secondo, si intende che Nicola pesca $p$ biglie, non succede ciò che voleva nel caso (i), toglie le biglie che non gli servono e poi ne estrae tante quante ne aveva distrutte. Poi considera le biglie estratte e non distrutte (che sono le $p-d$ di prima e le $d$ nuove) e spera che queste $p$ soddisfino la richiesta del punto (i).
"Sei il Ballini della situazione" -- Nikkio
"Meriti la menzione di sdegno" -- troppa gente
"Sei arrivato 69esimo? Ottima posizione!" -- Andrea M. (che non è Andrea Monti, come certa gente pensa)
"Se ti interessa stanno inventando le baricentriche elettroniche, che dovrebbero aiutare a smettere..." -- Bernardo
Rispondi