from Guide to Hacking on Mar 16, 2024

Why 4=10 has exactly 500 levels

A extremely simple math game called "4=10" caught my attention recently. Here's the premise: You are given four single-digit numbers, and your goal is to make the number 10 — by using addition, subtraction, division, multiplication, and a pair of parentheses at most once.

However, one aspect of the game stuck out to me: There are only 500 "levels" in the game. Why is that? There are theoretically 10,000 possible sets of four numbers to pull from. What's stopping the creator from adding more?

How many solutions are there?

One obvious explanation for the meager number of levels is that many sets of four numbers can't ever equal to 10, given these rules. Let's first see how many sets are possible. In other words, we're looking for the possible number of solutions.

I'll programmatically search all possible options, but a pure brute force solution searching over 1.2 million¹ options would take prohibitively long to run. We can cut down the number of options drastically just with a few common sense simplifications.

Simplification #1. Get rid of number ordering. There are four numbers, with 10 possible values for each number. In theory, there are 10,000 total permutations, but this counts duplicates — i.e., any ordering of the numbers "9, 9, 9, 9" is indistinguishable from any other.

To address this, we can consider all possible combinations of four numbers in increasing order. This is simple for us to count with a few for loops.

math/combinations.py

def get_possible_four_number_combinations():
    combinations = set()
    for i in range(10):
        for j in range(10):
            for k in range(10):
                for l in range(10):
                    combinations.add(tuple(sorted((i, j, k, l))))
    return combinations

def get_possible_number_combinations(maximum=10, count=4):
    if count == 0:
        return {tuple()}
    combinations = set()

This gives us 715 total combinations. We can also calculate this in close form: Picking four numbers in increasing order is the same as distributing 9 "+1s" between 5 slots².

• Any "+1s" we place in the first slot determines the first number.
• Any "+1s" we place in the second slot determines how much to add to the first number, to get the second number.
• Any "+1s" we place in the last slot are unused.
• Say "+1s" are denoted with *, and slots are divided by |. Then, the four numbers "1346" become *|**|*|**|***.

In other words, this is also known as a "Stars and Bars" setup. There are 9 stars and 4 bars, so we can use the Stars and Bars expression for $s$ stars and $b$ bars to get the same result 715.

$${s+b \choose b} = {9 + 4 \choose 4} = \frac{13!}{(13-4)!4!} = 715$$

In short, we now only have 715 possible combinations of numbers.

Simplification #2. Ignore ineffective parentheses. For example, say we have the expression 4*3+2-0. Parentheses around (4*3) are useless, since the order of operations already ensures that multiplication happens first.

As a result, instead of counting possible parentheses using positions, we can count using the operations selected. Parentheses including just top-priority operation or just the top two priority operations are ineffective. Parentheses including just the second operation, just the third operation, second and third, or first and third. This makes at most four possible parentheses placements.

Combining both simplifications, we now have 715 possible number combinations x 24 possible operation combinations x 4 parentheses placements = 183,040 options. We've now reduced the number of possible expressions to search, by an order of magnitude — from 1.2 million to 68,640.

We can now search the above set of options exhaustively, to see how many of those expressions actually total 10. We generate all of those possible expressions and evaluate them naively.

math/combinations.py

        return eval(equation) == 10
    except:
        pass
    return False

def get_valid_equations(maximum=10, count=4, parens=True):
    equations = []
    combinations = get_possible_number_combinations(maximum=maximum, count=count)
    for combination in combinations:
        for equation in get_possible_equations(combination, parens=parens):
            if is_equation_equal_to_ten(equation):
                equations.append(equation)
    print(f"Possible {count}-number combinations: {len(combinations)}")
    print(f"Possible equations: {len(equations)}")
    return equations

import string

def get_numbers_from_equations(equation):
    return tuple(item for item in equation if item in string.digits)

