Solutions to the 24 Game
1. Introduction
The 24 Game is a challenging math game,
where given four onedigit 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
combinations of n elements chosen from a set of m elements,
where elements may be repeated.
Proof
There is a onetoone relation between
combinations of n elements chosen from the set 1, ..., m,
and the series
a_{1} a_{2} a_{3} ... a_{n+m1}
with n zeros and m  1 ones.
Let P be the set of all indices p
such that a_{p} = 0.
Then the represented combination is
U_{p in P} (1 + sum_{i=1...p}a_{i})
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.

Start with the last arithmetic operation and the two operands that follow that operation.

Evaluate that subexpression and replace the arithmetic operation and the two operands by the result.

Follow these steps until there is no arithmetic operation left but only one operand, which is the answer.
See Table 1 for an example of evaluating prefix expressions.
Table 1:
Steps taken in solving two prefix expressions.

and 
 +  ×  ×  2  9  1  6 
=  +  ×  18  1  6 
=  +  18  6 
=  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).
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).
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 rootleftright 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 leftrightroot 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 leftrootright 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  6  T(n  1) 

n 

= 
(4 × n  6) × (4 × n  10)  T(n  2) 

n × (n  1) 

= 
... 
= 
(4 × n  6) × (4 × n  10) × ... × 6 × 2 

n! 

= 
2^{n  1} × (2 × n  3) × (2 × n  5) × ... × 3 × 1 

n! 

= 
2^{n  1} × (2 × n  2)! 

n! × (2 × n  2) × (2 × n  4) × ... × 4 × 2 

= 
2^{n  1} × (2 × n  2)! 

n! × 2^{n  1} × (n  1)! 

= 
(2 × n  2)! 

n! × (n  1)! 

= 
( 
2 × n  2 
) 
n  1 

n 

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 
) 
9^{n} × 4^{n  1} × 
n  1 
= 9^{4} × 4^{3} × 
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.

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.
rejected  accepted 
+abc, +acb, abc  +acb 
abc  a+bc 
++abc  +a+bc 
×÷abc, ×a÷cb, ÷a÷bc  ÷×acb 
÷÷abc  ÷a×bc 
××abc  ×a×bc 

+×abc, +÷abc, ×abc, ÷abc, ×+abc, ×abc, ÷+abc, ÷abc,
+a×bc, +a÷bc, a×bc, a÷bc, ×a+bc, ×abc, ÷a+bc, ÷abc



The second component rejects expressions with certain substructures that are not nonascending.

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.

Substructures ×ab and ×ba with [b]=1 are rejected,
when there is a non multiplication node in the path between this substructure
and the root node.

Substructures ÷ab with [b]=1 are rejected, because there exists
a tree c which is the complete tree without the ÷b branch and
with a ×b branch inserted at its root that is accepted.

Substructures ab are rejected, where
a = +a_{1}+a_{2}+...+a_{k1}a_{k} and
b = +b_{1}+b_{2}+...+b_{k1}b_{k},
when there exist sets P and Q such that
a' = 
sum 
a_{p} > 0, b' = 
sum 
b_{q} > 0, and a'  b' = 0 
_{p in P} 
_{q in Q} 
because there exists
a tree c which is the complete tree without the branches
a_{p} for p in P and b_{q} for q in Q
with branch ×÷a'b' inserted that is accepted.

Substructures ab are rejected, where [ab] < 0,
because there exists an other tree which can be obtained
by (possibly) changing the order of numbers
and by (possibly) changing pluses into minuses and vice versa,
that uses the same approach,
but where all the intermediate outcomes are nonnegative.
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

In the original game there is
an indication of the difficulty of the combination:
(easy),
(medium), and
(tough).
Is there a way of telling how hard a combination is?

Why did they choose 24 as target outcome?

What if you take another number of numbers?
What if you allow a larger range of number or allow fractions
(these two variants are also available commercially)?
4. Interesting links

Suntex, the manufacturer.

Computer programs that solve combinations:

Computer programs that present it as a game: