You've got a game where you have two 5x4 boards. In each board there are 20 hidden prizes from 1 to 20 (each board has all 20 prizes).

You have 8 moves. In each move you choose a board and a unrevealed cell in that board. Then you get the prize that was hidden there and a cell in the other board is revealed, showing a prize that you'll be no longer able to get in that board.

That way, there's always the same number of revealed cells in each board.

Obviously the best strategy is to always pick a cell in the board where the lowest sum of prizes had been revealed.

My question, though, is: What's the expected win in this game?

I tried to think about creating a random variable $X_n$ that gives the win in a board after $n$ selections if you choose that board. And $Y_n$ the variable that gives the win following this strategy. Then I'd say something like $E[Y_n]=\max(X_n,X'_n)$


1 Answer 1


I doubt that one can get very far solving this without a computer, since the distribution of $X_n$ is rather complicated. Here's code that iterates over all subsets of the numbers to find the probability mass function of the sums at each stage of the game, then sums it up to find the cumulative distribution function, whose square yields the probability of the cumulative distribution function of the minimum, which can then be summed to find the expected value. Here are the expected wins per move (left column) and summed up to that move (right column), once as exact fractions and once as rounded decimals:

\begin{array}{c|cc} 1&\frac{21}{2}&\frac{21}{2}\\ 2&\frac{85}{8}&\frac{169}{8}\\ 3&\frac{289612}{27075}&\frac{6892571}{216600}\\ 4&\frac{118832791}{11046600}&\frac{58794239}{1380825}\\ 5&\frac{84608908}{7824675}&\frac{65964673}{1235475}\\ 6&\frac{1632518251}{150233760}&\frac{48269112439}{751168800}\\ 7&\frac{19138745839}{1752727200}&\frac{39530002459}{525818160}\\ 8&\frac{71435694037}{6510129600}&\frac{11777950214117}{136712721600}\\ 9&\frac{70001400461}{6347376360}&\frac{172713744912601}{1777265380800}\\ 10&\frac{860093839581}{77579044400}&\frac{2116594841613023}{19549919188800}\\ 11&\frac{237856752981}{21334237210}&\frac{25680139327791733}{215049111076800}\\ 12&\frac{237329463727}{21157921200}&\frac{28092355997112961}{215049111076800}\\ 13&\frac{47785583201}{4231584240}&\frac{30520819335387781}{215049111076800}\\ 14&\frac{39886604437}{3505454400}&\frac{235483877555603}{1536065079120}\\ 15&\frac{8622382639}{751168800}&\frac{843719292713647}{5120216930400}\\ 16&\frac{580881931}{50077920}&\frac{8854034958321}{50198205200}\\ 17&\frac{183916739}{15649350}&\frac{481643090040859}{2560108465200}\\ 18&\frac{23312191}{1949400}&\frac{4610326764760433}{23040976186800}\\ 19&\frac{110736}{9025}&\frac{978607525561981}{4608195237360}\\ 20&\frac{103}{8}&\frac{1037938039242991}{4608195237360}\\ \end{array}

\begin{array}{c|cc} 1&10.500&10.500\\ 2&10.625&21.125\\ 3&10.697&31.822\\ 4&10.757&42.579\\ 5&10.813&53.392\\ 6&10.867&64.259\\ 7&10.919&75.178\\ 8&10.973&86.151\\ 9&11.028&97.179\\ 10&11.087&108.266\\ 11&11.149&119.415\\ 12&11.217&130.632\\ 13&11.293&141.925\\ 14&11.378&153.303\\ 15&11.479&164.782\\ 16&11.600&176.382\\ 17&11.752&188.134\\ 18&11.959&200.093\\ 19&12.270&212.362\\ 20&12.875&225.237\\ \end{array}

So the expected total win in your case of $8$ moves is

$$ \frac{11777950214117}{136712721600}\approx86.151\;, $$

compared to $8\cdot\frac{21}2=84$ that you'd expect to get when choosing eight cells from a single board.

Here's a graph of the expected wins per move:

expected wins per move

The expected win increases with each move, but there's no simple relationship.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .