Newsgroup: it.hobby.enigmi
Titolo: Biancaneve e gli n nani

Biancaneve ha preparato
un cappuccio per ognuno degli n nani.
Poichč non aveva lana di uno stesso
colore aveva formato non volendo due gruppi
di nani dal cappuccio dello stesso colore
che erano diventati piuttosto ostili,
l'un gruppo contro l'altro.
Al mattino i nani salutata Biancaneve
s'inoltravano verso il bosco in fila indiana
disponendosi in ordine casuale
ma sempre in modo da lasciare uno spazio
tra se' e il nano davanti qualora fosse stato
dal cappuccio di colore diverso dal proprio.
Contando su tutte le possibili disposizioni
di nani dal cappuccio dello stesso colore
 il numero di interruzioni sulle file
quante erano in media le interruzioni in ogni fila?
Siano (per ora) 9 nani dal cappuccio rosso
e 13 nani dal cappuccio blu

anbra1 propone

Dico la prima cosa che mi viene in mente, ma ho molta fiducia che sia la 
soluzione esatta. Sono tornato a casa adesso ed ho sonno. Domani controllo.
La probabilitŕ che tra i primi due nani ci sia un buco vale
P(rb)+P(br) = 9/22*13/21 + 13/22*9/21 = 234/462 = 0.506+
Quindi mediamente ci saranno E = 0.506+ spazi tra il primo e il secondo 
nano.
Ma anche tra il secondo e il terzo e cosě via.
Ma la media della somma č la somma delle medie, quindi invece di calcolare 
la media della somma dei buchi, possiamo calcolare la somma della media dei 
buchi, posizione per posizione, e questa vale semplicemente 21 * E = 
21*234/462 = 117/11 = 10.(63)
-- 
Ciao, Silv:o)


.
.
.
.
.
.
.
.
.
.
.
.
.
Ho controllato la soluzione do ieri notte, mi pare corretta.
La generalizzazione è evidente dal metodo.
Siano r i cappelli rossi e b quelli blu.
La probabilità che in una qualsiasi coppia di nani contigui ci sia un buco 
vale:
p = P(BR)+P(RB) = 2P(BR) =  2br/[(b+r)(b+r-1)]
La cosa più difficile, ma neanche tanto, da digerire, è che questo valga per 
tutte le coppie. E' evidente per la prima, ma quelle successive non sono 
indipendenti, quindi le probabilità dovrebbero cambiare. Invece non è così. 
A priori, le probabilità sono tutte uguali. Cominciano a  cambiare mano mano 
che scopriamo i colori, perchè giustamente dobbiamo usare valori 
condizionati e i numeri cambiano. Ma a priori sono tutte uguali. Mi pare 
abbastanza ragionevole e soprattutto simmetrico.
Appurato ciò resterebbe da calcolare la media.
Chiamiamo Xi la variabile indicatrice del fatto che c'è un buco nella coppia 
i-esima. Vale 1 se il buco c'è, 0 se i nani sono dello stesso colore e 
quindi compatti.
P(Xi=1) = p = 2br/[(b+r)(b+r-1)]
P(Xi=0) = 1-p
La media di questa variabile vale E[Xi]=p, cioè p è sia la probabilità di 
trovare un buco che il numro medio di buchi in quella posizione.
La somma di Xi su tutte le posizioni (1,..,b+r-1) da il numero di buchi.
S = X1+X2+..+X(b+r-1)
Dobbiamo calcolare la media di questa somma, E[S]
Ma la media di una somma di variabili è uguale alla somma delle singole 
medie! E questo vale per variabili indipendenti, ma anche per variabili che 
indipendenti non sono, come nel nostro caso.
Quindi E[S] = E[X1+X2+..] = E[X1]+E[X2]+..
Ma abbiamo detto prima che le Xi sono tutte egualmente distribuite, quindi 
le medie coincidono.
Ecco allora la conclusione:
E[S] = (b+r-1)E[X1] = 2br/(b+r)
-- 
Ciao, Silv:o)

 Poichè non aveva lana di uno stesso

Ci ho ragionato un po''. Qui non c'e' il risultato finale, ad un certo
punto mi sono interrotto. Riprendero'.
Siano B i nani blu e R i nani rossi.
All'interno della fila, sia G il numero di gruppi continui di nani
rossi.
Indichiamo con E il numero di estremita' della fila occupate da nani
rossi (ovviamente, 0,1 o 2)
Una fila puo', per i nostri scopi, essere definita con (B,R,G,E). Il
numero di spazi e' dato da S(B,R,G,E) = G*2-E
Se a una fila definita con (B,R;G,0) aggiungiamo un nano rosso,
possiamo ottenere:
in 2 casi: (B, R+1, G+1, 1)
in R+G casi: (B, R+1, G, 0)
in B-G-1 casi: (B, R+1, G+1, 0)
Per una fila (B,R,G,1):
in 1 caso: (B, R+1, G+1, 2)
in R+G casi: (B, R+1, G, 1)
in B-G casi: (B, R+1, G+1, 1)
Per una fila (B,R;G,2):
in R+G casi: (B, R+1, G, 2)
in B-G+1 casi: (B, R+1, G+1, 1)
Possiamo partire da una fila di soli nani blu (B,0,0,0) e aggiungere i
nani rossi uno a uno, calcolando quante configurazioni otteniamo.
Eccetera (sempre che non sia un vicolo cieco o, come piu' sospetto, un
gran pantano che porta nello stesso posto di una comoda autostrada
sgombra)

