Il posto davanti libero.

[Erasmus]

astromauh

Il tuo programmino, verificava anche cosa succede con P ed F diversi?

Sì.
Il numero di posti p per fila e il numero di file f erano piccoli (tra 3 e 5) perché il programmino era "grafico". Disegnava una matrice di f righe per p colonne di caratteri diversi: "–"per il posto libero e "•" per quello occupato. I numeri p, (posti per fila), f (numero di file) ed s (numero di spettatori) erano tre costanti: bisognava scriverle nel codice sorgente. Una volta lanciato, il programma faceva solo un esempio, quello appunto con quei numeri p, f ed s.
I numeri piccoli servivano per procedere , volendo, alla variazione della situazione un passo alla volta manualmente premendo un tasto.
Ma lo scopo era dimostrare che il conteggio dei casi "coppie di sedie dietro-occupata/davanti-libera" diviso per il numero totale di "coppie di sedie dietro/davanti" dava lo stesso rapporto di quello della formula:
[(f–1)/f]*[(p*f – s)/(p*f–1)]

astromauh

Ho capito che non hai usato P=10 ed F=10, ma dei valori molto più piccoli, altrimenti il numero delle permutazioni possibili sarebbe troppo alto, ...

Non ti rispondo ... del tutto perché aspetto che qualcuno suggerisca un preciso algoritmo per il conteggio da fare.
Però ... (scusa la deformazione "professionale" del vecchio insegnante), non si deve parlare di permutazioni! E' vero che gli spettatori sono "individui distinti". Ma qua non interessa se è costui o colui che sta seduto davanti alla sedia "fila Nr X, posto Nr Y": come non mi interessa, in una miscela di ossigeno e azoto, l'identità delle molecole ma solo il saper distiguere quelle di azoto da quelle di ossigeno, (se ... riuscissi a contare una per una le molecole di un certo volume di miscela di ossigeno O2 e azoto N2, se riuscissi a distinguere quelle di O2 da quelle di N2 e il mio scopo fosse il calcolo delle percentuali di O2 e N2 della miscela).

Forse ho fatto una inutile lungaggine.

Insomma: le permutazioi si fanno su una N-pla di elementi distinti e sono N!
Se da quella N-pla prendo arbitrariamente k (minore o uguale ad N) elementi, posso fabbricare
N*(N-1)* ...*(N–k+1) = N!/(N-k)!
disposizioni (= file) distinte una da ogni altra, vuoi per elementi scelti, vuoi per l'ordine in cui li dispongo, vuoi per entrambe le cose.

I numeri di 4 cifre (in base 10) sono tutti distinti e sono 10^4= 10*10*10*10 = 10000: ma non sono obbligati ad avere le cifre distinte!

Ovviamente, i numeri di 4 cifre tutte distinte sono
D(10,4) = 10*9*8*7 = 7830 < 10000

Scelte 4 cifre precise (e distinte) delle 10, i numeri distinti che posso fare con queste sono solo 4! =24.

astromauh

... ma nel tuo programmino P era sempre uguale ad F, e P ed F erano sempre pari?

No. A suo tempo avevo provato, se non ricordo male, varie coppie (p,f) sempre con p*f non maggiore di 30, (e può anche darsi che non abbia mai provato p=5 e f=6 o viceversa). Ma senz'altro avevo provato p=f = 3, p=f=4, p=3 e f=4, p=4 e f = 3; e anche p=5 e f=3 come pure p=3 e f=5
Al pari e dispari non ho mai pensato. Ma certamente la cosa è irrilevante...

[luranz]

astromauh

Questo perchè gli spettatori scelgono il posto in cui si siedono, e quindi se possono scelgono un posto dove non ci sia nessuno davanti.

Se poi gli spettatori fossero anche saggi, solo il 3,8% si troverebbe con qualcuno davanti... quanta ignoranza!

[astromauh]

luranz

Se poi gli spettatori fossero anche saggi, solo il 3,8% si troverebbe con qualcuno davanti... quanta ignoranza!

Si, in una distribuzione ottimale si può fare in modo che solo 2 dei 52 spettatori, abbiano il posto davanti occupato da un altra persona, che equivalgono a (50/13)% ossia a circa il 3,8%. Ma supponi che sei andato al cinema con una ragazza conosciuta da poco, forse è più saggio tenersela vicina.

[astromauh]

Erasmus

