Per comodità ricordo come si gioca a NIM. Si prendono tre pile ciascuna composta da un numero qualsiasi (ma facciamo maggiore di zero per avere le tre pile) di pedine e i due giocatori A e B muovono a turno con A che inizia .Le uniche regole sono che il giocatore che muove può prendere quante pedine vuole (1,2 ...la pila intera) però da una sola pila e deve prendere almeno una pedina.Vince chi prende l' ultima pedina (o pedine),detto in altri termini perde chi non può più muovere.
Ora assumendo che
a)ogni pila contenga meno di $ 2^n $ pedine,
b)nessuna pila abbia zero pedine (quindi ci sono tre pile),
c)che i giocatori conoscano la teoria (e quindi non facciano mosse sbagliate quando giocano) e
d)che il numero delle pedine in ogni pila sia determinato a caso (sempre nell' ambito dei vincoli a) e b) ),
si calcoli $ P(n) $ ovvero la probabilità di vittoria di B in funzione di $ n $.
Chi vuole può provare a calcolare la stessa probabilità dello stesso gioco ma con la modifica che chi prende l' ultima pedina perde;è solo un pò meno semplice.
NIM e probabilità in SNS
Allora:
facciamo corrispondere a ciascuna colonna un valore. Si vede subito, se vince chi leva l'ultima pedina, che il valore di una colonna è il numero di pedine che essa contiene. Il gioco è vinto per il secondo se e solo se, mettendo in colonna i valori delle 3 colonne espressi in base 2, in ogni colonna compare la cifra 1 un numero pari di volte. Se esprimiamo i valori in codice binario, troviamo che ogni colonna può assumere qualsiasi valore che abbia almeno una cifra e non più di n. Quindi, date 2 colonne con valori scelti a caso, si può scegliere la terza in modo che il gioco sia vinto per B, tranne nel caso in cui la prima colonna sia uguale alla seconda, visto che la terza non può esser lasciata vuota. La seconda colonna può assumere $ 2^n-2 $ valori tali che esista un valore della terza colonna che consenta a B di vincere, e a quel punto la terza colonna può assumere $ 2^n-1 $ valori di cui 1 solo consente a B di vincere.
Quindi $ P(n)=\frac{(2^n-2)}{(2^n-1)^2} $
Supponiamo invece che perda chi leva l'ultima pedina.
Tranne il caso in cui ciascuna colonna contiene una pedina, una partita è vinta in questa modalità se e solo se lo sarebbe stata stabilendo che vinceva chi levava l'ultima pedina. Definiamo invariata una posizione con questa caratteristica. Si dimostra per induzione: poniamo che le colonne abbiano rispettivamente $ 2,1,1 $ pedine: la posizione è invariata. Resta da dimostrare che una posizione $ a,b,c $ è invariata se tutte le posizioni $ m,n,l $, dove $ 1<m\leq a $, $ 1<n\leq b $, $ 1<l \leq c $, $ a+b+c>m+n+l $ sono invariate. Ma ciò è evidente, perché se si considera che una posizione è vinta se e solo se da essa si può raggiungere una posizione persa per l'avversario, tra una modalità di gioco e l'altra non cambia nulla visto che le posizioni perse raggiungibili sono le medesime, fatta eccezione per i casi in cui c'è solo una pedina per colonna. Analizziamo questi casi, considerando che nella posizione di partenza almeno una colonna ha almeno 2 pedine. Se da una posizione si può raggiungere la posizione $ 1,1,1 $ allora si può raggiungere anche la posizione $ 1,1,0 $
Se da una posizione si può raggiungere $ 1,1,0 $ ma non $ 1,1,1 $, allora si può raggiungere $ 1,0,0 $
Se da una posizione si può raggiungere $ 1,0,0 $ ma non $ 1,1,0 $, allora si può raggiungere $ 0,0,0 $
Se da una posizione si può raggiungere $ 0,0,0 $, allora si può raggiungere $ 1,0,0 $
Quindi la modalità di gioco è indifferente se almeno una colonna ha almeno 2 pedine.
Quindi $ P(n)=\frac{(2^n-1)(2^n-2)+1}{(2^n-1)^3} $
P.S. Nel primo caso la soluzione del problema è più bella se levi la condizione che le colonne non sono vuote
facciamo corrispondere a ciascuna colonna un valore. Si vede subito, se vince chi leva l'ultima pedina, che il valore di una colonna è il numero di pedine che essa contiene. Il gioco è vinto per il secondo se e solo se, mettendo in colonna i valori delle 3 colonne espressi in base 2, in ogni colonna compare la cifra 1 un numero pari di volte. Se esprimiamo i valori in codice binario, troviamo che ogni colonna può assumere qualsiasi valore che abbia almeno una cifra e non più di n. Quindi, date 2 colonne con valori scelti a caso, si può scegliere la terza in modo che il gioco sia vinto per B, tranne nel caso in cui la prima colonna sia uguale alla seconda, visto che la terza non può esser lasciata vuota. La seconda colonna può assumere $ 2^n-2 $ valori tali che esista un valore della terza colonna che consenta a B di vincere, e a quel punto la terza colonna può assumere $ 2^n-1 $ valori di cui 1 solo consente a B di vincere.
Quindi $ P(n)=\frac{(2^n-2)}{(2^n-1)^2} $
Supponiamo invece che perda chi leva l'ultima pedina.
Tranne il caso in cui ciascuna colonna contiene una pedina, una partita è vinta in questa modalità se e solo se lo sarebbe stata stabilendo che vinceva chi levava l'ultima pedina. Definiamo invariata una posizione con questa caratteristica. Si dimostra per induzione: poniamo che le colonne abbiano rispettivamente $ 2,1,1 $ pedine: la posizione è invariata. Resta da dimostrare che una posizione $ a,b,c $ è invariata se tutte le posizioni $ m,n,l $, dove $ 1<m\leq a $, $ 1<n\leq b $, $ 1<l \leq c $, $ a+b+c>m+n+l $ sono invariate. Ma ciò è evidente, perché se si considera che una posizione è vinta se e solo se da essa si può raggiungere una posizione persa per l'avversario, tra una modalità di gioco e l'altra non cambia nulla visto che le posizioni perse raggiungibili sono le medesime, fatta eccezione per i casi in cui c'è solo una pedina per colonna. Analizziamo questi casi, considerando che nella posizione di partenza almeno una colonna ha almeno 2 pedine. Se da una posizione si può raggiungere la posizione $ 1,1,1 $ allora si può raggiungere anche la posizione $ 1,1,0 $
Se da una posizione si può raggiungere $ 1,1,0 $ ma non $ 1,1,1 $, allora si può raggiungere $ 1,0,0 $
Se da una posizione si può raggiungere $ 1,0,0 $ ma non $ 1,1,0 $, allora si può raggiungere $ 0,0,0 $
Se da una posizione si può raggiungere $ 0,0,0 $, allora si può raggiungere $ 1,0,0 $
Quindi la modalità di gioco è indifferente se almeno una colonna ha almeno 2 pedine.
Quindi $ P(n)=\frac{(2^n-1)(2^n-2)+1}{(2^n-1)^3} $
P.S. Nel primo caso la soluzione del problema è più bella se levi la condizione che le colonne non sono vuote
"Sei la Barbara della situazione!" (Tap)
Strano ho ricontato ma la prima parte mi pare abbastanza sicura.
Riscrivo in maniera più chiara il ragionamento, così almeno puoi dirmi con chiarezza qual è il passaggio sbagliato.
Stabiliamo che $ V_1 $ è il valore della prima colonna, $ V_2 $ il valore della seconda e $ V_3 $ il valore della terza. Tutti questi valori sono da intendersi espressi in base 2. Definiamo "somma" l'operazione che mette in colonna un determinato numero di valori e semplifica a coppie gli 1 incolonnati, dopodiché somma normalmente gli elementi rimasti. A tale operazione corrisponde il simbolo "+"
1) Ogni valore da $ 1 $ a $ 1...1 $ compare esattamente 1 volta.
2)Scelgo $ V_1 $ a caso. A questo punto abbiamo che $ V_1"+"V_2=0 $ per un solo valore di $ V_2 $
3)Se $ V_1"+"V_2=0 $, dato che per ipotesi $ V_3\not =0 $, la posizione finale è vinta per A per qualsiasi $ V_3 $ visto che ad A basta levare tutta la terza colonna per arivare ad una posizione persa per B.
4)Posso scegliere $ V_2 $ in $ 2^n-2 $ modi su $ 2^n-1 $ possibili dimodoché a B resti qualche speranza di vittoria.
5)A questo punto, avendo $ V_1 \not = V_2 $, ponendo $ V_1"+"V_2=x $ abbiamo che x (espresso in codice binario) è un numero di massimo n cifre, diverso da 0. Dunque esiste uno e un solo $ V_3 $ tale che $ V_3=x $ ovvero che $ V_1"+"V_2"+"V_3=0 $ ovvero che la partita è vinta per B.
6) Quindi le probabilità che la partita sia vinta per B sono: le probabilità che la seconda colonna sia diversa dalla prima per le probabilità che la terza colonna abbia un valore che corrisponde alla "somma" della prima con la seconda.
Espresso in numeri ciò corrisponde a
$ \frac{2^n-2}{2^n-1}*\frac{1}{2^n-1} $
Quale dei punti ti sembra sbagliato?
Riscrivo in maniera più chiara il ragionamento, così almeno puoi dirmi con chiarezza qual è il passaggio sbagliato.
Stabiliamo che $ V_1 $ è il valore della prima colonna, $ V_2 $ il valore della seconda e $ V_3 $ il valore della terza. Tutti questi valori sono da intendersi espressi in base 2. Definiamo "somma" l'operazione che mette in colonna un determinato numero di valori e semplifica a coppie gli 1 incolonnati, dopodiché somma normalmente gli elementi rimasti. A tale operazione corrisponde il simbolo "+"
1) Ogni valore da $ 1 $ a $ 1...1 $ compare esattamente 1 volta.
2)Scelgo $ V_1 $ a caso. A questo punto abbiamo che $ V_1"+"V_2=0 $ per un solo valore di $ V_2 $
3)Se $ V_1"+"V_2=0 $, dato che per ipotesi $ V_3\not =0 $, la posizione finale è vinta per A per qualsiasi $ V_3 $ visto che ad A basta levare tutta la terza colonna per arivare ad una posizione persa per B.
4)Posso scegliere $ V_2 $ in $ 2^n-2 $ modi su $ 2^n-1 $ possibili dimodoché a B resti qualche speranza di vittoria.
5)A questo punto, avendo $ V_1 \not = V_2 $, ponendo $ V_1"+"V_2=x $ abbiamo che x (espresso in codice binario) è un numero di massimo n cifre, diverso da 0. Dunque esiste uno e un solo $ V_3 $ tale che $ V_3=x $ ovvero che $ V_1"+"V_2"+"V_3=0 $ ovvero che la partita è vinta per B.
6) Quindi le probabilità che la partita sia vinta per B sono: le probabilità che la seconda colonna sia diversa dalla prima per le probabilità che la terza colonna abbia un valore che corrisponde alla "somma" della prima con la seconda.
Espresso in numeri ciò corrisponde a
$ \frac{2^n-2}{2^n-1}*\frac{1}{2^n-1} $
Quale dei punti ti sembra sbagliato?
"Sei la Barbara della situazione!" (Tap)
Francamente già al punto 2) noto qualche problemino.Scusa ma non dovrebbe essere all' incirca così: 1)prendo a caso $ V_1 $ e $ V_2 $ (e CONTO in quanti modi posso farlo) , a questo punto $ V_3 $ è determinato in modo tale che $ V_1"+"V_2"+"V_3=0 $ dato che voglio trovare tutte le possibili posizioni in cui B vinca ( e A perda),2) poi non mi resta che contare le configurazioni possibili (stando attento però a come ho contato nel punto 1)), 3)faccio il rapporto.Come tu stesso puoi notare l' unico prerequisito dell' esercizio è leggere al posto di probabilità casi favorevoli su casi possibili (facendo finta di essere ancora nel 1600 dato che è la vecchia definizione che usavano Pascal e company nel XVII secolo) e fare due moltiplicazioni per non dover CONTARE 1,2,3...
Ovviamente ciò che ho scritto è un vago hint dato che prima di inviare la mia soluzione preferisco lasciare provare chi ha ancora voglia di pensarci .
Ovviamente ciò che ho scritto è un vago hint dato che prima di inviare la mia soluzione preferisco lasciare provare chi ha ancora voglia di pensarci .
Ultima modifica di herbrand il 12 ott 2006, 17:43, modificato 1 volta in totale.
Eppure il punto 2 mi pare il più ovvio...
Sarò cocciuto, ma mi pare che tu stia trascuando che $ V_3\not =0 $
Ovviamente la coppia dei primi 2 valori posso calcolarla in $ (2^n-1)^2 $ modi. A questo punto posso scegliere un adeguato $ V_3 $ se e solo se $ V_1\not = V_2 $
Infatti se $ V_1=V_2 $ allora per qualsiasi $ V_3 $, dal momento che la terza colonna non è nulla, la partita è vinta per A. Infatti, ripeto, gli basta togliere tutta la terza colonna. A questo punto ogni volta che B leva k pedine da una colonna, A leva k pedine dall'altra colonna. In questo modo, ovviamente, leva l'ultima pedina e vince.
Se $ V_1\not = V_2 $ allora la loro "somma" è un valore maggiore di 0 e minore di $ 2^n $ quindi esiste un $ V_3 $ adatto a far vincere B.
Di conseguenza devo scegliere le prime 2 colonne dimodoché siano diverse, poi scelgo la terza (in un solo modo possibile)
Invece, se levi l'ipotesi che tutte le colonne hanno almeno una pedina, questo problema non si pone e le probabilità sono $ \frac{1}{2^n} $
Se preferisci rispondi per messaggio privato.
Ciao!
Sarò cocciuto, ma mi pare che tu stia trascuando che $ V_3\not =0 $
Ovviamente la coppia dei primi 2 valori posso calcolarla in $ (2^n-1)^2 $ modi. A questo punto posso scegliere un adeguato $ V_3 $ se e solo se $ V_1\not = V_2 $
Infatti se $ V_1=V_2 $ allora per qualsiasi $ V_3 $, dal momento che la terza colonna non è nulla, la partita è vinta per A. Infatti, ripeto, gli basta togliere tutta la terza colonna. A questo punto ogni volta che B leva k pedine da una colonna, A leva k pedine dall'altra colonna. In questo modo, ovviamente, leva l'ultima pedina e vince.
Se $ V_1\not = V_2 $ allora la loro "somma" è un valore maggiore di 0 e minore di $ 2^n $ quindi esiste un $ V_3 $ adatto a far vincere B.
Di conseguenza devo scegliere le prime 2 colonne dimodoché siano diverse, poi scelgo la terza (in un solo modo possibile)
Invece, se levi l'ipotesi che tutte le colonne hanno almeno una pedina, questo problema non si pone e le probabilità sono $ \frac{1}{2^n} $
Se preferisci rispondi per messaggio privato.
Ciao!
"Sei la Barbara della situazione!" (Tap)
Francamente è irrilevante ai fini del calcolo della probabilità ed infatti quando nell' hint ho scritto ,
mi riferivo proprio a questo fatto. Comunque , per la cronaca consiglio di considerarli UGUALI (perlomeno mi è sembrato naturale vederli come tali)(stando attento però a come ho contato nel punto 1)),
Allora, se consideriamo la probabilità come casi favorevoli/casi probabili considerando le terne ordinate (e mi pare che il testo sia espilicito in questo senso) ha ragione piever... Tento di rispiegarlo:
Per la teoria dei giochi simmetrici il gioco è vinto per B se la somma (intesa come xor) dei valori delle tre colonne fa zero. Se due colonne sono uguali chiaramente questo non è possibile (il terzo valore sarà anche quello dello xor) quindi dobbiamo prendere la prima distinta dalla seconda, e la terza uguale all'"inverso binario" (1 a posto di 0 e viceversa) della somma xor dei primi 2. Quindi le possibilità sono
$ $ (2^n-1)(2^n-2)*1 $. Le possibili partite sono invece chiaramente $ $ (2^n-1)(2^n-1)(2^n-1) $. Quindi la probabilità è:
$ $ \frac{2^n-2}{(2^n-1)^2} $
Per la teoria dei giochi simmetrici il gioco è vinto per B se la somma (intesa come xor) dei valori delle tre colonne fa zero. Se due colonne sono uguali chiaramente questo non è possibile (il terzo valore sarà anche quello dello xor) quindi dobbiamo prendere la prima distinta dalla seconda, e la terza uguale all'"inverso binario" (1 a posto di 0 e viceversa) della somma xor dei primi 2. Quindi le possibilità sono
$ $ (2^n-1)(2^n-2)*1 $. Le possibili partite sono invece chiaramente $ $ (2^n-1)(2^n-1)(2^n-1) $. Quindi la probabilità è:
$ $ \frac{2^n-2}{(2^n-1)^2} $
"Ma devo prendere una n-upla qualsiasi o una n-upla arbitraria?" (Lui)
Allora, cercherò di esser breve. Sulla "teoria" (dei giochi simmetrici, "inversi binari" e comunque vogliate chiamarli ) siamo tutti d' accordo e credo che lo fossero anche i cinesi (ma solo i più accorti) che si trastullavano (poveri loro) con questo tipo di giochi più di mille anni or sono . Questo NON è l' esercizio.
Non avete considerato ( contato) con attenzione le possibilità, ecco tutto. D' altro canto non siete lontanissimi, voglio dire almeno non vi viene un numero maggiore di uno
.
@Boll (anche se non è essenziale )
Boll wrote:
Non avete considerato ( contato) con attenzione le possibilità, ecco tutto. D' altro canto non siete lontanissimi, voglio dire almeno non vi viene un numero maggiore di uno
.@Boll (anche se non è essenziale )
Boll wrote:
, ti ricordoconsiderando le terne ordinate
, scusa ma i giochi 1,3,2 e 1,2,3 ti sembrano così diversi? Se sì allora considerali, per finta uguali...considerarli UGUALI
Bastava chiarirlo nel testo... Non ci siamo sbagliati, era poco chiaro... Detto questo è chiaro che una posizione vincente per B non avrà mai due colonne uguali, quindi quello ci basta dividerlo per 3 e dobbiamo solo ricontare tutti i giochi possibili che diventano, non contando l'ordine
$ $ X=\frac{(2^n-1)(2^n-2)(2^n-3)}{6}+(2^n-1)(2^n-2)+(2^n-1) $
quindi la probabilità è
$ $\frac{(2^n-1)(2^n-2)}{6X} $
Messo in funzione di $ 2^n $
$ $\frac{2^n-2}{2^n(2^n+1)} $
EDIT: messo in f(2^n)
$ $ X=\frac{(2^n-1)(2^n-2)(2^n-3)}{6}+(2^n-1)(2^n-2)+(2^n-1) $
quindi la probabilità è
$ $\frac{(2^n-1)(2^n-2)}{6X} $
Messo in funzione di $ 2^n $
$ $\frac{2^n-2}{2^n(2^n+1)} $
EDIT: messo in f(2^n)
Ultima modifica di Boll il 12 ott 2006, 22:26, modificato 4 volte in totale.
"Ma devo prendere una n-upla qualsiasi o una n-upla arbitraria?" (Lui)