Project Euler

Matchstick Equations

Each digit 0-9 can be formed using matchsticks with the following costs: | Digit | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | |:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:| | Cost | 6 | 2 | 5 | 5 | 4 |...

Source sync Apr 19, 2026

Problem #0882

Level Level 35

Solved By 207

Languages C++, Python

Answer 15800662276

Length 458 words

dynamic_programminggreedymodular_arithmetic

Dr. One and Dr. Zero are playing the following partisan game.

The game begins with one $1$, two $2's$, three $3's, \ldots, n n$'s. Starting with Dr.One, they make moves in turn.

Dr.One chooses a number and changes it by removing a $1$ from its binary expansion.

Dr.Zero chooses a number and changes it by removing a $0$ from its binary expansion.

The player that is unable to move loses.

Note that leading zeros are not allowed in any binary expansion; in particular nobody can make a move on the number $0$.

They soon realize that Dr.Zero can never win the game. In order to make it more interesting, Dr.Zero is allowed to "skip the turn" several time, i.e passing the turn back to Dr. One without making a move.

For example, when $n = $, Dr.Zero can win the game if allowed to skip $2$ turns. A sample game: $$[1,2,2] \xrightarrow{\text{Dr. One}} [1,0,2] \xrightarrow{\text{Dr. Zero}} [1,0,1] \xrightarrow{\text{Dr. One}} [1,0,0] \xrightarrow[\text{Dr. Zero}]{\text{skip}} [1, 0, 0] \xrightarrow{\text{Dr. One}} [1, 0, 0] \xrightarrow[\text{Dr. Zero}]{\text{skip}} [0, 0, 0]$$ Let $S(n)$ be the minimal number of skips needed so that Dr. Zero has a wining strategy. For example, $S(2) = 2$, $S(5) = 17$, $S(10) = 64$.

Find $S(10^5)$.

Problem 882: Matchstick Equations

Mathematical Analysis

Theorem 1 (Maximum Number with $m$ Matchsticks)

To maximize the numeric value using exactly $m$ matchsticks, use as many digits as possible. Since digit 1 costs 2 matchsticks (minimum cost), the maximum number of digits is $\lfloor m/2 \rfloor$ .

If $m$ is even: use $m/2$ ones, giving $\underbrace{11\cdots1}_{m/2}$ .
If $m$ is odd: replace one “1” with “7” (cost 3), giving $7\underbrace{11\cdots1}_{(m-3)/2}$ .

Theorem 2 (DP Formulation)

Let $f(s)$ = maximum number formable using exactly $s$ matchsticks. Then:

f(s) = \max_{d \in \{0,\ldots,9\}} \left\{ 10 \cdot f(s - c(d)) + d \right\}

where $c(d)$ is the matchstick cost of digit $d$ , with base case $f(0) = 0$ .

Theorem 3 (Counting Valid Equations)

For equations of the form $A + B = C$ using exactly $m$ matchsticks total (including $+$ and $=$ , each costing 2 matchsticks):

The number of valid equations is:

N(m) = \sum_{s_A + s_B + s_C = m - 4} \sum_{A, B} [A + B = C] \cdot [\text{cost}(A) = s_A] \cdot [\text{cost}(B) = s_B] \cdot [\text{cost}(C) = s_C]

Concrete Numerical Examples

Maximum Number by Matchstick Count

$m$	Max number	Representation
2	1	1
3	7	7
4	11	11
5	71	71
6	111	111
7	711	711
8	1111	1111
10	11111	11111
12	111111	111111

Digit Efficiency

Digit	Cost	Value/Cost
1	2	0.50
7	3	2.33
4	4	1.00
2	5	0.40
3	5	0.60
5	5	1.00
0	6	0.00
6	6	1.00
9	6	1.50
8	7	1.14

Small Equations ( $A + B = C$ )

With total matchstick budget = 12 (including 4 for + and =):

$1 + 1 = 2$ : cost $= 2 + 2 + 5 + 4 = 13$ (too many)
$0 + 7 = 7$ : cost $= 6 + 3 + 3 + 4 = 16$ (too many)

With budget = 16: $1 + 1 = 2$ costs $2+2+5+4=13$ … We need cost(A) + cost(B) + cost(C) = budget - 4.

DP Solution Details

The dynamic programming approach maintains:

State: number of matchsticks remaining
Transition: try each digit, recurse on remaining sticks
Memoization: cache results by remaining matchstick count

For equations, we enumerate all possible allocations of matchsticks among $A$ , $B$ , $C$ , and verify $A + B = C$ .

Complexity Analysis

Method	Time	Space
Max number with $m$ sticks	$O(m)$	$O(m)$
Count equations, budget $m$	$O(m \cdot 10^{m/2})$ brute	varies
DP for numbers of cost $s$	$O(m \cdot 10)$	$O(m)$

Answer

\boxed{15800662276}

C++ project_euler/problem_882/solution.cpp

/*
 * Problem 882: Matchstick Equations
 * Matchstick costs: 0->6,1->2,2->5,3->5,4->4,5->5,6->6,7->3,8->7,9->6
 * Max number with m sticks: greedy (all 1s, or 7 + 1s for odd m).
 * DP for counting valid equations A + B = C.
 */
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int COST[] = {6, 2, 5, 5, 4, 5, 6, 3, 7, 6};

int matchstick_cost(int n) {
    if (n == 0) return COST[0];
    int total = 0;
    while (n > 0) { total += COST[n % 10]; n /= 10; }
    return total;
}

