Quiz: Indovina il colore

[axpgn]

Da un normale mazzo di $52$ carte, ben mescolato, ogni volta viene estratta casualmente una carta, girata a faccia in su e mostrata al giocatore.
Però prima che la carta venga girata, il giocatore deve indovinarne il colore, ma ad una condizione: egli dovrà sempre dire il colore della maggioranza delle carte rimaste ancora coperte, solo in caso di parità tra nere e rosse può tirare a indovinare il colore della prossima.

Determinare il numero atteso di carte indovinate seguendo questa strategia.



Cordialmente, Alex

[Bokonon]

Testo nascosto, fai click qui per vederlo

Voglio andare ad intuito. Ho immaginato la probabilità di vittoria sotto quelle condizioni e varia fra $1/2<p<1$. Pensando a tutte le possibili sequenze di carte nere e rosse, non vedo perché la distribuzione di p non debba essere uniforme. Quindi in media $p=3/4$ . Quindi il valore atteso è $39$. Mentre il valore atteso che la mia intuizione alcolica sia sbagliata è considerevolmente più alto

[axpgn]

No.

[ghira]

Testo nascosto, fai click qui per vederlo

30.0406647747139

?
fatto numericamente

[sellacollesella]

Per curiosità personale, mi sono limitato ad una simulazione numerica.

Testo nascosto, fai click qui per vederlo

\[
\begin{array}{|c||c||c|}
\hline
\text{numero partite} & \text{tempo impiegato} & \text{media carte indovinate} \\
\hline
10^1 & 0.04\,\text{s} & 29.5000000 \\
10^2 & 0.06\,\text{s} & 29.7800000 \\
10^3 & 0.22\,\text{s} & 30.0760000 \\
10^4 & 1.28\,\text{s} & 30.0693000 \\
10^5 & 11.4\,\text{s} & 30.0493100 \\
10^6 & 1\,\text{min} \; 48\,\text{s} & 30.0395110 \\
10^7 & 19\,\text{min} \; 13\,\text{s} & 30.0404162 \\
\hline
\end{array}
\]

The College Mathematics Journal, Volume 30, Number 3, May 1999, pp. 234-235.

Testo nascosto, fai click qui per vederlo

630 [1998, 243]. Proposed by Michael Andreoli, Miami-Dade Community College (North), Miami, FL.

From a well-shuffled deck of \(52\) cards, one card at a time is turned face up and shown to a player. Before each card is turned, the player must guess its color. The player always chooses the color that constitutes the majority of the cards unturned, guessing whimsically whenever the number of red and black cards is the same. Find the expected number of correct guesses for this strategy.

Solution by John Henry Steelman, Indiana University of Pennsylvania, Indiana, PA.

We generalize the game to a deck with \(m\) red and \(n\) black cards. Let \(E(m,n)\) denote the expected number of correct guesses. By symmetry, we see that \(E(m,n) = E(n,m)\), so we need only consider the case with \(m \ge n\). \(E(m,n)\) can be computed recursively using the relations \[
\begin{align*}
E(m,n) =
\begin{cases}
\frac{n}{m+n}E(m,n-1)+\frac{m}{m+n}\left(E(m-1,n)+1\right), & \text{if} \; m>n>0, \\
E(n,n-1)+\frac{1}{2}, & \text{if} \; m=n>0, \\
m, & \text{if} \; n=0. \\
\end{cases}
\end{align*}
\] Next we prove that for \(m \ge n\), \[
\begin{align*}
E(m,n) = m + \sum_{k=0}^{n-1} \binom{m+n}{k}/\binom{m+n}{n}. \\
\end{align*}
\] We proceed by induction on the sum \(m+n\). This result is trivial if \(m\) or \(n=0\), so assume it has been established for all arguments whose sum is smaller than \(m+n\). Then \[\small
\begin{align*}
E(m,n)
& = \frac{n}{m+n}E(m,n-1)+\frac{m}{m+n}\left(E(m-1,n)+1\right), \\
& = \frac{n}{m+n}\left(m+\sum_{k=0}^{n-2}\binom{m+n-1}{k}/\binom{m+n-1}{n-1}\right)
+ \frac{m}{m+n}\left(m+\sum_{k=0}^{n-1}\binom{m+n-1}{k}/\binom{m+n-1}{n}\right), \\
& = \frac{m\,n}{m+n}\sum_{k=0}^{n-1}\binom{m+n-1}{k-1}/\binom{m+n}{n}
+ \frac{m^2}{m+n} + \sum_{k=0}^{n-1}\binom{m+n-1}{k}/\binom{m+n}{n}, \\
& = m + \sum_{k=0}^{n-1} \binom{m+n}{k}/\binom{m+n}{n}. \\
\end{align*}
\] This completes the induction.

