Newsgroup: it.hobby.enigmi
Titolo: pillole

 risponde:
Non ti dico i conti che ho fatto (non li ho fatti :^)
Tav = 2 * n - 1 / SQRT(3) - LOG( n + 1 / 2 )
... e Silvio
Io lo so risolvere solo numericamente, ed i dati somigliano moltissimo ai
tuoi. Quella che proponi e` una approssimazione, credo, ma decisamente buona
già da n=2. Dove l'hai pescata?
Ciao, Silv:o)
...e  Stefano
L'ho fatto anch'io numerico (Markov, stato:(N:npills,H:nhalves)
trans:{(N-1,H+1),p=N/(N+H); (N,H-1),p=H/(N+H)}, trovo la probabilità
cumulativa di arrivare allo stato (0,ANY), i cui incrementi sono la
probabilità che accada a quel passo), e poi ho cercato una formula che
appattasse (pensavo che tu l'avessi :^)
1) Plot dei dati e vedo che è quasi lineare, minore di 2*n
2) Plot di 2*n-f(n) e vedo che sembra un logaritmo
3) Plot di exp(2*n-f(n)) e sembra lineare \propto (n+1/2) a tentativi trovo
1.78
S
P
O
I
L
E
R
Non conoscendo Markov, dopo essere impazzito per calcolare manualmente
alcuni valori, ho ripiegato sul programma in Turbo Pascal di cui trascrivo
il sorgente:
""""""""""""
 program SpezzaPillole;
uses dos,crt;
const
MaxPillole: byte = 31;
type
  id = record
         num:             longint;
         path:            string;
         padre:           longint;
         day,whole,half:  byte;
         prob:            real;
end;
var
   rec         : id;
   rec2        : id;
   pillole     : 0..31;
   media,somma : real;
   j,n,cont    : longint;
   up          : string;
   f           : file of id;
function b_d(ps:string):longint;
var
   l,i,k: byte;
   c:     integer;
   v:     longint;
begin
     l:=length(ps);
     v:=0;
     for i:=1 to l do begin
       val(copy(ps,i,1),k,c);
       v:=v+round(exp((l-i)*ln(2))*k);
     end;
     b_d:=v;
end;
function d_b(ps:longint):string;
var
   s,ss:     string;
begin
     s:='';
     while ps>0 do begin
       if odd(ps) then ss:='1' else ss:='0';
       s:=concat(ss,s);
       ps := ps shr 1;
     end;
     d_b:=s;
end;
function CercaPadre(p:longint): longint;
var
   l: byte;
   ps:string;
begin
     ps:=d_b(p);
     l:=length(ps);
     ps:=copy(ps,1,l-1);
     CercaPadre:=b_d(ps);
end;
begin
  cont:=0;
  media:=0;
  somma:=0;
  pillole:=0;
  while ((pillole<1) or (pillole>MaxPillole)) do begin
    clrscr;
    readln(pillole);
  end;
  clrscr;
  n:=round(exp((2*pillole-1)*ln(2))-1);
  rec.num:=0;
  rec.path:='';
  rec.padre:=0;
  rec.day:=0;
  rec.whole:=pillole;
  rec.half:=0;
  rec.prob:=1;
  assign(f,'pillole');
  rewrite(f);
  write(f,rec);
  close(f);
  j:=1;
  while j<=n do begin
      rec2.num:=j;
      rec2.path:=d_b(j);
      rec2.padre:=CercaPadre(j);
      rec2.day:=length(rec2.path);
      up:=copy(rec2.path,rec2.day,1);
      reset(f);
      seek(f,rec2.padre);
      read(f,rec);
      close(f);
      if rec.prob=0 then begin
         rec2.whole:=0;
         rec2.half:=0;
         rec2.prob:=0;
      end else if up='0' then begin
         rec2.whole:=rec.whole;
         rec2.half:=rec.half-1;
         rec2.prob:=rec.prob*rec.half/(rec.whole+rec.half);
      end else begin
         rec2.whole:=rec.whole-1;
         rec2.half:=rec.half+1;
         rec2.prob:=rec.prob*rec.whole/(rec.whole+rec.half);
         if rec2.whole=0 then begin
           inc(cont);
           somma:=somma+rec2.prob;
           media:=media+rec2.prob*rec2.day;
         end;
      end;
      reset(f);
      seek(f,FileSize(f));
      write(f,rec2);
      close(f);
      inc(j);
  end;
    writeln('Confezione da ',pillole:12,' pillola/e');
    writeln;
    writeln('Numero eventi           ',cont:2);
    writeln;
    writeln('Somma probabilità       ',somma:12:9);
    writeln;
    writeln('Numero medio di giorni  ',media:12:9);
end.
"""""""""""""
I tempi di esecuzione e le dimensioni del file che produce crescono in
misura tale da sconsigliarne l'uso oltre le 10 pillole.
La tabella che segue riporta:
          a col. 1:
il numero minimo di giorni necessari a spezzare le n pillole che è
evidentemente pari a n
          a col. 2
il numero massimo che è 2*n-1
          a col. 3
il valore f(n) calcolato col programma
          a col 4
la differenza f(n)-f(n-1) che, come può riscontrarsi, è pari al il rapporto
tra il numero massimo max(n) e n stesso
  n    min(n)   max(n)   f(n)           max(n)/n
  1    1           1          1               1
  2    2           3          2,5            1,5
  3    3           5          4,16667    1,66667
  4    4           7          5,91667    1,75
  5    5           9          7,71667    1,8
  6    6         11          9,55          1,83333
  7    7         13        11,40714    1,85714
  8    8         15        13,28214    1,87514
  9    9         17        15,17103    1,88889
10  10         19        17,07103    1,9
Il valore cercato, dunque, è in generale
f(n) = somma(i=1..n) [ max(i) / i ]
f(n) = somma(i=1..n) [ ( 2 * i - 1 ) / i ]
      oppure (che è lo stesso)
f(n) = 2 * n - somma(i=1..n) [ 1 / i ]
Scusate il ritardo.....
et

 f(n) = 2 * n - somma(i=1..n) [ 1 / i ]
Una mia vecchia conoscenza, la serie armonica.
Quello che Stefano chiamava 1/sqr(3) allora non dev'essere altro che la
costante di Eulero-Mascheroni :
f(n) = 2n + 0.57721... + logn + 1/2n - 1/12n ...

 intera?
brillantemente scopri` che
  Il valore cercato, dunque, è in generale
  f(n) = 2*n - H_n
  dove H_n e` l'ennesimo numero armonico, H_n somma(i=1..n) [1/i]
Allora ormai siamo in grado di dare una formula chiusa anche per g(n,m),
ovvero il numero medio di giorni necessari a finire la pillole intere,
partendo da una boccetta con n pillole intere e m mezze pillole.
O no?
Ciao, Silv:o)