Newsgroup: it.hobby.enigmi
Titolo: copincolla

L'allarme sul n,g, decotto mi spinge a rifarmi vivo, con questo
problema di cui non ho la soluzione.
(Ma ci sono ancora i matematici e gli statistici del n.g.?)
Ho una serie di n CD, disposti in pila uno sull'altro.
Ogni giorno prelevo un CD dalla pila, decidendo a caso (
p.es
.
lanciando una moneta) se prendere il primo, in cima alla pila, o
l'ultimo, in basso.
Poi piazzoil CD nel lettore e copio-incollo i dati sul disco rigido.
Finita l'operazione ripongo il CD nella pila; se l'avevo prelevato in
cima lo metto in fondo, e viceversa.
La domanda č:
Dopo quanti giorni posso prevedere di avere sul disco rigido i dati di
tutti i CD?
O forse la domanda si pone meglio cosě:
Qual č la probabilitŕ p(n,k) che dopo k giorni tutti i dati siano
stati copiati?
Ciao
Paolo


Qualche domanda tecnica:
1) il disco che capacita ha?
2) i contenuti dei CD sono tutti distinti o c'e' qualche file con lo 
stesso nome presente in piu' CD?
3) i contenuti del CD sono esenti da protezione dalla copia?

3) i contenuti del CD sono esenti da protezione dalla copia?
nessuna protezione

 stati copiati?
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Cosě a sentimento mi viene:
p(n, k) = (1/2)p(n, k-1) + (1/2)p[n-1, k-1)
p(1, k) = 1
p(n, 1) = 0 (se n > 1)
Sembra sensato, ma non sono sicuro.
Maurizio

 problema di cui non ho la soluzione.
mi sembra molto difficile. Ma dovrebbe esserci una soluzione elegante?
ciao
marco

 mi sembra molto difficile.
Concordo, infatti la soluzione che avevo dato è ovviamente sbagliata.
Sarà un caso che questo problema sia stato proposto in data 06.06.06?
Maurizio

 Sarà un caso che questo problema sia stato proposto in data 06.06.06?
Non l'avevo notato! mi sa che hai ragione, che sia un problema 
notoriamente diabolico?
ciao
marco

 stati copiati?
Questa ci devo pensare.
Con la teoria della rovina del giocatore è facile calcolare la probabilità, 
avendo i cd già letti in testa e n-i in coda, di leggerne uno nuovo dalla 
testa oppure dalla coda. E' più difficile calcolare le probabilità che 
questo succeda entro un certo tempo k. E poi non vedo come assemblarle.
-- 
Ciao e bentrovati, Silv:o)

 Questa ci devo pensare.
A me pare molto difficile. Se trovi qualcosa lo posti vero?!
ciao
marco


