Newsgroup: it.hobby.enigmi
Titolo: PESCE mangia pesce

Ci sono 10 pesci, 0,..,9 , bellamente in fila, in ordine causale (insomma:
permutazioni equiprobabili). Come e' noto "pesce grande mangia pesce
piccolo", e se e' furbo aspetta che "pesce piccolo mangi pesce ancora piu'
piccolo", in modo da avere pranzetti ben farciti.
Ad ogni passo il pesce piu' piccolo tra quelli ancora in vita puo'
"mangiare", togliendoli dalla lista, eventuali pesci piu' piccoli alla sua
portata, ovvero suoi vicini.
Es.:
4706291358
 => 470629358 => 47062958 => 476958 => 7958 => 798 => 9
      ^*            ^*       ^*^       ^*^         ^*    ^*^
Quanti pesci mangia in media ogni pesce?
Ciao, Silv:o)

 wrote:
" Ci sono 10 pesci, 0,..,9 , bellamente in fila, in ordine causale (insomma:
" permutazioni equiprobabili). Come e' noto "pesce grande mangia pesce
" piccolo", e se e' furbo aspetta che "pesce piccolo mangi pesce ancora piu'
" piccolo", in modo da avere pranzetti ben farciti.
" Ad ogni passo il pesce piu' piccolo tra quelli ancora in vita puo'
" "mangiare", togliendoli dalla lista, eventuali pesci piu' piccoli alla sua
" portata, ovvero suoi vicini.
Spiegati meglio.
Intendi dire che, dato l'insieme dei pesci che hanno come vicini pesci piu`
piccoli, il primo a mangiare sara` il minore dell'insieme?
" Quanti pesci mangia in media ogni pesce?
Io voterei per 4/3, ma non ho voglia di fare i conti precisi :-)
ciao, .mau.

 Io voterei per 4/3, ma non ho voglia di fare i conti precisi :-)
mmm...
Io volevo sapere: quanti pesci mangia in media il pesce 1? zero!
Quanti il 2? bene che gli va uno, quindi in media...
...
e quanti il 9, il barracuda?
Parlo di pesci mangiati 'vivi' ed interi, non di quelli presenti come
farcitura.
Ciao, Silv:o)

 wrote:
" > Intendi dire che, dato l'insieme dei pesci che hanno come vicini pesci
" piu`
" > piccoli, il primo a mangiare sara` il minore dell'insieme?
" 
" Mi sembrava che l'esempio postato fosse sufficientemente autoesplicativo.
" Si', il primo a mangiare sara' il piu' piccolo tra quelli che hanno vicini
" ancor piu' piccoli.
" 
" > " Quanti pesci mangia in media ogni pesce?
" >
" > Io voterei per 4/3, ma non ho voglia di fare i conti precisi :-)
" 
" mmm...
" Io volevo sapere: quanti pesci mangia in media il pesce 1? zero!
Perche`? ad esempio, in 0123456789 ogni pesce escluso 0 mangia esattamente
un pesce.
La probabilita` che il pesce 1 mangi un pesce e` la probabilita` che 1 sia
vicino a 0: delle 10! permutazioni, quelle buone sono 9 (posti dove il
"dittongo" 01 puo` stare) * 2 (01 o 10 pari sono) * 8! (le altre cifre
possono stare a caso), quindi il numero medio di pesci mangiati dal pesce 1
e` 1/5.
Per gli altri pesci, il conto e` piu` complicato, perche` devi fare una
somma di tutti i casi in cui da 0 a k-1 pesci sono gia` stati mangiati.
ciao, .mau.

 somma di tutti i casi in cui da 0 a k-1 pesci sono gia` stati mangiati.
Pero' il risultato ti stupira' ;)
Ciao, Silv:o)

 wrote:
" Pero' il risultato ti stupira' ;)
Hai ragione.
.mau.

Pero' il risultato ti stupira' ;)
Se non ho sbagliato i calcoli, trovo un risultato che in
fondo non dovrebbe stupire piu' di tanto:
Il pesce numero k mangia in media k/5 pesci.
Parto da queste considerazioni:
Per ciascun pesce k, esistono k pesci piu' piccoli e (9-k)
piu' grandi.
Se il pesce k ha alla sua destra un pesce piu' piccolo,
prima o poi mangera' a destra uno ed un solo pesce. Idem a
sinistra. Quindi ciascun pesce puo' mangiare 0,1, o 2 pesci.
Considero separatamente i casi:
k si trova ad una estremita' della fila (0.2 prob.)
k si trova in una posizione interna (0.8 prob.)
nel primo caso, k mangia 1 pesce se il vicino e' piu'
piccolo (k/9 prob), e 0 pesci se il vicino e' piu' grande
((9-k)/9 prob).
nel secondo caso puo' trovare vicini
2 pesci piccoli: k*(k-1)/(9*8) prob. mangia due pesci
2 pesci grandi: (9-k)*(9-k-1)/(9*8) prob. mangia 0 pesci
pesce piccolo a destra e grande a sinistra; k*(9-k)/(9*8)
prob. mangia 1 pesce
o viceversa: stesse prob.
sviluppando i calcoli trovo:
p(k,0)=(90-19*k+k^2)/90 prob. che k mangi 0
p(k,1)=(20*k-2*k^2)/90  prob. che k mangi 1
p(k,2)=(-k+k^2)/90      prob. che k mangi 2
da cui i pesci mangiati in media
m(k)=p(k,1)+2*p(k,2)=k/5
Perche' dico che il risultato non dovrebbe stupire?
si puo' intuire che la quantita' m(k) di pesci mangiati sia
funzione crescente della grandezza k del pesce
possiamo calcolare immediatamente m(9)
se 9 e' ad una estremita' della fila(0.2 prob) mangia 1
pesce,
se 9 si trova all'interno (0.8 prob.)  mangia due pesci
quindi
m(9)=0.2+2*0.8=1.8=9/5
abbiamo gia' visto che m(0)=0; m(1)=1/5
avendo gia' tre punti allineati, la prima cosa che mi e'
venuta in mente,prima di verificare con i calcoli esposti
sopra, e' stata la funzione lineare.
Mi conforta anche il fatto che la sommatoria degli m(k)
risulta uguale a 9, cioe' al numero di pesci mangiati (tutti
tranne il big:-)
ciao
paolo

 sopra, e' stata la funzione lineare.
mi inchino alla potenza dell'induzione.
Ciao, Silv:o)

Visto che la prima domanda l'avete fatta fuori in poco tempo, provo a tirar
fuori qualcos'altro da 'sti pesci.
Prima di tutto voglio farvi vedere che un modo alternativo di rappresentare
le stringhe dei pesci e' dato dagli alberi binari parzialmente ordinati,
dove in ogni sottoalbero i rami sinistri e destri sono i pesci mangiati
dalla radice.
Per la stringa dell'esempio 
(4706291358
) l'albero e':
                   _9_
               _.-'   '-._
            .-'           '-.
          _7_               _8_
         /   \             /
        4     6           5
             / \         /
            0   2       3
                       /
                      1
Visitandolo in ordine simmetrico (sx-radice-dx) si ottiene proprio la
stringa di partenza.
Non so a che cosa puo' servire, ma mi sembra interessante. E veniamo alla
domanda.
Chiamiamo T_k il tempo di sopravvivenza del kappesimo pesce.
Che possiamo dire della distribuzione di T_k, e della sua media?
Io ho trovato l'intera distribuzione, con un programma, e devo ancora
analizzare i risultati. Almeno per i valori medi credo ci si possa arrivare
con considerazioni tipo quelle che avete fatto per il punto precedente, ma
non ne sono sicuro. Per distribuzione intendo, per ogni k, P(T_k=n), ovvero
la probabilita' che il pesce k assista a n pasti prima di finire mangiato,
(o di andare a farsi una pennichella, se e' il barracuda n. 9). Nell'esempio
T_4=3, per capirci, perche' il pesce 4 assiste a 3 pasti (3>1, 5>3, 6>02)
prima di finire nelle fauci di 7.
Ciao, Silv:o)