string max_number_greedy(int m) {
    if (m < 2) return "";
    if (m % 2 == 0) return string(m / 2, '1');
    return "7" + string((m - 3) / 2, '1');
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cout << "=== Digit Costs ===" << endl;
    for (int d = 0; d <= 9; d++)
        cout << "cost(" << d << ") = " << COST[d] << endl;

    cout << "\n=== Max Number ===" << endl;
    for (int m = 2; m <= 20; m++)
        cout << "m=" << m << ": " << max_number_greedy(m) << endl;

    cout << "\n=== Cost Verification ===" << endl;
    for (int n : {0, 1, 7, 11, 71, 111, 1234}) {
        cout << "cost(" << n << ") = " << matchstick_cost(n) << endl;
    }

    // Count small equations
    cout << "\n=== Equations A+B=C ===" << endl;
    for (int budget = 10; budget <= 30; budget++) {
        int rem = budget - 4;
        int count = 0;
        for (int A = 0; A < 200; A++) {
            int cA = matchstick_cost(A);
            if (cA >= rem) continue;
            for (int B = A; B < 200; B++) {
                int cB = matchstick_cost(B);
                if (cA + cB >= rem) continue;
                int C = A + B;
                int cC = matchstick_cost(C);
                if (cA + cB + cC == rem) count++;
            }
        }
        if (count > 0)
            cout << "budget=" << budget << ": " << count << " equations" << endl;
    }

    return 0;
}

Python project_euler/problem_882/solution.py

"""
Problem 882: Matchstick Equations
Matchstick cost per digit: 0->6, 1->2, 2->5, 3->5, 4->4, 5->5, 6->6, 7->3, 8->7, 9->6.
"""

COST = {0: 6, 1: 2, 2: 5, 3: 5, 4: 4, 5: 5, 6: 6, 7: 3, 8: 7, 9: 6}

def matchstick_cost(n):
    """Total matchstick cost of displaying number n."""
    if n == 0:
        return COST[0]
    total = 0
    while n > 0:
        total += COST[n % 10]
        n //= 10
    return total

def max_number_dp(m):
    """Find maximum number displayable with exactly m matchsticks."""
    if m <= 1:
        return -1
    # dp[s] = max number with exactly s matchsticks, or -1 if impossible
    dp = [-1] * (m + 1)
    dp[0] = 0
    for s in range(1, m + 1):
        for d in range(10):
            c = COST[d]
            if s >= c and dp[s - c] >= 0:
                candidate = dp[s - c] * 10 + d
                if candidate > dp[s]:
                    dp[s] = candidate
    return dp[m]

def max_number_greedy(m):
    """Greedy: maximize digits using 1s (cost 2) and 7 (cost 3)."""
    if m <= 1:
        return -1
    if m % 2 == 0:
        return int("1" * (m // 2))
    else:
        return int("7" + "1" * ((m - 3) // 2))

def count_numbers_with_cost(s, max_digits=6):
    """Count numbers whose matchstick cost is exactly s."""
    count = 0
    upper = 10 ** max_digits
    for n in range(0, min(upper, 10 ** 4)):
        if matchstick_cost(n) == s:
            count += 1
    return count

def count_equations(budget):
    """Count valid A + B = C where total matchstick cost = budget.
    Budget includes 4 for the + and = signs."""
    remaining = budget - 4  # matchsticks for A, B, C
    if remaining <= 0:
        return 0
    count = 0
    # Enumerate small A, B
    for A in range(0, 200):
        cA = matchstick_cost(A)
        if cA > remaining:
            continue
        for B in range(A, 200):  # A <= B to avoid double counting
            cB = matchstick_cost(B)
            if cA + cB >= remaining:
                continue
            C = A + B
            cC = matchstick_cost(C)
            if cA + cB + cC == remaining:
                count += 1
    return count

# --- Verification ---
print("=== Matchstick Costs ===")
for n in range(10):
    print(f"  cost({n}) = {COST[n]}")

print("\n=== Max Number (DP vs Greedy) ===")
for m in range(2, 21):
    dp_val = max_number_dp(m)
    greedy_val = max_number_greedy(m)
    print(f"  m={m:>2}: DP={dp_val:>10}, Greedy={greedy_val:>10}, "
          f"Match={'OK' if dp_val == greedy_val else 'FAIL'}")
    assert dp_val == greedy_val

print("\n=== Matchstick Cost Verification ===")
test_cases = [(1, 2), (7, 3), (11, 4), (71, 5), (111, 6)]
for n, expected in test_cases:
    actual = matchstick_cost(n)
    print(f"  cost({n}) = {actual}, expected {expected}: "
          f"{'OK' if actual == expected else 'FAIL'}")
    assert actual == expected

print("\n=== Small Equations ===")
for budget in range(10, 30):
    cnt = count_equations(budget)
    if cnt > 0:
        print(f"  budget={budget}: {cnt} valid equations")

answer = count_equations(20)
print(f"\nAnswer: equations with budget 20 = {answer}")

# --- 4-Panel Visualization ---

Matchstick Equations

Problem Statement

Problem 882: Matchstick Equations

Mathematical Analysis

Theorem 1 (Maximum Number with $m$ Matchsticks)

Theorem 2 (DP Formulation)

Theorem 3 (Counting Valid Equations)

Concrete Numerical Examples

Maximum Number by Matchstick Count

Digit Efficiency

Small Equations ( $A + B = C$ )

DP Solution Details

Complexity Analysis

Answer

Code

Problem Statement

Problem 882: Matchstick Equations

Mathematical Analysis

Theorem 1 (Maximum Number with mmm Matchsticks)

Theorem 2 (DP Formulation)

Theorem 3 (Counting Valid Equations)

Concrete Numerical Examples

Maximum Number by Matchstick Count

Digit Efficiency

Small Equations (A+B=CA + B = CA+B=C)

DP Solution Details

Complexity Analysis

Answer

Code

Theorem 1 (Maximum Number with $m$ Matchsticks)

Small Equations ( $A + B = C$ )