Ciao Silvio e bentornato (... e smettila di sparire sempre!... ;-) )
La tua idea è bella ma c'è qualcosa che non mi convince.
Ho provato a cambiare l'esposizione di Paolo nel modo seguente perché mi ci 
ritrovo meglio. Suppongo di avere un mazzo di n carte coperte. Scelgo la 
carta sopra o la carta sotto con uguale probabilità, se è coperta la scopro 
altrimenti la lascio comunque scoperta e la ripongo dalla parte opposta del 
mazzo da cui l'avevo presa. Questa operazione conta come una mossa. Dopo 
quante mosse avrò tutte le n carte scoperte? Dovrebbe essere equivalente al 
problema di Paolo, se non sbaglio.
La tua soluzione con i numeri triangolari è bella ma si basa su un'ipotesi 
che forse non è quella del problema in questione. Provo a ragionare così. 
Dopo avere scoperto un certo numero di carte, diciamo 3, io mi posso trovare 
in una di queste possibili situazioni (indico con i numeri le carte 
scoperte):
0 ; n-3 carte coperte; 3
1; n-3 carte coperte; 2
2; n-3 carte coperte; 1
3; n-3 carte coperte; 0
Non mi sembra che ci siano altre possibilità; le carte coperte saranno 
sempre consecutive per la natura stessa del problema. Quindi ho 4 casi 
possibili. *Se fossero equiprobabili*, avremmo la tua soluzione. 2 volte su 
4 sarò nel caso in cui da una parte ci sono 0 carte scoperte (e quindi 1 
coperta a disposizione) e una volta su due la prenderò. Questo avverrà 
quindi 2/4*1/2 = 1/4. Con probabilità 1/4 scoprirò la quarta carta e quindi 
mediamente avrò bisogno di 4 mosse per scoprire la quarta carta. Quindi in 
generale scoprirò la i-esima carta impiegando i mosse. Questa potrebbe 
essere una giustificazione, non so quanto rigorosa, alla tua idea dei numeri 
triangolari.
Il fatto però che non mi convince è che si parte dalla supposizione che i 
casi analizzati precedentemente siano equiprobabili, ma questo non credo sia 
vero. Se infatti pensiamo di avere appena scoperto la terza carta e portata 
dall'altra parte del mazzo, noi ci ritroviamo in una di queste possibili 
situazioni:
0 ; n-3 carte coperte; 3
3; n-3 carte coperte; 0
Le altre due situazioni al momento non si presentano. In questo momento la 
probabilità di scoprire la quarta carta è 1/2, non 1/4. Non saprei poi dire 
cosa succeda quando le carte già scoperte si distribuiscono più o meno 
equamente sopra e sotto il mazzo coperto. Quello che mi sembra di poter dire 
è che la distribuzione dei vari casi non sia uniforme e questo non porti 
alla soluzione da te trovata.
Ho fatto una piccola simulazioncina (se la fai anche tu, sono più 
tranquillo... tanto ci vogliono 3 minuti a scriverla) e ho visto che ad 
esempio con 100 carte, il numero di mosse si aggira attorno a un valore di 
3700, abbastanza lontano dal valore 5050 che dovrebbe risultare dalla tua 
soluzione.
Io mi fermo qui sperando di non aver detto troppe sciocchezze.
Ancora ciao!
Giorgio
Inviato da X-Privat.Org - Registrazione gratuita 
http://www.x-privat.org/join.php

 soluzione.
Io l'ho fatta, e conferma(va) esattamente i miei risultati.
Giusto per allegarti il codice, oggi ho scritto in C# la procedura. Ieri 
l'avevo scritta in VB6 senza salvarla.
PRIMA SORPRESA: conferma il tuo 3600! ieri mi dava 5050 in VB6, che cavolo!
SECONDA SORRPESA: ho tradotto il codice C# in VB6 e mi rida il 5050 
aspettato!
Quindi deve essere una questione di array 0 o 1 based, o cose simili.
Io credo a quello VB6, e penso che abbiamo fatto lo stesso errore in C!
Ti allego i due listati:
============= C# ============================================
using System;
public class MyClass
{
  public static void Main()
  {
    int tot = 0;
    int tentativi = 10000;
    for (int i=0; i<tentativi;i++)
    {
      int carte = 100;
      bool[] mazzo = new bool[carte];
      Random caso = new Random();
      int p = 0;
      int t = 0;
      int girate = 0;
      while(girate<carte)
      {
        t++;
        if(caso.Next(2)==0)
        {
          if (!mazzo[p])
          {
            mazzo[p]=true;
            girate++;
          }
          p = (p+1) % carte;
        }
        else
        {
          p = (p+carte-1) % carte;
          if (!mazzo[p])
          {
            mazzo[p]=true;
            girate++;
          }
        }
      }
      tot+=t;
    }
    Console.WriteLine("media tentativi: {0}", tot/tentativi);
    Console.ReadLine();
  }
}
============= VB6 ============================================
Public Sub ihe()
    Dim tot As Long
    Dim tentativi As Integer
    Dim carte As Integer
    Dim mazzo() As Boolean
    Dim p As Integer
    Dim t As Integer
    Dim girate As Integer
    tot = 0
    tentativi = 1000
    For i = 1 To tentativi
        carte = 100
        ReDim mazzo(carte)
        p = 0
        t = 0
        girate = 0
        Do While (girate < carte)
            t = t + 1
            If Rnd > 0.5 Then
                If Not mazzo(p) Then
                    mazzo(p) = True
                    girate = girate + 1
                End If
                p = (p + 1) Mod carte
            Else
                p = (p + carte - 1) Mod carte
                If Not mazzo(p) Then
                    mazzo(p) = True
                    girate = girate + 1
                End If
            End If
        Loop
        tot = tot + t
    Next i
    Debug.Print "media tentativi: " & tot / tentativi
