On Share And Share Alike

| 0 Comments

When last they met, the Baron challenged Sir R----- to a wager in which, for a price of three coins and fifty cents, he would make a pile of two coins upon the table. Sir R----- was then to cast a four sided die and the Baron would add to that pile coins numbering that upon which it settled. The Baron would then make of it as many piles of equal numbers of no fewer than two coins as he could muster and take back all but one of them for his purse. After doing so some sixteen times, Sir R----- was to have as his prize the remaining pile of coins.

The upshot of these rules is that at each turn the pile of coins would be reduced to the lowest prime factor of the number that it had after those indicated by the die were added, the primes being those positive integers that cannot be wholly divided by any positive integers other than themselves and one. For example, if Sir R----- had started a turn with seventeen coins and had thrown a one then he would have ended it with
\[ 17+1 = 18 = 3^2 \times 2 \to 2 \]
coins.
The first consequence of this is that the pile could only consist of a prime number of coins at the end of a turn.
The second is that it could never be larger than twenty three coins, since
\[ \begin{align*} 23+1 &= 24 = 3 \times 2^3 = \left(3 \times 2^2\right) \times 2 \to 2\\ 23+2 &= 25 = 5^2 = 5 \times 5 \to 5\\ 23+3 &= 26 = 13 \times 2 \to 2\\ 23+4 &= 27 = 3^3 = 3^2 \times 3 \to 3 \end{align*} \]
We need therefore only consider the implications of the rules of the wager for piles of two, three, five, seven, eleven, thirteen, seventeen, nineteen and twenty three coins in order to figure its fairness.

If we construct a table showing how many ways Sir R----- could start and end a turn with some numbers of coins in the pile by column and row respectively

Start   2      3      5      7     11     13     17     19     23   
End
2222222222
311111111
5111
711
111
131
171
191
231

create a matrix of its elements, and multiply it by one quarter
\[ \mathbf{M} = \begin{pmatrix} 2 & 2 & 2 & 2 & 2 & 2 & 2 & 2 & 2\\ 1 & 0 & 1 & 1 & 1 & 1 & 1 & 1 & 1\\ 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 1\\ 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \end{pmatrix} \times \frac14 \]
then the result \(\mathbf{M}\) is the transition matrix of a turn, representing the probabilities of beginning and ending it with the numbers of coins associated with the table's columns and rows.
If we further define a vector \(\mathbf{v}\) with
\[ \mathbf{v} = \begin{pmatrix} p_2\\ p_3\\ p_5\\ p_7\\ p_{11}\\ p_{13}\\ p_{17}\\ p_{19}\\ p_{23} \end{pmatrix} \]
where \(p_n\) is the probability that the pile contains \(n\) coins at the start of a turn, then \(\mathbf{M} \times \mathbf{v}\) is a vector whose elements correspond to the probabilities that it should contain a given number of coins at the end of that turn.
That this is necessarily so follows firstly from the fact that the transitions from a particular starting number of coins to a particular ending number are independent, meaning that we may simply multiply the probabilities of the former by the probabilities of those transitions and add together the resulting probabilities of each of the latter and secondly that, by the rules of matrix-vector multiplication, we have
\[ \left(\mathbf{M} \times \mathbf{v}\right)_i = \sum_j \mathbf{M}_{ij} \times \mathbf{v}_j \]
where \(\sum\) is the summation sign, which is trivially that sum of the products of those probabilities.

Now it must also be the case that if the probabilities of the pile having particular numbers of coins at the start of a turn are \(\mathbf{M} \times \mathbf{v}\), then at the end of that turn they must be
\[ \mathbf{M} \times (\mathbf{M} \times \mathbf{v}) = \mathbf{M}^2 \times \mathbf{v} \]
and so if they were instead \(\mathbf{v}\) at the start of a turn, they will be \(\mathbf{M}^2 \times \mathbf{v}\) at the end of the following turn, since the rolls of the die at each turn are also independent.
Carrying on in the same fashion, we find that if the probabilities were \(\mathbf{v}\) at the start of the game then they should be \(\mathbf{M}^{16} \times \mathbf{v}\) at its conclusion.

Such probabilistic systems are known as Markov chains and are of tremendous utility when it comes to figuring the probabilities of the outcomes of processes for which the transitions between various states at any given time are independent of those that have come before, not least for the ease with which we may use matrices and vectors to do so. I said as much to the Baron, but I fear that I may not have had his full attention.

