On An Arithmetical Pursuit

| 0 Comments

Arithmetical Pursuit

Whilst taking our afternoon tea, my fellow students and I occasionally pass the time with some arithmetical pursuit, being a game in which the goal is to be the swiftest to manipulate six randomly chosen integers with addition, subtraction, multiplication and division to hit a randomly chosen target, or at least to land as closely as possible to it, admitting no more than one appearance of each number and no fractions.
The integers that we manipulate are supplied by the first six cards of a well shuffled deck, with the pip cards representing their face values, the Jacks representing twenty five, the Queens fifty and the Kings one hundred and the target is given by the roll of three twenty sided dice having the digits zero to nine twice each and where three zeros represents one thousand.

By way of an example, given the cards


and the dice


we might proceed with
\[ 6 \times (K + 10) - 8 = 6 \times (100 + 10) - 8 = 660 - 8 = 652 \]

Some Properties Of The Game

Naturally, one of the first things my fellow students and I set about upon learning of this game was to try to fathom its mathematical properties.

A trivial one is that every target can be hit with the right set of cards. This follows from the fact that if we have a King and a ten we can with them hit one thousand and that there are sufficient cards remaining to specify the hundreds, the tens and the units of other numbers with
\[ abc = a \times K + b \times 10 + c \]
where we simply leave out any terms that should be zero.

A rather more difficult property to figure is the total number of arithmetical expressions that might arise in the game. The problem is made significantly more difficult by the fact that the result of an expression may be affected by the presence of parentheses.
\[ \begin{align*} 2 + 3 \times 10 &= 2 + (3 \times 10) = 32\\ (2+3) \times 10 &= 50 \end{align*} \]
Fortunately, there is an alternative convention for arithmetical expression that does not require parentheses to determine the order of application of the operators; reverse Polish Notation.

Reverse Polish Notation

In reverse Polish notation, or RPN, the operator appears after its arguments rather than between them. Perhaps a little surprisingly, this small change means that there is no need to define the precedence of operators in the absence of parentheses, such as multiplications being resolved before additions. For example, the first of the above expressions is written in RPN as
\[ 3 \; 10 \; \times \; 2 \; + \]
which we read as take three and ten and multiply them, then take the result and two and add them and the second takes the form
\[ 2 \; 3 \; + \; 10 \; \times \]
which reads take two and three and add them, then take the result and ten and multiply them. Note that it is still possible to distinguish between the first and second arguments of an additive or multiplicative expression even though exchanging them has no effect upon their results. For example, we can swap the order of the arguments of the addition in the first expression with
\[ 2 \; 3 \; 10 \; \times \; + \]
which now reads take two and the result of taking three and ten and multiplying them and add them. Now there is a simple rule by which we can unambiguously determine how to read these RPN expressions

Reading from left to right, whenever you come across an arithmetical operator apply it to the two numbers that precede it, then scrub out both them and the operator and write in their place the result and begin again, until there is but a single number left.

For example, using parentheses to identify the operator and numbers that we shall scrub out and replace with their result
\[ 2 \; 3 \; 10 \; \times \; + \\ 2 \; (3 \; 10 \; \times) \; + \\ (2 \; 30 \; +)\\ 32 \]
Now, an extremely convenient consequence of this rule is that, when it comes to enumerating RPN expressions involving addition, subtraction, multiplication and division, they can only represent calculable arithmetical expressions if the count of operators is one greater than the count of numbers and furthermore that at no point when reading from left to right the former equals or exceeds the latter, for if it did we should exhaust the numbers upon which the operators should operate!

Counting The Formulae

If we use \(x\) as a place-holder for the numbers and \(o\) as a place-holder for the arithmetical operators we can divide the set of RPN formulae into subsets of varying general structure. For example, the formula
\[ 3 \; 10 \; \times \; 2 \; + \]
belongs to the subset \(xxoxo\).

The first step in counting the number of formulae is therefore to count the number of ways we can arrange \(n\) \(x\) symbols and \(n-1\) \(o\) symbols. The easiest way to figure this is to imagine that we have a line of \(2n-1\) \(x\) symbols and we then choose to swap \(n-1\) of them, one at a time, with \(o\) symbols. At the first step we have \(2n-1\) \(x\) symbols to choose from, at the second \(2n-2\), at the third \(2n-3\) and so on and so forth until at the last there are just \(n+1\) left. The number of ways we can do this is consequently the product
\[ (n+1) \times (n+2) \times \dots \times (2n-3) \times (2n-1) \times (2n-1) = \frac{(2n-1)!}{n!} \]
where the exclamation mark stands for the factorial, the product of every number from one up to the value that precedes it.
Now the order in which we choose which of the \(x\) symbols to swap doesn't make any difference to the result, so we must divide this result by the number of ways we can label the \(o\) symbols with the digits one to \(n-1\) which, since we progressively exhaust the unlabelled ones, is simply the product of the numbers from \(n\) down to one, \((n-1)!\), yielding the combination
\[ ^{2n-1}C_{n-1} = \frac{(2n-1)!}{(n-1)! \times n!} \]
The next step is to figure out how many of these are valid RPN formulae subsets. If we pose the question as what is the probability that, as we traverse from left to right, the count of \(x\) symbols is always greater than that of \(o\) symbols then we can answer it with the ballot theorem[1] which, in its simplest form, states

Suppose that, in a ballot, candidate P scores \(p\) votes and candidate Q scores \(q\) votes, where \(p > 0\) and \(p \geqslant q\). The probability that throughout the counting there are always more votes for P than for Q equals \((p-q)/(p+q)\).