End Sub
-- 
Ciao, Silv:o)

      Random caso = new Random();
fuori dal ciclo for, per avere il risultato corretto!
-- 
Ciao, Silv:o)


Ma guarda tu! L'ho scritto anch'io in C# e non mi sono posti molti problemi 
su dove mettere la creazione dell'oggetto Random. Certo, pensandoci, č 
verosimile che a ogni replica del tentativo venga generata in quel modo la 
stessa sequenza di numeri, falsando la simulazione. Buono a sapersi per il 
futuro.
Bello! Adesso la tua soluzione mi piace ancora di piů! :-)
Ciao
Giorgio 

 po' di sommatorie su tutti gli stati.
Ho trovato un paio di modi, algebrici più che intuitivi, per
giustificare il risultato, che ho dato per buono dalla rovina del
giocatore, che T(0,n) = n+1
supponiamo di appena girato n carte. Siamo nella situazione in cui
abbiamo n carte coperte in cima al mazzo e le altre scoperte sotto.
Dobbiamo scoprire la n+1-esima.
Sia Ek=T(k,n-k) il tempo medio che ci vuole per scoprire una nuova
carta quando abbiamo k carte in coda e n-k in testa. Quello che
cerchiamo è E0
E0 = 1 + 1/2 E1
questo perché almeno una mossa è necessaria, e la metà delle volte
siamo sfortunati e dobbiamo aspettare altre E1 mosse per terminare.
Analogamante:
E0   = 1 + 1/2 E1
E1   = 1 + 1/2 E2 + 1/2 E0
E2   = 1 + 1/2 E3 + 1/2 E1
E1   = 1 + 1/2 E4 + 1/2 E2
..
En-1= 1 + 1/2 En + 1/2 En-2
En   = 1 +           + 1/2 En-1
Se chiamiamo S la somma di tutti gli Ek e sommiamo le espressioni del
sistema abbiamo:
S = (n+1) + 1/2(S-E0) +1/2(S-En)
S = (n+1) + 1/2S + 1/2S - 1/2(E0 + En)
0 = (n+1) - 1/2(E0+En)
dato che per simmetria E0=En si ha finalmente
E0 = En = n+1
che è il risultato cercato
Oppure un'altra dimostrazione, stavolta per induzione:
Dobbiamo dimostrare che T(0,n) = n+1
è vero per banalmente per n=0 e n=1.
supponiamolo vero fino a k e dimostriamolo per k+2.
Io dico che
T(0,k+2) = 1 + 1/2[T(0,k) + T(0,k+2)]
Questo perché almeno una mossa è necessaria, e se siamo sfortunati ci
troviamo nella situazione in cui abbiamo 1 carta sotto e k sopra.
Civogliono T(0,k) mosse per riportare quell'unica carta sopra o tutte
le k carte da sotto a sopra, dopodiché siamo nella situazione di
partenza e dobbiamo aspettare in media altre T(0,k+2) mosse.
Un esempio:
Se dobbiamo girare la decima carta, o siamo subito fortunati oppure
avremo 8 carte sopra e 1 sotto. Con T(0,7) mosse arriviamo a girare
l'ottava carta del mazzo di 8 o l'unica che stava sotto, in entrambi i
casi riportando tutte le coperte da una parte dopodiché ci servono
T(0,9) mosse per girare la decima carta.
Torniamo alle formule:
T(0,k+2) = 1 + 1/2[T(0,k) + T(0,k+2)]
T(0,k+2) = 2 + T(0,k)
T(0,k+2) = 2 + k          per induzione
Col fatto che si dimostra per k+2 bisogna forse dividere i dispari dai
pari, ma sono dettagli.
dubito che qualcuno abbia avuto la pazienza di arrivare fino qui ;)
--  
Ciao, Silv:o)

 Questa ci devo pensare.
