Proof of solutions to “24” operations game

Consider a deck of cards with values $1$ through $13$, each with multiplicity $4$, so that $$S = \left( \bigcup_{i=1}^{13} \{ i \} \right) \times \{1,2,3,4\}$$

Supposedly, there exists a game in which four cards $(v,m)$ in $S$ are selected (here $m$ stands in for the suit), and participants try to devise a series of operations using:

• addition $+$;
• subtraction $-$;
• multiplication $\times$;
• division $\div$;
• exponentiation $\wedge$;
• factorial-ization $!$; and
• any number of parentheses $()$

on the $v$-values that yields $24$. For example,

$$(2, 1) \times (10,3) - (2,4) + (3,2)! = 24$$

• Do there exist any combinations of cards for which no series of operations yielding $24$ exists?
• What mathematical processes could one use to analyze other aspects of solutions, such as how many solutions exist?

This is a post-examination game we are playing in class to kill time. I haven’t the slightest idea of how one would approach any sort of ‘proof.’

• So, does the suit 1-4 have anything to do with anything? Might be easier to just say "ignore the suit". May 18, 2018 at 5:17
• @fleablood The suit doesn’t have anything to do with it. However, I didn’t know how to approach the problem, so I started with rigorous notation. In hindsight, looking at Dark Malthorp’s answer, it’s clear that it doesn’t matter. May 18, 2018 at 11:32
• It doesn't but $(2,1)\times(10,3)$ would be clearer to read if it were just $2\times 10$. Second question may/must these distribute. If I had 2, 3, 4 and I chose to do 2 + 3 ^ 4 does that mean $(2 + 3)^4$ or $2 + 3^4$ or can I choose which one to mean. May 18, 2018 at 16:38
• @fleablood There’s no need to change it now; second: “any number of parentheses $()$” May 18, 2018 at 23:22

EDIT: there was a bug in my code so it missed some solutions. There are actually only 48 unsolvable hands, not 56.

EDIT 2: due to rounding errors, my code thought [9,7,5,5] was solvable, when in fact it is not (see update below).

I have played that game too, so when I saw your question I was pretty sure there are some hands that have no series reaching 24. Since there's only $$\binom{52}{4} = 270,725$$ possible hands of 4 cards (even less since this game doesn't count suits), I figured it would be feasible to do a computer search to find all of these solutions (see the bottom for my code).

My program found solutions for all but 48 hands (ignoring different suits):

[1,1,7,7] [1,1,9,9] [1,1,10,10] [1,1,10,11] [1,7,7,13] [1,9,9,9] [1,9,10,10] [1,10,10,10] [1,10,10,11] [1,10,11,11] [1,11,11,11] [1,13,13,13] [6,6,6,13] [6,6,7,7] [6,6,7,13] [6,6,13,13] [6,7,7,13] [6,7,13,13] [6,8,8,13] [6,11,11,13] [7,7,7,7] [7,7,7,13] [7,7,10,10] [7,7,10,12] [7,7,11,11] [7,7,13,13] [7,8,9,9] [7,10,10,13] [7,11,11,13] [7,13,13,13] [8,8,9,9] [8,8,11,11] [8,9,9,10] [8,9,13,13] [9,9,9,9] [9,9,9,11] [9,9,10,10] [9,9,13,13] [9,10,10,10] [9,10,10,11] [9,10,11,11], [10,10,10,10] [10,10,10,11] [10,10,11,11] [10,10,13,13] [10,11,11,11] [11,11,11,11] [13,13,13,13]

Counting suits, this works out to be 2413 possibilities out of the 270,725 total hands, or a probability of just a tad below 0.9%.

Since my program did not use factorials of any numbers larger than 13, so it is possible that some of these 48 actually do have solutions, but I don't find that very likely. Among these combinations all have repeated cards. None of the combinations have a 2, 3, 4, or 5, and only one has a 12. Surprisingly, the most common number in the unsolvable hands is 10 (accounting for suits, it shows up in 1109 out of the 2413 unsolvable hands). As someone who has played this game a lot, I was expecting 11 or 13 to be the most likely to give an unsolvable hand, but they only showed up in 845 and 1073 unsolvable hands, respectively.

