Title: On Share and Share Alike

Author: Bob Schmidt

Date: 09 November 2017 17:01:27 +00:00 or Thu, 09 November 2017 17:01:27 +00:00

Summary: A Student gets to grips with the Baron’s coin puzzle.

Body: 

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

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

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	2	2	2	2	2	2	2	2	2	2
	3	1		1	1	1	1	1	1	1
	5	1	1							1
	7		1	1
	11				1
	13					1
	17						1
	19							1
	23								1

create a matrix of its elements, and multiply it by one quarter

then the result 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 with

where is the probability that the pile contains coins at the start of a turn, then 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

where 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 , then at the end of that turn they must be

and so if they were instead at the start of a turn, they will be 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 at the start of the game, then they should be 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

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

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

Finally, Sir R-----’s expected prize was simply

which comes out to

Now the cost of the wager was

and so this represents a slight loss for Sir R----- and I should have advised him to decline it.

Acknowledgement

Courtesy of www.thusspakeak.com

Notes: 

More fields may be available via dynamicdata ..