Però ... (scusa la deformazione "professionale" del vecchio insegnante), non si deve parlare di permutazioni! E' vero che gli spettatori sono "individui distinti". Ma qua non interessa se è costui o colui che sta seduto davanti alla sedia "fila Nr X, posto Nr Y": come non mi interessa, in una miscela di ossigeno e azoto, l'identità delle molecole ma solo il saper distiguere quelle di azoto da quelle di ossigeno, (se ... riuscissi a contare una per una le molecole di un certo volume di miscela di ossigeno O2 e azoto N2, se riuscissi a distinguere quelle di O2 da quelle di N2 e il mio scopo fosse il calcolo delle percentuali di O2 e N2 della miscela).

Forse ho fatto una inutile lungaggine.

Naturalmente ho notato che il problema è diverso da quello del test di Randi, perchè non importa l'identità degli spettatori, ma soltanto il posto che occupano, ma credevo che si potesse parlare anche in questo caso di permutazioni, adesso che so che il termine non è corretto non l'userò più, ma allora come si dice?

Erasmus

Insomma: le permutazioi si fanno su una N-pla di elementi distinti e sono N!
Se da quella N-pla prendo arbitrariamente k (minore o uguale ad N) elementi, posso fabbricare
N*(N-1)* ...*(N–k+1) = N!/(N-k)!
disposizioni (= file) distinte una da ogni altra, vuoi per elementi scelti, vuoi per l'ordine in cui li dispongo, vuoi per entrambe le cose.

I numeri di 4 cifre (in base 10) sono tutti distinti e sono 10^4= 10*10*10*10 = 10000: ma non sono obbligati ad avere le cifre distinte!

Ovviamente, i numeri di 4 cifre tutte distinte sono
D(10,4) = 10*9*8*7 = 7830 < 10000

Scelte 4 cifre precise (e distinte) delle 10, i numeri distinti che posso fare con queste sono solo 4! =24.

No. A suo tempo avevo provato, se non ricordo male, varie coppie (p,f) sempre con p*f non maggiore di 30, (e può anche darsi che non abbia mai provato p=5 e f=6 o viceversa). Ma senz'altro avevo provato p=f = 3, p=f=4, p=3 e f=4, p=4 e f = 3; e anche p=5 e f=3 come pure p=3 e f=5
Al pari e dispari non ho mai pensato. Ma certamente la cosa è irrilevante...

Ovviamente, i numeri di 4 cifre tutte distinte sono
D(10,4) = 10*9*8*7 = 7830 < 10000

Ah!



Non ho ben capito cosa sarebbe

N!/(N-k)!

ma adesso sono un po' stanco, ciao.

[Mizarino]

aleph

Ehi Miza, mi dispiace....
Che scocciatura 'ste cose...

Grazie del pensiero ...
In realtà sono rimasto di buon umore, pensando a Valerio che rifiutava sdegnosamente l'anestesia, e a cosa avrei detto io ad una siffatta proposta ...

[Erasmus]

Mizarino

Grazie del pensiero ...
In realtà sono rimasto di buon umore, pensando a Valerio che rifiutava sdegnosamente l'anestesia, e a cosa avrei detto io ad una siffatta proposta ...

A me, un dentista pazzo della "mutua" (ai tempi dell'INA) ha estratto un dente del giudizio senza anestesia, dopo avermi praticamente violentato (con l'aiuto di un robusto infermiere) ed aver finto ignobilmente che io acconsentissi al macabro esperimento. I singulti soffocati che ho emesso durante la tortura devono aver impressionato i numerosi pazienti in attesa nel corridoio. Al che il dentista è uscito a percorrere l'intero corridoio avanti ed indietro tra le due file di pazienti in attesa, a mano alzata stringendo la pinza col mio dente ben visibile, in alto, .. come un trofeo!
[Tra l'altro, essendo il dente consumato e quasi sepolto nella gengiva, oltre al dente ha estratto vari brandelli di gengiva ... ed io ho anche ingoiato un bel po' del mio sangue ...]
========================

Mentre Mizarino, oltre che del gattino, si deve occupare pure d'un canino, non c'è nessuno che propone che tipo di "processo" fare per il conteggio opportuno?