As for the number of ways to get to 24 from a given hand, my program didn't really look at that because I was trying not to make the program take up to much computational power, and it was much easier to simply remember a single boolean than a whole chain.

Rounding errors update:

[9,7,5,5] is not a solution, but my code thinks it is due to rounding errors. For example, it couldn't distinguish $$9^{5-7!}$$ from $$0$$, and found this "solution":$$\left(5 - \left(9^{5-7!}\right)!\right)! \approx 24$$ If you use the gamma function to interpolate the factorials, this is off by only about$$5\times 10^{-4804}$$.

Removing exponentiation from the options, other than using $$1^a = 1$$, shows that this is the only solution that took advantage of this particular numerical error. Since I didn't ever take a factorial of a number bigger than 13, the factorials should not have introduced any other fake solutions.

Some interesting example hands: Among the hands that have solutions, I've chosen to highlight a few particularly interesting ones:

[13,11,10,6], [13,6,1,1], [13,12,10,8], [11,11,5,5], [11,11,5,1], [9,7,7,7], and [5,1,1,1]

If you want to challenge yourself, see if you can solve these before looking at the solutions.

[13,11,10,6]

This is the only hand that requires a factorial of a number bigger than 10: $$24 = \left(\frac{13 + \frac{11!}{10!}}{6}\right)!$$

[13,6,1,1]

This and [9,8,1,1] are the only ones that require use of exponentiation: $$\begin{eqnarray} 24&=&\left(\frac8{1+1^9}\right)!\\24&=&\left(6 - 1^{13} - 1\right)! \end{eqnarray}$$

[9,7,7,7]

This hand has only one possible solution, and is an interesting example of one which requires factorials but doesn't use $$4!=24$$. $$24 = \frac{9!}{7!+7!+7!}$$

If you disallow factorials, there are fully 430 unsolvable hands (not counting suits). Some of my favorite solutions without factorials include [11,11,1,5], [13,12,10,8], [11,11,5,5] and [5,1,1,1], which have the following unique non-factorial solutions:

[13,12,10,8]

$$24=\frac{10\cdot 12}{13-8}$$

[11,11,5,5]

$$24=5\cdot5-\frac{11}{11}$$

[11,11,5,1]

$$24=\frac{11\cdot 11 - 1}{5}$$

[5,1,1,1]

$$5^{1+1} - 1$$

Below is my Haskell program. Programming is not my strong point, so excuse the messiness.

unsolvable = p 4
-- all hands that have no way to reach 24.

-- derivation:

-- returns True if an input four card hand is solvable.
check :: (Num a, Fractional a, Eq a, Ord a, Floating a, Enum a) => [a] -> Bool
check [a,b,c,d] = firstCheck a b c d
check _ = False

--check as a four-argument function
firstCheck :: (Num a, Fractional a, Eq a, Ord a, Floating a, Enum a) => a -> a -> a -> a -> Bool
firstCheck a b c d = or [fCheck a b c d, fCheck b c d a, fCheck c d a b, fCheck d a b c, fCheck d b a c, fCheck a c b d]

fCheck :: (Num a, Fractional a, Eq a, Ord a, Floating a, Enum a) => a -> a -> a -> a -> Bool
fCheck a b c d = or $$map (secondCheck a b)$$ op c d

{--finalCheck :: (Num a, Fractional a, Eq a, Ord a, Floating a, Enum a) => a -> a -> Bool
finalCheck a b = (24 elem s)
where s = op a b --}

--check if 3 numbers can make 24
sCheck :: (Num a, Fractional a, Eq a, Ord a, Floating a, Enum a) => a -> a -> a -> Bool
sCheck a b c = or $$map (finalCheck a)$$ op b c

secondCheck :: (Num a, Fractional a, Eq a, Ord a, Floating a, Enum a) => a -> a -> a -> Bool
secondCheck a b c = (sCheck a b c) || (sCheck b a c) || (sCheck c a b)

-- checks if 2 numbers can combine to 24 or 4! = 24
finalCheck :: (Num a, Fractional a, Eq a, Ord a, Floating a, Enum a) => a -> a -> Bool
finalCheck a b = (24 elem s) || (4 elem s)
where s = op a b

