Carte casuali ribaltate

[marcorossi94]

Ci sono $n$ carte su un tavolo, inizialmente tutte coperte. Ogni turno consiste nel scegliere una carta a caso tra le $n$ presenti (a prescindere che sia coperta o scoperta) e ribaltarla. Vinco quando tutte le carte sono scoperte.

Due varianti:
A) ribalto la carta a prescindere dal suo stato; quindi se era coperta diventa scoperta e viceversa
B) dopo aver scelto casualmente la carta, la scopro se era coperta; la lascio così se era già scoperta.

Dopo quanti turni mi aspetto di vincere?
NB: con turno si conta eventualmente anche la scelta di una carta che poi non ribalto (anche perché altrimenti il B sarebbe banale in n turni)

[Alemin1]

Con la versione A credo che teoricamente potresti andanare avanti all'infinito poniiamo n=2 con tutte e due le carte girate; supponiamo che tu ne giri una per un numero pari di volte e poi passi alla successiva. Alla fine dell'azione sulla singola carta essa rimarrebbe sempre col retro disposto verso l'alto.
Con variante B i movimenti sarebbero , dato che si parte con tutte le carte girate, esattamente n, le scelte della carta potrebbero però essere infinite se scegli sempre quelle già girate

[marcorossi94]

@Alemin
A: non ci siamo. è chiaro che potenzialmente potrei andare avanti all'infinito… ti chiedo l'attesa. Pensa a lanciare un dado: dopo quanti lanci mi aspetto un sei? potenzialmente (CON UN NUMERO ALTO MA FINITO DI LANCI) potrebbe anche non uscire, ma non è questa la risposta.
B: guarda l'NB. ovviamente si contano anche le carte che scelgo ma non ribalto

[Alemin1]

Lo pensavo... grazie dei chiarimenti, a sto punto la cosa si fa tosta, io passo

[axpgn]

Premesso che non ho capito la differenza tra il problema originale e la variante A, ho provato a fare il seguente ragionamento:

Variante B

Non ho "studiato" il caso generale ma solo $n=3$

Chiamo $S_i$ la situazione con $i$ carte scoperte e costruisco la seguente tabella:

	$S_0$	$S_1$	$S_2$	$S_3$
$-$	$3/3$	$-$	$-$	$S_1$
$1/3$	$2/3$	$-$	$S_2$	$-$
$2/3$	$1/3$	$S_3$	$-$	$-$

I numeri all'interno delle caselle sono la probabilità di passare dalla situazione $S_k$ nella riga alla situazione $S_h$ nella colonna; per esempio per passare da $S_1$ (una carta scoperta) a $S_2$ (due carte scoperte) la probabilità è $2/3$ mentre quella da $S_1$ a $S_1$ (cioè di pescare proprio quella già scoperta) è $1/3$.

Chiamo $P_i$ il numero di passi necessari per passare dalla situazione $S_i$ a quella finale (cioè $S_3$)

Quindi avrò:

$P_0=1+3/3P_1$ (i passi necessari per passare dalla posizione iniziale a quella finale saranno $1$, cioè la carta iniziale, più quelli delle altre posizioni $P_i$ moltiplicate ognuna per la propria probabilità

$P_1=1+1/3P_1+2/3P_2$

$P_2=1+2/3P_2+1/3P_3$

$P_3=0$

Risolvendo per $P_0$ mi vengono $5,5$ passi (mediamente)

Ho preparato la tabella anche per la variante A ma aspetto commenti ...

Forse con un po' di impegno si può generalizzare

Cordialmente, Alex

[marcorossi94]

Non esiste problema originale
C'è solo variante A e B

[marcorossi94]

Per il B io stavo pensando questa cosa:

Ho $n$ carte coperte. Dopo una mossa mi trovo nella situazione con $n-1$ carte coperte. Mi sono quindi ricondotto al caso precedente, con la sola differenza che una volta ogni n "spreco la mossa", nel senso che non prendo nessuna delle n-1 carte. Se ne spreco una ogni n, direi che il numero totale di mosse attese viene moltiplicato per $n/(n-1)$.
Ottengo quindi la relazione $x_n=1+x_{n-1}*n/(n-1)$
Quindi
$x_1=1$
$x_2=1+1*2/1=3$
$x_3=1+3*3/2=5.5$
Etc...

Ci può stare?

[axpgn]

"marcorossi94":Non esiste problema originale
C'è solo variante A e B

Allora avevo capito bene non capendo quale fosse la differenza

Per quanto possa dire io, ci può stare ma qui occorrerebbe tommik ...

[Lo_zio_Tom]

non saprei proprio....ci vorrebbe Orsoulx ma è molto che non si collega più

per $n=2$ è facile anche calcolare la media analiticamente e mi torna.....per $n=3$ già vado in apnea.....

[marcorossi94]

Il ragionamento che ho scritto in spoiler ti convince?

[axpgn]

@tommik
Se ci dici così siamo fregati

@marcorossi94
Ho provato ad applicare il tuo ragionamento alla variante A ed apparentemente avrei trovato una formula risolutiva, peccato che quando provo a fare i conti vado in contraddizione

Invece utilizzando la mia tabella per la variante A e $n=3$ giungo a questo risultato:

	$ S_0 $	$ S_1 $	$ S_2 $	$ S_3 $
$ - $	$ 3/3 $	$ - $	$ - $	$ S_1 $
$-$	$ 2/3 $	$ - $	$ S_2 $	$ - $
$- $	$ 1/3 $	$ S_3 $	$ - $	$ - $

$ P_0=1+3/3P_1 $

$ P_1=1+1/3P_0+2/3P_2 $

$ P_2=1+2/3P_1+1/3P_3 $

$ P_3=0 $

Risolvendo per $ P_0 $ mi vengono $ 10$ passi (mediamente)

Cordialmente, Alex

[marcorossi94]

Il mio ragionamento non saprei come adattarlo alla A
Perché quella volta ogni n non spreco semplicemente il turno, ma cambio situazione, perché cambia il numero di carte coperte

[axpgn]

Le soluzioni che ho trovato si possono generalizzare usando le matrici

Variante A

$P_0$	$P_1$	$P_2$	$P_3$	$...$	$P_(n-1)$	$P_n$	$T$
$-n/n$						$1$	$-1/n$
$-(n-1)/n$					$1$		$-2/n$
$-(n-2)/n$				$1$			$-3/n$
$-(n-3)/n$			$1$
		$1$					$-(n-1)/n$
$-1/n$	$1$

Cordialmente, Alex

[wanderer1]

Non si potrebbe usare la relazione: $\mathbb{E}(\mathbb{E}(X | Y)) = \mathbb{E}(X) ? $
Io me la sfangherei usando una relazione di ricorrenza. Detta $a_k$ il valore atteso di turni per avere tutte le carte scoperte partendo da un generica configurazione con esattamente $k$ carte scoperte, si ha:
A)

$ { ( a_k = k/n a_{k-1} + (1-k/n)a_{k+1} + 1 ),( a_-1 = 0 ),( a_n = 0 ):} $

B)

$ { ( a_k = (1-k/n)a_{k+1} + 1 ),( a_-1 = 0 ),( a_n = 0 ):} $

[axpgn]

Sostanzialmente mi sembrano tutte soluzioni equivalenti ... IMHO

[Settevoltesette]

Per quanto possa essere utile... per il primo punto ho calcolato questo

ho cancellato, credevo di aver scritto una grossa cassata, comunque sarà stato sicuramente sbagliato, domattina ci riprovo (forse)