Nel quiz di Mizarino nel thread "Il test di Randi", alla fine (vuoi tramite le formule, vuoi tramite il conteggio diretto) veniva risolto completamente il quiz degli n "abbinamenti giusti" per n da 0 a 12. Procedendo numericamente, come fatto per la prima volta con successo da Luciano, bisognava "processare" ognuna delle 12! permutazioni.
Detta N = p*f la capienza della sala– f file, p posti per fila – con un certo numero s di spettatori sono possibili C(N, s) distribuzioni distinte degli s spettatori (dove C(N, s) è il numero di combinazioni delle N "sedie" della sala ad s ad s).
Ora succede che la somma di tutti i C(N, s) per s da 0 ad N vale 2^N.
D'altra parte, basta un bit per stabilire se una certa sedia è occupata o libera.
Immaginiamo di far partire un contatore "count" che conti da 0 a (2^N)-1 e di rappresentare i numeri contati in base 2. Abbiamo allora N bit che cambiano progressivamente. Quando il contatore è ad un cero numero, ci saranno s bit ad 1 e N–s bit a 0.
Allora conto le cO\L coppie sedia-occupata-dietro\sedia-libera-davanti ed incremento l'elemento s-esimo d'un array Tot[0..N] di questo numero cO\L.
Il numero di volte che mi capita di avere s bit a 1 e N–s bit a 0 è ovviamente C(N, s). Ma non mi importa affatto tenerne conto: prima o poi ciascuna delle C(N, s) distribuzioni degli s spettatori capiterà. Questo succederà per ogni s da 0 (count=0, sala vuota) ad N (count= 2^N–1, posti esauriti).

Quanto alla formula (che lascia perplessi gli specialisti di pribabilità!) ho ragionato così:
Immaginiamo che la sala sia tutta occupata, ma che solo s spettatori siano visibili, mentre N-s sono invisibili, trasparenti ... come se non ci fossero. Io sono uno degli spettatori "visibili". Davanti a me – se non sono nella prima fila ... quindi con probabilità (f–1)/f – si può sedere uno qualsiasi degli altri N–1 spettatori – me escluso –, dei quali però N – s sono invisibili. Quindi, se non sono nella prima fila, ci sono N–s casi favorevoli (i.e: che si sieda davanti a me un invisibile ) su N–1 casi totali. In definitiva:
P = [(f–1)/f]*[(N–s)/(N–1)] = [(f–1)/f]*[(p*f–s)/(p*f–1)].

[Erasmus]

Tok, tok ...C'è qualcuno ?

Cacchio: i thread che apro io sono snobbati dall'Illustrissimo e dalla co(o)rte dei suoi giannizzeri ...

[luranz]

Erasmus

Nel quiz di Mizarino nel thread "Il test di Randi", alla fine (vuoi tramite le formule, vuoi tramite il conteggio diretto) veniva risolto completamente il quiz degli n "abbinamenti giusti" per n da 0 a 12. Procedendo numericamente, come fatto per la prima volta con successo da Luciano, bisognava "processare" ognuna delle 12! permutazioni.
Detta N = p*f la capienza della sala– f file, p posti per fila – con un certo numero s di spettatori sono possibili C(N, s) distribuzioni distinte degli s spettatori (dove C(N, s) è il numero di combinazioni delle N "sedie" della sala ad s ad s).
Ora succede che la somma di tutti i C(N, s) per s da 0 ad N vale 2^N.
D'altra parte, basta un bit per stabilire se una certa sedia è occupata o libera.
Immaginiamo di far partire un contatore "count" che conti da 0 a (2^N)-1 e di rappresentare i numeri contati in base 2. Abbiamo allora N bit che cambiano progressivamente. Quando il contatore è ad un cero numero, ci saranno s bit ad 1 e N–s bit a 0.
Allora conto le cO\L coppie sedia-occupata-dietro\sedia-libera-davanti ed incremento l'elemento s-esimo d'un array Tot[0..N] di questo numero cO\L.
Il numero di volte che mi capita di avere s bit a 1 e N–s bit a 0 è ovviamente C(N, s). Ma non mi importa affatto tenerne conto: prima o poi ciascuna delle C(N, s) distribuzioni degli s spettatori capiterà. Questo succederà per ogni s da 0 (count=0, sala vuota) ad N (count= 2^N–1, posti esauriti).