Now we may spare ourselves some considerable effort by noting that
\[ \begin{align*} \mathbf{M}\phantom{^2} \times \mathbf{M}\phantom{^2} &= \mathbf{M}^2\\ \mathbf{M}^2 \times \mathbf{M}^2 &= \mathbf{M}^4\\ \mathbf{M}^4 \times \mathbf{M}^4 &= \mathbf{M}^8\\ \mathbf{M}^8 \times \mathbf{M}^8 &= \mathbf{M}^{16} \end{align*} \]
and so we need but four matrix multiplications to figure the probabilities of the pile having any particular number of coins at the game's end. With some small measure of patience my fellow students and I have reckoned these to equal
\[ \begin{align*} \mathbf{M}^2 &= \begin{pmatrix} 8 & 8 & 8 & 8 & 8 & 8 & 8 & 8 & 8\\ 3 & 4 & 3 & 3 & 3 & 3 & 3 & 3 & 3\\ 3 & 2 & 3 & 3 & 3 & 3 & 3 & 4 & 3\\ 2 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 2\\ 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \end{pmatrix} \times \frac{1}{4^2} \\ \\ \mathbf{M}^4 &= \begin{pmatrix} 128 & 128 & 128 & 128 & 128 & 128 & 128 & 128 & 128\\ 51 & 52 & 51 & 51 & 51 & 51 & 51 & 51 & 51\\ 45 & 44 & 45 & 45 & 45 & 46 & 45 & 45 & 45\\ 24 & 24 & 24 & 24 & 24 & 24 & 25 & 24 & 24\\ 6 & 6 & 6 & 6 & 6 & 6 & 6 & 7 & 6\\ 2 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 2\\ 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \end{pmatrix} \times \frac{1}{4^4} \\ \\ \mathbf{M}^8 &= \begin{pmatrix} 32,768 & 32,768 & 32,768 & 32,768 & 32,768 & 32,768 & 32,768 & 32,768 & 32,768\\ 13,107 & 13,108 & 13,107 & 13,107 & 13,107 & 13,107 & 13,107 & 13,107 & 13,107\\ 11,471 & 11,469 & 11,470 & 11,470 & 11,470 & 11,470 & 11,470 & 11,470 & 11,471\\ 6,144 & 6,145 & 6,145 & 6,144 & 6,144 & 6,144 & 6,144 & 6,144 & 6,144\\ 1,536 & 1,536 & 1,536 & 1,537 & 1,536 & 1,536 & 1,536 & 1,536 & 1,536\\ 384 & 384 & 384 & 384 & 385 & 384 & 384 & 384 & 384\\ 96 & 96 & 96 & 96 & 96 & 97 & 96 & 96 & 96\\ 24 & 24 & 24 & 24 & 24 & 24 & 25 & 24 & 24\\ 6 & 6 & 6 & 6 & 6 & 6 & 6 & 7 & 6 \end{pmatrix} \times \frac{1}{4^8} \\ \\ \mathbf{M}^{16} &= \begin{pmatrix} 2,147,483,648 & 2,147,483,648 & 2,147,483,648 & 2,147,483,648 & \dots\\ 858,993,459 & 858,993,460 & 858,993,459 & 858,993,459 & \dots\\ 751,717,587 & 751,717,586 & 751,717,587 & 751,717,587 & \dots\\ 402,677,762 & 402,677,761 & 402,677,761 & 402,677,761 & \dots\\ 100,669,440 & 100,669,441 & 100,669,441 & 100,669,440 & \dots\\ 25,167,360 & 25,167,360 & 25,167,360 & 25,167,361 & \dots\\ 6,291,840 & 6,291,840 & 6,291,840 & 6,291,840 & \dots\\ 1,572,960 & 1,572,960 & 1,572,960 & 1,572,960 & \dots\\ 393,240 & 393,240 & 393,240 & 393,240 & \dots \end{pmatrix} \times \frac{1}{4^{16}} \end{align*} \]
Since the probability of having two coins in the pile at the outset equals one, the initial probability vector must have a one for its first element and zero for the rest and so the product of a matrix and it is simply equal to the first column of that matrix, giving us a probability vector at the end of the game of
\[ \begin{pmatrix} p_2\\ p_3\\ p_5\\ p_7\\ p_{11}\\ p_{13}\\ p_{17}\\ p_{19}\\ p_{23} \end{pmatrix} = \mathbf{M}^{16} \times \begin{pmatrix} 1\\ 0\\ 0\\ 0\\ 0\\ 0\\ 0\\ 0\\ 0 \end{pmatrix} = \begin{pmatrix} 2,147,483,648\\ 858,993,459\\ 751,717,587\\ 402,677,762\\ 100,669,440\\ 25,167,360\\ 6,291,840\\ 1,572,960\\ 393,240 \end{pmatrix} \times \frac{1}{4^{16}} \]
Finally, Sir R-----'s expected prize was simply
\[ p_2 \times 2 + p_3 \times 3 + p_5 \times 5 + p_7 \times 7 + p_{11} \times 11 + p_{13} \times 13 + p_{17} \times 17 + p_{19} \times 19 + p_{23} \times 23 \]
which comes out to
\[ \frac{7,514,855,751}{2,147,483,648} = 3 + \frac{1,072,404,807}{2,147,483,648} \]
Now the cost of the wager was
\[ 3 + \frac{50}{100} = 3 + \frac{1,073,741,824}{2,147,483,648} \]
and so this represents a slight loss for Sir R----- and I should have advised him to decline it.
\(\Box\)

Leave a comment

 
This site requires HTML5, CSS 2.1 and JavaScript 5 and has been tested with

Chrome Chrome 26+
Firefox Firefox 20+
Internet Explorer Internet Explorer 9+