Anch'io ci ho pensato e non sono arrivato a risposte definitive. Le
prove che ho fatto per piccoli n mi stanno però convincendo che una
risposta semplice ed elegante, valida per tutti i casi, non esiste.
Cominciamo col dire che p(n,k) è una frazione che ha come denominatore
2^k (che sono i casi possibili). D'altra parte i casi favorevoli sono
sempre in numero pari (se scambio testa con croce il risultato è lo
stesso), quindi diciamo per fissare le idee che:
p(n,k) = a(n,k)/2^(k-1)
dove a(n,k) sono numeri interi.
Non è difficile (brute force) ricavare gli a(n,k) per valori piccoli di
n e k:
  k   1   2   3   4   5   6   7   8   9  10
n__________________________________________
  |
2 |   0   1   3   7  15  31  63 127 255 511
  |
3 |   0   0   1   3   9  21  49 105 225 465
  |
4 |   0   0   0   1   3  10  25  63 144 327
  |
5 |   0   0   0   0   1   3  11  28  76 178
Per n=2 troviamo il risultato ovvio: a(2, k) = 2^(k-1) - 1.
Per n=3 le cose si complicano, però dando un'occhiata alla tabella si
vede che vale ad esempio la relazione ricorsiva:
a(3, k) = a(2, k-1) + 2a(3, k-2)
e da qui si può ricavare il risultato esplicito:
a(3, k) = 1 + 2^(k-1) - 3*2^(k/2-1)      [per k pari]
a(3, k) = 1 + 2^(k-1) - 2^((k+1)/2)      [per k dispari] 
Purtroppo per a(4, k) non vale l'analoga relazione ricorsiva; pare
invece che valga:
a(4, k) = a(3, k-1) + a(4, k-2) + a(4, k-3) + ... + a(4, 1)
Per n = 5, infine, pare che i numeratori abbediscano ad una relazione
ricorsiva ancora diversa:
a(5, k) = a(4, k-1) + a(5, k-2) + 2*a(5, k-4)
Insomma, non vedo emergere nessun pattern definito, ogni n sembra un
caso a se'. D'altra parte il semplice risultato per la media farebbe
sperare che emerga uno schema universale, ma non sono molto ottimista.
Maurizio

 sperare che emerga uno schema universale, ma non sono molto ottimista.
Ho controllato su Sloane, e i casi favorevoli corrispondono al numero di 
stringhe binarie n-unbalanced di lunghezza k, mentre i casi sfavorevoli sono 
le stringhe binarie n-balanced.
Una stringa è n-balanced se in ogni sottostringa la differenza massima tra 
gli "0" e gli "1" è k.
La cosa non mi sorprende. Se utilizziamo una sequenza n-balanced di pescate 
da sopra e sotto, non riusciamo mai a girare tutte le n carte, ma al massimo 
n-1.
Purtroppo anche lì il massimo che sono riusciti a trovare sono relazioni 
ricorsive come quelle che hai trovato tu.
-- 
Ciao, Silv:o)

 ricorsive come quelle che hai trovato tu.
mannaggia, cmq il fatto che siano già classificati come numeri e non ci 
sia un'espressione chiusa mi sa che è un indizio di difficoltà.
m

Paolo Licheri, al quale rivolgo un saluto affettuoso, propone
[cut]
Ciao Silvio, bentornato e grazie del saluto.
Devo scusarmi se, per cosě dire, ho lanciato il sasso e nascosto la
mano, ma anch'io ultimamente non ho avuto molto tempo per seguire il
n.g.
Comunque noto con piacere che il problema ha suscitato interesse,
appena possibile mi studierň le soluzioni proposte.
Paolo