1
$\begingroup$

A colleague of mine in work told me of a game where each player is given $4$ cards, each card being a number from $1-9$, and is asked to generate an expression evaluating to the number $24$ using only these $4$ cards exactly once and the 4 operations $\{+, -, \times, \div\}$. My first thought- is this always possible? I don't think so. Consider the case where the cards are $(1, 1, 1, 1)$. Seems like the biggest number we can generate is $4 = 1 + 1 + 1 + 1$. Using multiplication doesn't seem like it would help here. Shouldn't take too long to brute force all the possible abstract syntax trees with all $1$s at the leaves and check that.

Question

There are tonnes of questions that can be asked from here, but let's stick to just one. What is the minimum number $n$, such that playing the above game, with $n$ cards instead of $4$, each card numbered $1-9$, we can always make the number $24$, no matter what the values of the cards are. Note we know from the below Lemma that such an $n$ exists.

Lemma: Existence of $n$

Here we prove the existence of such a minimum $n$ and show that $n \leq 55$. Proof: Suppose we have at least $55$ cards. Since each of the cards is numbered $1-9$, we can throw the cards into $9$ buckets, based on their number. Now, let's look at all the buckets with an odd number of cards in them. There can be at most $9$ such buckets. Remove exactly one card from each bucket, and take them aside. If there are no odd buckets, we take aside two cards from any non-empty even bucket. Note: the buckets now all contain an even number of cards. We'll use this later.

With the cards we removed in the last step, we can always make a number between $1$ and $9$. First, note that by our selection process we will always have at least one card. Now, simply divide the removed cards into two piles, such that the sum of the cards in the piles are as close as possible. First, we show that the difference between the two piles is between $0$ and $9$. Well, if it isn't, then one pile is bigger than the other by more than $9$, in which case we can swap any card from the bigger pile to the smaller one and decrease the difference, contradicting our assumption that we'd divided the piles as evenly as possible. Now we can show that it's possible to use our piles to create a number between $1-9$. Well, if the difference between the piles is $0$, then divide one pile by the other, else subtract the smaller from the larger. In either case, we end up with a number between $1$ and $9$. Let's call this number $k$.

We still need to make $24$, and we still need to use the cards left in the buckets. To do this, we're going to make the number $24 - k$ and then add it to $k$ which we made earlier on. To do this, we simply pair up all the cards in each bucket and divide them to get $1$. For example, we might have $6$ $2$s, so pairing we get $2 \div 2, 2 \div 2, 2 \div 2$, which evaluates to $1, 1, 1$.

Now, we know that there are an even number of cards left in each bucket, so we know that all cards will be paired up and we will have at least $23$ $1s$ formed because there are at least $46 = 55 - 9$ cards remaining after we remove the odd cards in the previous step. Now we simply take $24 - k \leq 23$ of these ones and add them up to get the number $24 - k$. Add this to $k$ and we get $24$. With the remaining $1$s we simply multiply them.

Note: This Lemma mostly only uses addition and subtraction, so I imagine it can be seriously improved.

Notes

  • It is allowed to have fractional values at nodes in the abstract syntax tree, but my intuition tells me we could always re-shuffle things so that we never get fractional values, given that the whole thing evaluates to an integer
  • We can't allow a value of $0$ for cards, otherwise the trivial case of all $0$s would mean no such $n$ exists
  • Card numbers are not necessarily unique. E.g. in the example above we have $4$ occurrences of the number $1$. The mathematical object describing the cards is a bag- a set with multiplicity

Example

Dealt the four cards $\{2, 4, 7, 8\}$ we can make $24$ with:

$$\dfrac{(7 \times 8)}{2} - 4$$

Possible Variations

  • Ask the question in reverse. Let's say we're playing the game with $n$ cards. Ask what is the largest $m$ such that all numbers from $1 - m$ are constructable, regardless of the values of the $n$ cards. Does $m$ grow with $n$?
  • Is the number $0$ always constructable, for sufficiently large $n$?
  • Let's say we have a bag $B$ of $n$ cards. Let $f(B)$ be the number of numbers constructable from this bag, using the rules above. Define $u_n$ as the minimum $f(B)$ over all bags $B$ of size $n$. Can we come up with bounds for $u_n$? How does it grow?

I'll stop here, because the variations and questions seem endless.

$\endgroup$
  • $\begingroup$ Did you end up answering your own question? Or you are looking for a smaller number than 55? $\endgroup$ – hyiltiz Aug 1 '17 at 19:37
  • $\begingroup$ @hyiltiz the number $55$ was just to demonstrate that such an $n$ definitely exists. I am looking for the minimum such $n$, which I strongly believe is less than $55$. $\endgroup$ – Colm Bhandal Aug 6 '17 at 11:05
  • $\begingroup$ I would try simulations, since the problem space is considerable. Then, upon inspecting the actual minimum and how the solution is derived at values around it, you might get some mathematical insight to minimize 55 more. $\endgroup$ – hyiltiz Aug 7 '17 at 16:52
  • $\begingroup$ Just saw this online game: 4nums.com $\endgroup$ – Colm Bhandal Aug 7 '17 at 18:09
  • $\begingroup$ That seemed interesting, esp. the "theory", but it is no where near your approach, and is mildly interesting at best (to me). $\endgroup$ – hyiltiz Aug 7 '17 at 18:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.