Quanto alla formula (che lascia perplessi gli specialisti di pribabilità!) ho ragionato così:
Immaginiamo che la sala sia tutta occupata, ma che solo s spettatori siano visibili, mentre N-s sono invisibili, trasparenti ... come se non ci fossero. Io sono uno degli spettatori "visibili". Davanti a me – se non sono nella prima fila ... quindi con probabilità (f–1)/f – si può sedere uno qualsiasi degli altri N–1 spettatori – me escluso –, dei quali però N – s sono invisibili. Quindi, se non sono nella prima fila, ci sono N–s casi favorevoli (i.e: che si sieda davanti a me un invisibile ) su N–1 casi totali. In definitiva:
P = [(f–1)/f]*[(N–s)/(N–1)] = [(f–1)/f]*[(p*f–s)/(p*f–1)].

Mi arrendo, posso noleggiare il DVD?

[astromauh]

Erasmus

A me, un dentista pazzo della "mutua" (ai tempi dell'INA) ha estratto un dente del giudizio senza anestesia, dopo avermi praticamente violentato (con l'aiuto di un robusto infermiere) ed aver finto ignobilmente che io acconsentissi al macabro esperimento. I singulti soffocati che ho emesso durante la tortura devono aver impressionato i numerosi pazienti in attesa nel corridoio. Al che il dentista è uscito a percorrere l'intero corridoio avanti ed indietro tra le due file di pazienti in attesa, a mano alzata stringendo la pinza col mio dente ben visibile, in alto, .. come un trofeo!
[Tra l'altro, essendo il dente consumato e quasi sepolto nella gengiva, oltre al dente ha estratto vari brandelli di gengiva ... ed io ho anche ingoiato un bel po' del mio sangue ...]

Non sei contento di aver dato il tuo contributo alla scienza?

[Erasmus]

Penso che Miza una "sgamata" la darà anche qua.

Ripeto il quiz generalizzato per proporre un conteggio che verifichi se la formula che risolve il quiz è corretta.

«La sala di un cinema è dotata di f file di p posti l’una.
Con s spettatori, (s compreso tra 1 e pf inclusi), qual è la probabilità P che uno di essi abbia il posto davanti a sé libero?»

La formula da verificare è:

    f – 1    p·f – s
P = ––––– · –––––––– 
      f      p·f – 1

