Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

The 24 game is a game where the number $24$ is to be obtained from 4 single-digit numbers using the basic mathematical operations addition, subtraction, multiplication, division and parenthesis.

For example, the numbers $1, 2, 6, 9$ can be arranged as,

$$ (9 - 1) \times (6 \div 2) = 8 \times 3 = 24 $$

A friend suggested this game to me to help improve my number sense skills. I have played it a few times and but I sometimes find a particular combination of numbers more difficult.

I was wondering if given any particular combination of numbers is it always possible to form $24$? And if yes how many different ways can a particular group of numbers yield $24$? I am also curious about the math behind this game in general.

Thanks for your help.

P.S. I have tried wikipedia and searching the web. Wikipedia doesn't answer the question and most of the links on solving this game that I found were related to figuring out if an expression correctly yields $24$.

share|improve this question
    
It is not elegant, but there are only $10^4 4^3$ possible solutions. So, open Maple, or whatever, start a loop with an if statement in it (if function=24 then print), go to bed and see where it takes you in the morning... –  user1729 Aug 17 '11 at 11:05
1  
What about "1,1,1,1" with multiplication and addition it would not become big enough to yield 24 if I understood this correctly. –  Listing Aug 17 '11 at 11:34
    
$(1+1+1+1)!$ . OK, I cheated and used the factorial. –  Raskolnikov Aug 17 '11 at 11:41
    
I have clarified the question, I forgot to mention that parenthesis is allowed. –  mathguy80 Aug 17 '11 at 11:46

2 Answers 2

up vote 3 down vote accepted

Mathematics can supply a bit of analysis before brute force computation is required.

We can count the number of problems easily enough. If the digits are all distinct (and nonzero), then there will be $C(9,4)$ of those, so all distinct digit problems number 126. Note that this considers the order of the digits unimportant since you seem to all their rearrangment in your Question above.

It remains only to count the problems which involve a certain number of duplicate digits. For example the same digit can occur four times in just 9 problems of that type. One digit occurring three times with a different fourth digit accounts for 9*8 = 72 problems.

Otherwise some digit occurs twice (but no more than twice). If the problem has two "twin" digits, it can happen in 72/2 = 36 ways. If the problem has one duplicate pair and two other distinct digits, this happens in 9*8*7/2 = 252 ways.

Totaling these possibilities gives 126+9+72+36+252 = 495.

I see no shortcut to deciding apriori how many of these have an admissible way of expressing 24 (using just the four basic arithmetic operations and parentheses). Certainly a program could be written to explore all the possibilities. For this purpose we can dispense with any question of parentheses by using Polish notation (evaluating such by a stack order of operation to see if 24 is the result). Note that with rearrangements we are back to considering how many ways the four arithmetic operators can be inserted qua Polish notation among any four single digit operands.

We can identify five possible sequences of operators and digits that are allowable. In the strings below, each A represents a place for an arithmetic operator and each D represents a place for a digit.

AAADDDD
AADADDD
AADDADD
ADAADDD
ADADADD

That is, if three binary operators are used to combine single digit operands, then only these five patterns are feasible to get a single result. All five patterns admit $4^3 = 64$ substitutions for the operators and $9^4 = 6561$ substitutions for the digits. Therefore the total number of expressions to check is at most 2099520. I say "at most" because some pruning will naturally occur as a result of finding solutions for problems without checking all possible expressions for a given set of digits. Further some of the patterns are equivalent because of the commutativity of addition and multiplication, but it would likely take magnitudes more time to program for any reduction in search space on that basis than it would to just exhaust the five patterns above

share|improve this answer
    
Using polish notation is a very good way of dealing with the parenthesis. Thank you for an excellent answer. –  mathguy80 Aug 18 '11 at 4:14

If you take the numbers $(1,1,1,1)$ (I assume that double numbers are allowed like in this implementation) you will notice that

$$1+1+1+1<24$$ $$(1+1) \cdot (1+1) < 24$$ $$(1+1+1) \cdot 1 < 24$$

And all other combinations using the operators addition, subtraction, multiplication, division and parenthesis have to be smaller or equal the ones above (this should be clear, otherwise you could just try all other combinations).

When you force all numbers to be distinct it is a bit harder but you can see that for example the numbers $(3,4,6,7)$ have no solutions. You can investigate further if every set has a solutions if you add new operators like factorial, I will leave that to you as homework :-).

Edit: As you asked here you can find the source-code of a rather straight-forward brute-force approach to the problem.

share|improve this answer
    
Thanks. Your excellent link throws up further questions. The trivia page says there are $495$ solutions of which $404$ are solvable. Looking through the source code of the solver I found that there are fixed number of solutions that he is checking against, which confirms this. Any ideas how he came up with these numbers? –  mathguy80 Aug 17 '11 at 15:21
    
I guess he generated them via brute force. Similar to integer partitions ( en.wikipedia.org/wiki/Partition_%28number_theory%29 ) you can of course generate partitions which include more operators than "+", I don't think there is some good formula to do this :-) –  Listing Aug 17 '11 at 15:26
    
Interesting, thanks. Yeah I was sort of hoping there was. :) –  mathguy80 Aug 17 '11 at 15:44
    
Thanks for the solver source, looks great. –  mathguy80 Aug 18 '11 at 4:15

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.