--all operations except factorial, with the assumption that a a -> a -> [a]
opp 0 b = [0,1,b,-b, 1+b, b-1, 1-b]
opp 1 b = [1+b,b,1/b,1-b,b-1,1]
opp a b = [a+b,a*b,a/b,a-b,b-a,b/a,a**b,b**a]

-- op includes operations from opp as well as manually including factorials up to 13!
op ::  (Num a, Fractional a, Eq a, Ord a, Floating a, Enum a) => a -> a -> [a]
op 3 b = opp (min 3 b) (max 3 b) ++ op b 6 ++ op 6 b
op 4 b = opp (min 4 b) (max 4 b) ++ op b 24
op 5 b = opp (min 5 b) (max 5 b) ++ op b 120
op 6 b = opp (min 6 b) (max 6 b) ++ op b 720
op 7 b = opp (min 7 b) (max 7 b) ++ op b 5040
op 8 b = opp (min 8 b) (max 8 b) ++ op b 40320
op 9 b = opp (min 9 b) (max 9 b) ++ op b 362880
op 10 b = opp (min 10 b) (max 10 b) ++ op b 3628800
op 11 b = opp (min 11 b) (max 11 b) ++ op b 39916800
op 12 b = opp (min 12 b) (max 12 b) ++ op b 479001600
op 13 b = opp (min 13 b) (max 13 b) ++ op b 6227020800
op a b = opp (min a b) (max a b)

lcheck :: (Num a, Fractional a, Eq a, Ord a, Floating a, Enum a,Enum a) => [a] -> [Bool]
lcheck [a,b,c,d] = [check [a,b,c,d]]
lcheck s = map (and . lcheck . (\n -> n:s)) [(head s)..13]
-- s must be in order from largest to smallest.
-- (lcheck s !! i) is True whenever there is a solvable hand sorted
-- from largest to smallest that ends with (head s + i):s

ccheck :: (Num a, Fractional a, Eq a, Ord a, Floating a, Enum a,Enum a) => [a] -> Bool
ccheck = and . lcheck
-- returns True if a sorted hand ending with s is solvable

p1 = filter (not . (\k -> (ccheck [k])) . fromIntegral) [1..13]
-- possible smallest cards for an unsolvable hand

pf :: (Integral a) => [a] -> [[a]]
pf x = map (\s -> s:x) $$filter (not . (\k -> (ccheck$$ map fromIntegral (k:x))) . fromIntegral) [(head x)..13]
-- if x is n cards, pf x lists possibilities of length n+1 endings for sorted hands that end in x

p :: Int -> [[Integer]]
p 1 = map (\x -> [x]) p1
p n = foldr (++) [] $$map pf$$ p (n-1)
-- lists possible last n cards of a sorted unsolvable hand.