Rettifica errore di battitura:
 Per una fila (B,R;G,2):
 in R+G casi: (B, R+1, G, 2)
 in B-G+1 casi: (B, R+1, G+1, 2)

 sgombra)
Forse la seconda che hai detto.
Prima un considerazione.
Il problema chiede una *MEDIA* dei buchi.
In teoria bisognerebbe enumerare tutte le possibili configurazioni, contare 
i buchi per ciascuna configurazione, sommare i buchi e dividere per il 
numero di configurazioni (e se non sono equiprobabili ci tocca anche 
ponderare le somme dando il giusto peso ad ogni addendo).
Fortunatamente quando si parla di media escono fuori un sacco di bei 
trucchetti che ti evitano un sacco di rogne.
Attnzione: se si è interessati *comunque* a *contare* si può saltare a piè 
pari una cinquantina di righe :)
<saltasenonvuoilalezioncina>
Un esempio scolastico potrebbe essere: Lanciando due dadi qual è il 
risultato medio?
Questo è facile con qualsiasi tecnica, però il metodo davvero più lungo è 
enumerare i casi possibili (1+1, 1+2, 1+3, .., 6+5, 6+6), sommare e dividere 
per 36.
Possiamo ad esempio osservare che per ogni esito (4+2 ad esempio), ce ne 
sarà uno complementare (3+5); i due eventi presi assieme hanno somma fissa 
14 e dunque media 7.
Con questo metodo è facile genralizzare a n dadi. Anche a un dado singolo.
Ancora meglio: lanciare due dadi insieme o uno alla volta non cambia poi 
molto.
Bene. Il primo dado da media 3.5, il secondo pure e dunque...
Nel nostro problema si chiede la media dei buchi.
L'osservazione che si può fare è:
Un buco in prima posizione capita se i primi due nani hanno cappelli 
differenti.
Non è che mi devo mettere a "contare" tutti i modi di piazzare 22 nani, e 
fra questi caparmi quelli che cominciano con BR o con RB! Posso 
semplicemente osservare che 9/22 delle file possibili cominciano con un 
cappuccio Rosso, e tra queste 13/21 continuano con un cappuccio Blu. Un 
numero uguale di file comincerà per BR (ogni fila BR***** ha la sua gemella 
RB*****).
Quindi in 39 casi su 77 la fila avrà un buco iniziale, 38 casi su 77 no.
Non ho contato i possibili modi in cui possono disporsi i nani! Potrebero 
essere 77000, che ne so. Se così fosse, di sicuro 39000 comincerebbero con 
due cappelli diversi e 38000 con due uguali.
Dunque, posso dire che in prima posizione "mediamente" ci saranno 39/77 di 
buco. Un po' più di mezzo buco. E in seconda posizione? Secondo me non 
cambia niente.
Ergo, nelle 21 posizioni tra un nano e l'altro ci stanno "mediamente" 117/11 
= 10.63636363 buchi.
Siamo certi che mettendoci a scrivere:
RRRRRRRRR-BBBBBBBBBBBBB (1 buco)
RRRRRRRR-B-R-BBBBBBBBBBBB (3 buchi)
RRRRRRRR-BB-R-BBBBBBBBBBB (3 buchi)
RRRRRRRR-BBB-R-BBBBBBBBBB (3 buchi)
..
RR-B-RR-BBBB-RRR-B-R-BBBBB-R-BB (9 buchi)
..
Arriviamo alla stessa conclusione? Io dico di si. Ma facciamo MOLTA più 
fatica.
</saltasenonvuoilalezioncina>
Eccoci. Se siete qui vuol dire che volete farla, 'sta fatica.
Cominciamo.
Quante sono le configurazioni con 1 buco, tipo RRRRRRRRR-BBBBBBBBBBBBB?
Facile. La configurazione prevede solo due casi:
R-B
B-R
Con due?
Intanto ci sono due possibili alternanze:
R-B-R e B-R-B.
Contiamo le R-B-R. Si tratta di formare due gruppi di R. In mezzo ci 
mettiamo le 13B. Il buco tra le 9 R può stare in 8 posti diversi, per cui 
direi che le R-B-R sono 8. Analogamente le B-R-B sono 12.
Andiamo avanti: 3 buchi.
R-B-R-B o B-R-B-R.
Contiamo le R-B-R-B. Si tratta di formare due gruppi di R e due gruppi di B, 
e poi incrociarli in tutti modi possibili. Due gruppi di R si fanno in 8 
modi, 2 di B in 12.
Incrociando i risultati, ci sono 8*12 modi diversi di costruire file 
R-B-R-B.
Le B-R-B-R neanche le conto. Sono R-B-R-B lette al contrario, quindi sono 
pure loro 96.
Andiamo avanti: 4 buchi.
R-B-R-B-R o B-R-B-R-B.
Contiamo le R-B-R-B-R. Si tratta di formare 3 gruppi di R e 2 gruppi di B, e 
poi incrociarli in tutti modi possibili.
Spiego in dettaglio come si fanno 3 gruppi di R, il resto è generalizzazione 
di questo.
Le due interruzioni R-R-R possono stare in 2 delle 8 posizioni. Per non 
farla tanto lunga le possibili combinazioni di 2 oggetti su 8 sono 
certamente note, e si indicano con C(8,2)=28. Analogamente i gruppi B-B sono 
C(12,1)=12. Quindi i gruppi R-B-R-B-R sono C(8,2)*C(12,1)=28*12=336. Le 
B-R-B-R-B sono C(12,2)*C(8,1)=66*8=528.
Ora è facile generalizzare.
Se c'è un numero pari di buchi i=2n,
le file sono C(8,n)*C(12,n-1) + C(8,n-1)*C(12,n)
Se c'è un numero dispari di file i=2n+1
le file sono 2*C(8,n)*C(12,n)
Sommando tutti i termini si ottiene 497420 possibili file, così distribuite:
buchi file
 1       2
 2      20
 3     192
 4     864
 5    3696
 6    9856
 7   24640
 8   43120
 9   69300
