Homepage 24 Game Homepage Reijnhoudt.nl

Solutions to the 24 Game

1. Introduction

The 24 Game is a challenging math game, where given four one-digit numbers, the task is to form an expression using all four numbers once, any set of arithmetic operators (+, -, and ) and possibly brackets, to form an expression with outcome 24.
For example, with the numbers 8, 4, 3 and 1, you can form the following expressions with outcome 24: (1 + 3) 4 + 8, (1 + 8 - 3) 4 and (4 + 8) (3 - 1).
The original game from Suntex consists of 192 cards, from which 48 are said to be easy, 96 medium, and 48 tough.

In section 2 we derive equations for the number of combinations of four numbers and for the number of possible expressions for a given combination. In section 3 we calculate how many combinations there are for which it is possible to form an expressions with outcome 24, and we define a filter that outputs only expressions with a different solution approach. In section 4 we conclude with more research questions, and section 5 contains some interesting links to other pages.

2. Combinatorics

Let us first recall some basic enumerative combinatorics.

Theorem There are

( n+m-1 )
n
combinations of n elements chosen from a set of m elements, where elements may be repeated.

Proof There is a one-to-one relation between combinations of n elements chosen from the set 1, ..., m, and the series

a1 a2 a3 ... an+m-1

with n zeros and m - 1 ones.
Let P be the set of all indices p such that ap = 0. Then the represented combination is

Up in P (1 + sumi=1...pai)
blokje

Thus there are 495 different combinations of 4 (n) numbers from 1 to 9 (m).

Enumerating all possible expressions using the four numbers of a combination can be easily done using prefix or postfix notation. Standard expressions are expressed in infix notation, that is, binary arithmetic operations are placed between the two operands, for example (6 2) (9 - 1) and 2 9 1 + 6. In prefix notation (also called Polish notation) the arithmetic operation precedes both operands. So for the two examples above, the prefix notation is 6 2 - 9 1 and + 2 9 1 6. Evaluating such an expression is done right to left.

See Table 1 for an example of evaluating prefix expressions.

Table 1: Steps taken in solving two prefix expressions.
 62-91
=628
=38
=24
and
 +2916
=+1816
=+186
=24

The main disadvantage of infix notation is that in general brackets are needed to ensure the correct order of evaluation. In practice there is no need to enclose every subexpression in brackets, but the cost is an extra rule for evaluation (Please Excuse My Dear Aunt Sally: Parentheses, Exponents, Multiplication, Division, Addition, and Subtraction).
To make the link between the different expression notations (prefix, infix, and postfix) more clear, note that expressions can be represented as trees (Figure 2).

Tree representation of the expressions (6  2)  (9 - 1) and 2  9  1 + 6
Figure 2: Tree representation of the expressions (6  2)  (9 - 1) and 2  9  1 + 6.

Different notations (prefix and infix) of an expression can be derived from a tree by traversing it starting at the left side of the root node and walking along the tree, staying as close to it as possible. Then all leaves are passed one time, and are printed then, but all internal nodes are passed three times. First on the left, the second time on the bottom, and the third time on the right (see Figure 3).

Traversing a tree passes each internal node three times
Figure 3: Traversing a tree passes each internal node three times.

The prefix notation can be obtained by printing the operator only the first time it is passed (a root-left-right algorithm). There is also a postfix notation (also called the reverse Polish notation) which is obtained by printing the operator only the third time it is passed (a left-right-root algorithm), but we will not discuss it here any further. The infix notation can be obtained by printing an opening bracket when an operator is passed the first time, printing the operator only the second time, and printing a closing bracket when an operator is passed the third time (basically a left-root-right algorithm). So the expressions of Figure 2 are in prefix notation 6 2 - 9 1 and + 2 9 1 6, in infix notation (6 2) (9 - 1) and 2 9 1 + 6 and in postfix notation 6 2 9 1 - and 2 9 1 6 +.

Given a fixed amount of numbers, how many expressions can we make with it?
Theorem Given an ordered set of n numbers and an ordered set of n - 1 arithmetic operations. Then the number of different expressions such that in the prefix notation the numbers and the operations are in the right order respectively is

( 2 n - 2 )
T(n) = n - 1
n
which is the (n - 1)th Catalan number.

Proof The number of binary trees with one leaf is 1. For a tree with n > 0 leafs, take all the trees with n - 1 leafs, which each have 2 (n - 2) edges. Consider all the 4 (n - 2) trees obtained by inserting a node on one edge and attaching a new leaf to it, either to the left or to the right, and the 2 trees obtained by taking a new root node and attaching the tree to one side and a new leaf to the other side. Together it makes 4 n - 6 trees with n leafs, but each tree is duplicated n times, because, given a tree with n leaves, each leaf can be added last. So

T(1) = 1 and T(n) = 4 n - 6 T(n - 1) for n = 1, 2, ...
n
Then
T(n) =
4 n - 6T(n - 1)
n
=
(4 n - 6) (4 n - 10)T(n - 2)
n (n - 1)
= ...
=
(4 n - 6) (4 n - 10) ... 6 2
n!
=
2n - 1 (2 n - 3) (2 n - 5) ... 3 1
n!
=
2n - 1 (2 n - 2)!
n! (2 n - 2) (2 n - 4) ... 4 2
=
2n - 1 (2 n - 2)!
n! 2n - 1 (n - 1)!
=
(2 n - 2)!
n! (n - 1)!
=
( 2 n - 2 )
n - 1
n
blokje

Thus given a set of four numbers and a set of three arithmetic operations there are 5 different expressions.
So, the number of possible expressions with four numbers from one to nine, and three arithmetic operations is

( 2 n - 2 ) ( 6 )
9n 4n - 1 n - 1 = 94 43 3 = 2099520.
n 4

3. Calculations

To see how many combination can form 24, consider all possible expressions for all combinations. That is, for each combination, consider all the permutations of the numbers of that combination, consider all sets of n - 1 arithmetic operators and consider all possible insertion points for these operations, so that the result is a valid expression in prefix notation, and see what combination can form 24.
From these 2099520 expressions 14754 expressions give 24 as outcome, occurring at 404 different combinations. Table 4 lists all 0 combinations for which it is not possible to form 24.

Table 4: List of all combinations of 4 numbers from 1 to 9 for which it is impossible to form 24.
1111 1112 1113 1114 1115 1116 1117 1119 1122 1123 1124 1125 1133 1159 1167 1177 1178 1179 1189 1199 1222 1223 1299 1355 1499 1557 1558 1577 1667 1677 1678 1777 1778 1899 1999 2222 2226 2279 2299 2334 2555 2556 2599 2677 2777 2779 2799 2999 3358 3467 3488 3555 3577 4459 4466 4467 4499 4779 4999 5557 5558 5569 5579 5777 5778 5799 5899 5999 6667 6677 6678 6699 6777 6778 6779 6788 6999 7777 7778 7779 7788 7789 7799 7888 7899 7999 8888 8889 8899 8999 9999

Note that the only combinations that can not form 24 and have four different numbers are 1678 and 3467.

Given all the expressions made from one combination, it can be seen that many expressions have the same solution approach. For example, the expressions (1+3)4+8, (3+1)4+8 and 8+4(3+1) represent basically the same solution approach, namely adding 1 and 3, multiplying this outcome by 4 and adding 8.
We will describe a filter that accepts only one expression from each approach and rejects all the other expressions. The filter consists of three components.

  1. The first component only accepts trees that can be build using the language as defined in Table 5.

    Table 5: Definition of the language accepted by the first component of the described filter.
    tree=plusmintree | timesdivtree
    plusmintree=- plustree plustree | plustree
    plustree=leaf | timesdivtree | + timesdivtree plustree
    timesdivtree= timestree timestree | timestree
    timestree=leaf | plusmintree | plusmintree timestree
    leaf=1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

    In Table 6 all substructures containing two arithmetic operations are listed, and for each one it is indicated whether it is rejected or accepted. When it is rejected, its accepted counterpart is on the right.

    Table 6: List of all substructures with an indication whether they are rejected or accepted.
    rejectedaccepted
    +-abc, +a-cb, -a-bc -+acb
    --abc-a+bc
    ++abc+a+bc
    abc, acb, abcacb
    abcabc
    abcabc
    +abc, +abc, -abc, -abc, +abc, -abc, +abc, -abc,
    +abc, +abc, -abc, -abc, a+bc, a-bc, a+bc, a-bc

  2. The second component rejects expressions with certain substructures that are not non-ascending.
  3. The third component rejects expressions with certain substructures that contain null elements (0 for addition/subtraction and 1 for multiplication/division). The notation [a] means the value of substructure a.

After applying the filter only 993 expressions remain that have outcome 24 (see Appendix a: Table 7).

The Java archive for these calculations is in 24game.jar and the Java source code is in 24game.zip.
Run with the command "java -jar 24game.jar".

3. Further questions

4. Interesting links