Using the facts that \[
\begin{align*}
\sum_{k=0}^{2n} \binom{2n}{k} = 2^{2n}
\quad \text{and} \quad
\binom{2n}{k} = \binom{2n}{2n-k}, \\
\end{align*}
\] we can simplify the result when \(m=n\) to get \[
\begin{align*}
E(n,n) = n - \frac{1}{2} + \frac{2^{2n-1}}{\binom{2n}{n}}. \\
\end{align*}
\] A straightforward calculation then establishes that the solution to the original problem is \[
\begin{align*}
E(26,26) = \frac{3724430600965475}{123979633237026} \cong 30.04\,. \\
\end{align*}
\] Also solved by EDWARD ABOUFADEL, Grand Valley State U.; DAVID M. BLOOM, Brooklyn C; MARC BRODIE, C of St. Benedict; OWEN BYER and JEREMY DOVER (jointly), Northwestern C and North Dakota State U. (respectively); DANIELE DONINI, Bertinoro, Italy; ROBERT L. DOUCETTE, McNeese State U.; MILTON P. EISNER, Mount Vernon C; KEITH EKBLAW; Walla Walla, WA; PETER GRIFFIN, California State U., Sacramento; KATHLEFN E. LEWIS, SUNY C, Oswego; DARRYL K. NESTER, Bluffton C; PHILIP OPPENHEIMER, South Norwalk, CT; ROBERT PATENAUDE, C of the Canyons; DANIEL PRATT, Laurel, MD; WILLIAM SEAMAN, Albright C; MICHAEL VOWE, Therwil, Switzerland; and the proposer. One incorrect solution was also received.

The American Mathematical Monthly, Volume 64, Number 1, January 1957, pp. 51-53.

Testo nascosto, fai click qui per vederlo

4661 [1955, 659]. Proposed by J. B. Kelly, Michigan State University.

From an urn containing \(m\) black balls and \(m\) white balls, balls are drawn one at a time without replacement. An observer guesses the outcome (black or white) of each drawing. It is assumed that at any stage he will guess black if there remain more black balls than white ones and vice versa. Determine \(E(m)\) the expected value of the number of correct guesses made during the entire procedure until all the balls have been withdrawn. Give an asymptotic formula for \(E(m)-m\).

I. Solution by Max Wyman and Leo Moser, University of Alberta.

Let \(E(n, m)\) denote the expectation for the number of correct guesses starting with \(n\) white and \(m\) black balls. An elementary consideration yields the recurrence \[
\begin{align*}
E(n,m) = \frac{\max(n,m)}{n+m} + \frac{n}{n+m}E(n-1,m) + \frac{m}{n+m}E(n,m-1), \tag{1} \\
E(0,m) = E(m,0) = m. \tag{2} \\
\end{align*}
\] Let \[
\begin{align*}
E(n,m) = \max(n,m) + f(n,m)/\binom{n+m}{n}. \tag{3} \\
\end{align*}
\] Then \((1)\) and \((2)\) take the form \[
\begin{align*}
f(n,m) = f(n-1,m) = f(n,m-1) \quad \quad n \ne m, \tag{4} \\
f(m,m) = 2f(m,m-1) + \binom{2m-1}{m}, \tag{5} \\
f(0,m) = f(m,0) = 0. \tag{6} \\
\end{align*}
\] For each \(r\), \(0 \le r \le \min(n,m)\), the function \[
\begin{align*}
\binom{n+m-2r}{n-r} \\
\end{align*}
\] satisfies \((4)\). Hence for arbitrary constants, \(b_r\), the function \[
\begin{align*}
\phi(n,m) = \sum_{r=0}^{\min(n,m)} b_r\binom{n+m-2r}{n-r} \tag{7} \\
\end{align*}
\] will satisfy \((4)\). Further, \(\phi(n,m)\) can also be made to satisfy \((6)\) by taking \(b_0=0\), and then to satisfy \((5)\) by taking \[
\begin{align*}
b_m = \binom{2m-1}{m} = \frac{1}{2}\binom{2m}{m}. \\
\end{align*}
\] Hence the solution of \((4)\), \((5)\) and \((6)\) is given by \[
\begin{align*}
f(n,m) = \frac{1}{2}\sum_{r=1}^{\min(n,m)} \binom{2r}{r}\binom{n+m-2r}{n-r} = \sum_{r=1}^{\min(n,m)} \binom{m+n}{r-1}, \tag{8} \\
\end{align*}
\] where the last form results from a familiar identity in binomial coefficients (easily established by induction).

Finally from \((3)\) and \((8)\) we have \[
\begin{align*}
E(m,m) = E(m) = m + \sum_{r=1}^m \binom{2m}{r-1}/\binom{2m}{m} = m - \frac{1}{2} + 2^{2m-1}/\binom{2m}{m}. \tag{9} \\
\end{align*}
\] Stirling's formula for \(n!\) gives the asymptotic value \(E(m)-m \sim \frac{1}{2}\sqrt{\pi\,m}\).

II. Solution by H. Kesten and J. Th. Runnenburg, Mathematical Centre, Amsterdam, Holland.

Consider the lattice points \((i,k)\) with \(0 \le i,k \le m\). We can represent every sequence of drawings by means of a path joining the point \((0,0)\) to the point \((m,m)\). Every path consists of horizontal and vertical segments of unit length connecting lattice points. A horizontal (vertical) segment corresponds to the drawing of a white (black) ball. In a point of the diagonal (i.e., a point \((r,r)\) with \(0 \le r < m\)) the probability of a correct guess is \(\frac{1}{2}\). In a point not on the diagonal a correct guess corresponds to a step towards the diagonal. For every complete path exactly \(m\) steps are towards the diagonal and \(m\) steps away from it. Therefore \(E(m) = m + \frac{1}{2}\sum_{r=0}^{m-1} P_r\), where \(P_r\) is the probability of a path meeting the diagonal at the point \((r,r)\) and is given by \[
\begin{align*}
P_r = \binom{2r}{r}\binom{2m-2r}{m-r}/\binom{2m}{m}. \\
\end{align*}
\] After simple reductions we have \[
\begin{align*}
E(m) - m = -\frac{1}{2} + \frac{1}{2} \cdot 4^m/\binom{2m}{m} = -\frac{1}{2}+\frac{1}{2}\,\sqrt{\pi\,m} + O(1/\sqrt{m}). \\
\end{align*}
\] Also solved by A. E. Currier, and the proposer.

[axpgn]

Vabbè ma così non vale

L'ho postata apposta in questa sezione per vedere una soluzione analitica (che io ho ma è complicatissima per me )


Cordialmente, Alex

[sellacollesella]

@axpgn: quella arriverà dagli esperti del settore, io arrivo fino ad un certo punto, poi...

[axpgn]

Infatti l'ho postata qui

[ghira]

L'ho fatto così. Magari cerco di farlo analiticamente ma per ora sembra un casino.

Codice:

#!/usr/bin/perl

sub v {
my $a=shift;
my $b=shift;
if ($b>$a) {
($a,$b)=($b,$a);
}
#print "$a $b\n";
if (exists $v[$a][$b]) {
         return $v[$a][$b];
         } else {
if ($b==0) {
$v[$a][$b]=$a;
         return $a;
         }
my $s=$a+$b;
$v[$a][$b]=$a/$s*(1+v($a-1,$b))+$b/$s*v($a,$b-1);

print "$a $b $v[$a][$b]\n";
return $v[$a][$b];
}
}

$val=v(26,26);