There are several means of proving this[2] but the tidiest is by induction; first we show that if it is true for \(n-1\) votes then it must also be true for \(n\) and then we show that it is true for a single vote. Before we start, however, we must demonstrate that it holds true for the special case of \(p\) equal to \(q\) when candidate P cannot be ahead when the final vote is cast. The theorem correctly states that probability in this eventuality is given by
\[ \frac{p-p}{p+p} = \frac{0}{2p} = 0 \]
To commence the induction we first note that that the probability that the final vote cast is for P is given by
\[ \frac{p}{p+q} \]
and that it is for Q by
\[ \frac{q}{p+q} \]
In the first case, in all but the last vote P must have received \(p-1\) votes and Q must have had \(q\) and so the probability that P was ahead throughout the previous votes is
\[ \frac{(p-1)-q}{(p-1)+q} \]
Similarly, in the second case P must have had \(p\) votes and Q must have had \(q-1\) and so the probability of \(P\) having always been ahead before is
\[ \frac{p-(q-1)}{p+(q-1)} \]
Since the cases of the last vote going to P and Q are independent, the probability that P was ahead for the entire race is consequently
\[ \begin{align*} \frac{p}{p+q} \times \frac{p-q-1}{p+q-1} + \frac{q}{p+q} \times \frac{p-q+1}{p+q-1} &= \frac{p \times (p-q-1) + q \times (p-q+1)}{(p+q) \times (p+q-1)}\\ &= \frac{p \times (p-q) - p + q \times (p-q) + q}{(p+q) \times (p+q-1)}\\ &= \frac{(p+q) \times (p-q) - (p-q)}{(p+q) \times (p+q-1)}\\ &= \frac{(p+q-1) \times (p-q)}{(p+q) \times (p+q-1)}\\ &= \frac{p-q}{p+q} \end{align*} \]
as predicted.

Finally, if there is but one vote cast then since \(p\) cannot be smaller than \(q\) it must be the case that \(p\) equals one and \(q\) equals zero and the theorem correctly predicts a probability of
\[ \frac{1-0}{1+0} = 1 \]
that P was ahead of Q after the one and only vote.

The fraction of our sequences of \(x\) and \(o\) symbols that represent valid subsets of RPN formulae is therefore
\[ \frac{n-(n-1)}{n+(n-1)} = \frac{1}{2n-1} \]

and so those subsets must number
\[ \frac{^{2n-1}C_{n-1}}{2n-1} = \frac{(2n-1)!}{(2n-1) \times (n-1)! \times n!} \]
To figure the total number of formulae with \(n\) numbers, we need only find the number of ways in which we can substitute the \(x\) symbols with numbers and the \(o\) symbols with arithmetical operators. For the former, note that for the first \(x\) there are fifty two cards to choose from, for the second fifty one and so on and so forth. Unlike the problem of choosing which \(x\) symbols to swap for \(o\) symbols, the order of the cards is important and so this number is given by the permutation
\[ ^{52}P_n = \frac{52!}{(52-n)!} \]
For the latter, note that each \(o\) can be replaced with any of the four arithmetical operators that the game allows, so the number of ways of choosing them is simply \(4^{n-1}\) and the total number of formulae is consequently
\[ \frac{(2n-1)!}{(2n-1) \times (n-1)! \times n!} \times \frac{52!}{(52-n)!} \times 4^{n-1} = \frac{(2n-1)! \times 52! \times 4^{n-1}}{(2n-1) \times (n-1)! \times n! \times (52-n)!} \]
Deck 1 calculates the results of this formula for \(n\) equal from one to six together with their sum, being the total number of formulae using from one to six cards.

Deck 1: The Number Of Formulae

Note that here we are exploiting the fact that
\[ ^nP_n = \frac{n!}{(n-n)!} = \frac{n!}{0!} = \frac{n!}{1} = n! \]
so that we can use p to calculate both permutations and factorials.

Ruling Out The Fractions

Unfortunately these figures include formulae that involve fractions, which are most emphatically not permitted in the game. My fellow students and I could not fathom how to figure how many of them do through reasoning alone and, given just how many the formulae number, testing each and every one of them would be a rather daunting prospect. We can certainly rule out those that don't involve division since that is the only means of producing fractions. To do so, we simply replace \(4^{n-1}\) with \(4^{n-1}-3^{n-1}\) in our formula to remove those that only use addition, subtraction and multiplication
\[ \frac{(2n-1)! \times 52! \times \left(4^{n-1}-3^{n-1}\right)}{(2n-1) \times (n-1)! \times n! \times (52-n)!} \]
However, this does precious little to improve the situation, as demonstrated by deck 2.

Deck 2: The Number Of Formulae With Division

We should certainly expect most divisions to result in fractions and consequently expect the allowed formulae to number not so very many more than the \(149,955,465,707,008\) that do not involve division, a figure that you can verify by setting ops to three in deck 1.
Still, it would be preferable to have at least a rough idea of how many more they might number and my fellow students and I are determined to return to the problem when time permits.
\(\Box\)

References

[1] Feller, W., An Introduction to Probability Theory and its Applications vol. 1 (3rd ed.), Wiley, 2007.

[2] Renault, M., Four Proofs of the Ballot Theorem, Mathematics Magazine, vol. 80, pp. 345-352, 2007.

Based upon an article I wrote for ACCU's Overload magazine.

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+