Propongo un algoritmo per il conteggio "esaustivo" di tutti gli "eventi possibili" con un numero s di spettatori da 1 a pf compresi. A Mizarino farà schifo: trattandosi di probabilità, lui pensa di colpo al suo Montecarlino. ...
Invece io vorrei fare come ha fatto per la prima volta Luciano Monti nel "Test di Randi": un programmino che esaurisce tutte le possibilità, conta tutti i casi possibili, (diciamo TOT questo numero), li esamina uno ad uno contando quanti di essi sono "favorevoli" (diciamo OK quest'altro numero) e fa il rapporto

P = OK/TOT.

Ecco, a parole, l'algoritmo che propongo (con preghiera ai programmatori di tradurlo in effettivo programma).

Dato il numero di file f della sala ed il numero p di posti di una fila (supponendo che la sala sia rettangolare ed abbia appunto f file ciascuna da p posti), poniamo
N = pf
e consideriamo il numero (2^N) –1. Scritto questo numero in base 2, esso è rappresentato da una fila di N caratteri tutti uguali a "1". Il numero 0, scritto con lo stesso numero N di cifre, è rappresentato da una fila di N caratteri tutti uguali a "0".
Ogni intero k tra 0 e (2^N)–1 compresi è rappresentato [in base 2] da una sfilza di N caratteri (o di numeri) che possono essere "0" o "1" a seconda del valore di k.
Immagino che gli "1" siano spettatori (occupanti una sedia delle N) e che gli "0" siano sedie vuote. A seconda del numero k, ho un certo numero s di "1" (che rappresenta il numero di spettatori). Lo stesso numero s di "uni" si ha per diversi k (tranne i due casi s=0 e s = N): precisamente ciò succede per un numero C(N, s) di volte, dove C(N,s) è il numero di combinazioni di N elementi ad s ad s. Ma di ciò non serve tener conto: variando k da 0 a (2^N)–1, la sfilza di "0" o "1" che rappresenta k descrive tutte le combinazioni possibili degli N posti della sala ad s ad s per ogni s da 0 (sala vuota: partenza del conteggio di k da k=0 rappresentato dalla sfilza di N "zeri") ad s = N (sala piena: termine del conteggio di k per k=(2^N)–1 rappresentato dalla sfilza di N "uni"), cioè tutte le possibili 2^N distribuzioni di spettatori nella sala.
Per contare k da 0 a (2^N)–1, considero un elenco E di N caratteri (o numeri), lo immagino un "contatore" e partendo dall'elenco con ogni elemento posto a "0", continuo ad aggiungere 1 fono a che "contatore" non è rappresentato dall'elenco di N "uni".

Sia dunque E(m) l'elemento m-esimo dell'elenco, con m da 1 ad N.
E(m) può essere soltanto "0" o "1".

Ho bisogno di altri due elenchi (diciamoli T e L – T come Totale, L come Libero –) di N elementi numerici T(m) e L(m), con m da 1 a N. Inizialmente metto a zero ogni T(m) e ogni L(m) .

Contati gli "uni" dell'elenco E (trovandone in tutto un certo numero s), rivisito l'elenco dal primo elemeto all'(N–p)-esimo compresi. Ad ogni E(m) =1 che trovo (con m non maggiore di N–p) incremento di una unità l'elemento T(s) dell'elenco T; e se E(m+p)=0 incremento di una unità anche l'elemento L(s).


Per simulare la rappresentazione del numero k (contato naturalmente: k = 1, 2, 3. 4, ecc) posso fare come segue, [avvertendo che, ad aogni passo dell'avanzamento di k rappresentato dalla sfilza delle N cifre binarie – s delle quali sono "1" – farò anche i dovuti incrementi degli elementi T(s) e L(s) degli elenchi T ed L].

Ripeti
m:=0; r:=0;
repeti
m:=m+1; r:=E(m); se r=0 allora E(m):=1 altrimenti E(m):= 0
fintantoché non trovi r=0;
s:=0; per m da 1 a N fa: se E(m)= "1" allora s:= s+1;
per m da 1 a N–p fa:
• se E(m)="1" allora fa
• • T(s):=T(s)+1; se E(m+p)="0" allora L(s):=L(s)+1;
fintantoché non trovi s = N .


Alla fine farò i rapporti L(s)/T(s) per s da 1 ad N.
L(s)/T(s) è la probabilità che, con s spettatori, uno spettatore abbia un posto davanti a sé e questo sia libero.

Adesso metto un programmino in TurboPascal ... tanto chiaro che un Luciano Monti, un Miza o un altro programmatore qualsiasi può convertirlo nel linguaggio (e nella struttura degli elenchi) che meglio preferisce.

Program Posto_davanti_libero;
  const p = ...; f = ...;  (* p ed f interi, pf non maggiore di 100 *)
  var E: array[1..101] of integer; T, L: array[1...100] of extended;
     m, n, r, last: integer; stop: boolean;  c: char;

  Procedure Draw_room;
    var h, i, j, spect: integer;
    begin
      spect:=0; for i:=1 to last do spect=spect+ E[i];
      writeln('MAPPA ATTUALE DELLA SALA'); writeln('Numero di spettatori: ',spect);
      writeln('NB.* = <posto occupato>; - = <posto libero>'); writeln;
      for i:=1 to f do for j:=1 to p do
        begin
          if j=1 then write('   ');
          h:=(i-1)*p+j; if E[h]=1 then write('*') else write('-');
          if j=p then writeln
        end
      writeln; writeln
    end;

  Procedure Control;    
    begin
      c:=readchar; ClearScreen; Draw_Room;  write('Vuoi smettere? [S/N]');
      repeat
        while not keypressed do;  c:=readchar; 
        if c='n' then c:='N'; if c='s' then c:='S'; stop:=(c='S')
      until (c='N') or stop;
      if not stop then
        begin ClearScreen; write('Premi un tasto per interrompere') end
    end;

  Procedure Show_results;
    begin
      ClearScreen; writeln('Spettatori  Probabilità');
      for m:=1 to last do writeln('   ',m:3,'      ',L[m]/T[m]);
      writeln; writeln('Premi un tasto per terminare'); while not keypressed do
    end;

Begin
  write('Premi un tasto per interrompere');
  for m:=1 to 101 do E[m]:=0;
  for m:=1 to 100 do begin T[m]:=0; L[m]:=0 end;
  last:=f*p; stop:=false;
  repeat
    if keypressed then begin Control; if stop then exit end;
    m:=0; r:=0;
    repeat
      m:=m+1; r:=E[m]; if r=0 then E[m]:=1 else E[m]:=0
    until (r=0);
    n:=0; for m:=1 to last do n:=n+E[m];
    for m:=1 to last–p do if E[m]=1 then 
      begin T[n]:=T[n]+1; if E[m+p]=0 then L[n]:=L[n]+1 end
  until n=last;
  Show_results
end.