Running the above script then gives us a total of 597 total equations. In other words, there are 597 possible solutions. This is quite close to the 500 levels we observed in the game! With that said, there's just one more hitch: The number above includes all possible equations, which is the number of possible solutions; we want the number of questions, where each question is just a set of four numbers. This begs the question: How many sets of four numbers — excluding operations — can equal to 10?

How many levels are there?

Start by updating the script above to count the number of four-number sets that have at least one equation that evaluates to 10.

math/combinations.py

import string

def get_numbers_from_equations(equation):
    return tuple(item for item in equation if item in string.digits)

def get_valid_levels(maximum=10, count=4):
    remaining = set()
    for equation in get_valid_equations(maximum=maximum, count=count):
        remaining.add(get_numbers_from_equations(equation))
    print(f"Possible {count}-number sets: {len(remaining)}")
    return remaining

def get_operations_from_equations(equation):
    return tuple(sorted(item for item in equation if item in OPS))

This gives us 300 total, unique four-number sets. This is a little odd: How does 4=10 have 500 levels then? There simply aren't enough four-number combinations. An unsatisfying explanation would be that some sets are repeated.

However, there's a clue: Some levels actually restrict the operations you can use. Let's see how many sets of four numbers and operations are, combined, unique.

math/combinations.py

def get_operations_from_equations(equation):
    return tuple(sorted(item for item in equation if item in OPS))


def get_valid_levels(maximum=10, count=4, parens=True):
    remaining = set()
    for equation in get_valid_equations(maximum=maximum, count=count, parens=parens):
        remaining.add(get_numbers_from_equations(equation) + get_operations_from_equations(equation))
    print(f"Possible sets of numbers and operations: {len(remaining)}")
    return remaining

import time
for count in range(4, 7):
    start = time.time()
    get_valid_levels(maximum=10, count=count, parens=False)

This gives us 507 total unique combinations of four numbers and operations. And that's it! There are 507 possible levels. This is awful close to the actual number of levels in 4=10 — namely, 500. Odds are, the author wanted a nice even number.

How could we increase the number of levels?

To start, consider increasing the difficulty of the puzzles.

1. Restrict the set of options: We could restrict each operation to exactly one usage. However, after filtering all of our existing equations, we find there is only one possible solution: 3*3+7/7.
2. Find all possibilities: We could alternatively make this more difficult. Ask the player to find all the possible equations for a give combination of numbers. Unfortunately, it looks like only 41 sets of numbers have 4 or more possible equations attached.

One simple way to increase the number of levels is to add more numbers. Instead of using 4 numbers, use 5 or 6. Let's see how the number of possible levels scales with the number of numbers. Before running the entire pipeline however, we can quickly compute the number of possible number combinations to get a rough idea of scaling:

This grows decently quickly, at approximately 2x per count, even without factoring in the number of parentheses. Let's see how search time scales with count.

Scaling is pretty poor, so let's run a few more counts but without factoring in the parentheses.

This is certainly a large expansion of the game, from 500 levels to at least 17,000. Perhaps a future DLC for 4=10 could include bonus levels of this type.

Takeaways

To summarize, we arrived at this number by taking the following steps:

1. There are 3.2 million total permutations of 4 numbers, 4 arithmetic operations, and parentheses.
2. After accounting for permutations, reduce 10,000 permutations of four single-digit numbers to just 715 unique combinations. This reduces the total to 85,800 options.
3. After accounting for ineffective parentheses placement, we reduce from 5 to just 4 possible parentheses placements, reducing the total to just 68,640 options.
4. Evaluating all of these options naively, we find 597 possible equations that evaluate to 10. These are all the possible solutions.
5. Of those valid equations, there are 507 unique sets of four numbers and operations. These are all the possible levels that 4=10 could introduce, by additionally limiting the set of possible operations.

This is extremely close to 4=10's number of levels — namely, 500. So, we declare victory. We also find that increasing the number of numbers grows the number of possible levels by an order of magnitude each time. More possibilities for more levels.

← back to Guide to Hacking