10   83160
11   88704
12   73920
13   51744
14   29568
15   12672
16    4752
17     990
18     220
----------
tot 497420
Facendo la media ponderata (somma di buchi*file / somma di file) si ottiene 
proprio quel 117/11 di prima.
Uff. Ce l'abbiamo fatta.
Mi ero ripormesso di riprendere il metodo del bragozzi per costruire questi 
numeri, ma ho deviato. Magari lo faccio in un post a parte. Questo è già 
troppo lungo così.
-- 
Ciao, Silv:o)

Silvio Sergio ha scritto:

Neanche il mio metodo prevede la determinazione di tutte le
configurazioni, ma direi che il tuo sia piu' comodo.
Il tuo e' basato su "numero nani rossi definito, numero blu definito,
determinare quante config ci sono al variare del numero di buchi".
Il mio e' "numero rossi definito, stabilito un criterio di equivalenza
di configurazioni (ossia appartenenza a una classe), determinare le
classi e il numero di appartenenti al variare del numero di blu" (forse
ho scambiato rossi e blu rispetto a quel che avevo detto sopra, non
fateci caso)
Gia' dalla descrizione il tuo approccio e' piu' semplice.
Forse il mio potrebbe essere piu' valido come algoritmo per un calcolo
automatizzato.

 automatizzato.
Ogni tanto ho sviluppato piccoli programmi per risolvere i problemi
proposti qui, talvolta basati su brute force, altre volte piu'
analitici.
A volte mi viene voglia di raccogliere i vari problemi, affiancarvi il
programma risolutivo e pubblicare il tutto.
Come operazione commerciale non so quanto potrebbe valere, non molto
penso. Come idea amatoriale, potrebbe essere lo spunto per un sito
carino.
Quando perdero' il posto di lavoro e avro' molto tempo libero, magari
lo faro'.
Specchio dei tempi: una volta si diceva "quando andro' in pensione"

 automatizzato.
Se parli del calcolo della media, allora non vedo come le cose possano
essere confrontabili.
Io ho fornito *la formula esplicita*. Anche se parli del secondo
approccio, quello che conta le configurazioni totali dividendole per
numero di buchi, fornisco la formula esplicita, classe per classe.
Potrei anche tentare un approccio ricorsivo, calcolando le disposizioni
con n buchi a partire da quelle con meno buchi, ma a che pro? Abbiamo
già la formula esplicita, il sogno di ogni approccio ricorsivo...
-- 
Ciao, Silv:o)
PS. occhio al quoting, plis

 PS. occhio al quoting, plis
Cosa ho sbagliato?
Forse perche' ho quotato interamente il post precedente?
E' un'abitudine dovuta al fatto che uso l'interfaccia web, non il
client di posta.
Via web i post precedenti lasciati intatti vengono compattati in un
link.
Non avevo pensato che, in effetti, chi usa il mail browser puo' avere
problemi. Ci staro' attento.

 metodo funziona, ma sara' solo per diletto..
Invece noi ci guadagnamo, coi problemi !?!?
Se non si fa per diletto e soddisfazione personale, allora perché si
gioca?
-- 
Ciao, Silv:o)

 gioca?
Intendo dire, di solito la soddisfazione e' nel trovare il risultato,
eventualmente con la soluzione piu' efficiente.
In questo caso, invece, si tratta di esplorare una soluzione gia'
stabilita come di minor livello, solo per il gusto dell'esplorazione.