• When I first started reading your answer, I was expecting it to have come from someone with several thousand rep. Very nice! This has hit on all of the points and has gone above and beyond— $\color{blue}{\uparrow}\color{green}{\checkmark}$ $\ddot\smile$ May 18, 2018 at 4:34
• @Chase Ryan Taylor Thanks! Glad to be of service. My program had an error that I just fixed, so actually there are fewer unsolvable hands than I originally claimed. May 18, 2018 at 4:50
• I'm wondering if your code snippet is missing some lines. You reference sCheck but never define it, define finalCheck but never use it, and have no main, for instance. Jun 2, 2018 at 21:28
• Good catch, I did forget the first few lines. They should be there now. There is no main (I never really learned I/O in Haskell and I've never actually needed it). Jun 3, 2018 at 21:47

Dark Malthorp showed that there are combinations of cards that cannot yield 24 from those operations you specified. I'll try to answer your other question about what strategy could someone use. Given the number/types of allowed operations, I think this strategy is unfeasible but it's only to showcase what we can do if the game was less complex (no ^, smaller numbers, etc.). EDIT: See comments on why $!$ cannot be removed.

Every formula built from $v_1,v_2,v_3,$ and $v_4$, using the operations $+,-,\cdot,/,$^$,$ and $!$, is of the following five forms:

1. $(((v_1!_n*v_2!_n)!_n*v_3!_n)!_n*v_4!_n)!_n$
2. $((v_1!_n*(v_2!_n*v_3!_n)!_n)!_n*v_4!_n)!_n$
3. $(v_1!_n*((v_2!_n*v_3!_n)!_n*v_4!_n)!_n)!_n$
4. $(v_1!_n*(v_2!_n*(v_3!_n*v_4!_n)!_n)!_n)!_n$
5. $((v_1!_n*v_2!_n)!_n*(v_3!_n*v_4!_n)!_n)!_n$

where $*$ is a binary operation $+,-,\cdot,/,$ or ^, and $!_n$ is an $n$ number of factorials $!$. It looks really ugly since a $!_n$ may appear after every $v_n$ and parenthesis.

I had a feeling that $v_1=v_2=v_3=v_4=13$ would work. Informally, making all the numbers the same "limits" what the operations can do in a sense, and Dark confirmed that 13,13,13,13 is one of the combinations that cannot yield 24.
So let's try proof by contradiction. This is in no way a proof since I haven't actually checked every case.

Suppose $v_1=v_2=v_3=v_4=13$, and that every form yields 24. Then in every form, $n$ in the outermost $!_n$ is zero.* (* means not fully justified without a lot of case checking). First, we have that $m!=24$ iff $m=4$. Suppose $n=2$, then the same formula with outermost $!_{n-1}$ in place of $!_n$ must yield $4$ (since then $4!=24$). In this case we require $\phi!_1$=4, where $\phi$ stands for the formula without the outermost $!_{n-1}=!_1$. But there is no number $m$ s.t. $m!=4$, contradiction, so $n\neq2$. We repeat this argument for $n>2$. Okay now is the part where we use $v_1=v_2=v_3=v_4=13$, and where I don't check the cases. Suppose $n=1$, then we require $\phi!_0=\phi=4$, which I do not believe is possible, so $n=0$.* (To actually check this would require a lot of computing). Then $\ldots$

As you can see, this devolves into A LOT of case checking. We'd have to eventually check the $!_n$'s in $\phi$ and subsequent subformulas are $!_0$.* I believe this as informally, getting $13!$ back to a lower number requires division by at least $13!$, taking up an operation slot. Maybe this is untrue of smaller numbers; this is another reason I chose 13,13,13,13 and not some other quadruple of same numbers, along with the fact that it doesn't seem you can get factors of 24 easily from 13.

Anyways by fixing ALL the $!_n$'s with a finite number of $n$'s, and noting there are only a finite number of combinations of binary operations, you'd have a finite number of cases to check.

I hope this helps in your future problems.

• Up-voting for the suggestion of proof by contradiction and your outline of the five forms. I’m not sure if you were trying to say this, but it definitely makes sense to start with a much smaller subset of cards and then extend those conclusions. May 19, 2018 at 2:41
• I'm not sure what you mean by starting out with a smaller subset of cards. I've also realized that we can't easily consider a version of the game with $!$ removed, even though $!$ is clearly the most difficult obstacle to finding a counterexample. In fact, considering the game with $!$ removed, I believe for 1,1,1,1 to yield 24, the operations must be in these forms: $(1+1+1+1)!$ (parenthesis omitted) or $((1+1)\cdot(1+1))!$ or $((1+1)^{(1+1)})!$. So without $!$, 1,1,1,1 seems like a clear counterexample.
– user524154
May 19, 2018 at 4:54
• Noting this, on the other hand if we don't change any operations, we can't change 24 into any number that 1,1,1,1 can't express, else we take the same counterexample. If you have any approaches to the original problem or some variant let me know, I'm interested in finding a proof that doesn't involve too much computation.
– user524154
May 19, 2018 at 4:58
• I would like to chime in, I can confirm that $(1,1,1,1)$ does require factorials to solve. As you point out, in any combination, the final $!_n$ must have $n=0$ or $n=1$. This would simplify it to your 5 cases with out a factorial at the end, and trying to make either $4$ or $24$ at the end. May 19, 2018 at 15:51
• That means you'll end with $a * b = 24$ or $a * b = 4$, where $* = +, -, \times, /,$ or ^, which you can limit to only a relatively small number of possibilities for $a$ and $b$. But even here there are quite a few cases to check, mostly because of division. For example, with the hand $(7,7,7,9)$, there is only one possible solution, $9! / (7! + 7! + 7!) = 24$, which ends with $a = 362880$ and $b = 15120$, demonstrating that the $a$ and $b$ to check can be quite large. May 19, 2018 at 15:51