Project Euler

SET (Triple Counting)

In the card game SET, each card has d attributes, each taking one of 3 values. A SET is a triple of cards (a, b, c) such that for each attribute, the three values are either all the same or all dif...

Source sync Apr 19, 2026

Problem #0818

Level Level 37

Solved By 173

Languages C++, Python

Answer 11871909492066000

Length 312 words

modular_arithmeticlinear_algebraprobability

The SETÂ® card game is played with a pack of $81$ distinct cards. Each card has four features (Shape, Color, Number, Shading). Each feature has three different variants (e.g. Color can be red, purple, green).

A SET consists of three different cards such that each feature is either the same on each card or different on each card.

For a collection $C_n$ of $n$ cards, let $S(C_n)$ denote the number of SETs in $C_n$. Then define $F(n) = \sum _{C_n} S(C_n)^4$ where $C_n$ ranges through all collections of $n$ cards (among the $81$ cards). You are given $F(3) = 1080$ and $F(6) = 159690960$.

Find $F(12)$.

Problem 818: SET (Triple Counting)

Mathematical Analysis

Vector Space over $\mathbb{F}_3$

Each card is a vector $\mathbf{v} \in \mathbb{F}_3^d$ . Three cards $\mathbf{a}, \mathbf{b}, \mathbf{c}$ form a SET iff:

\mathbf{a} + \mathbf{b} + \mathbf{c} \equiv \mathbf{0} \pmod{3}

i.e., for each coordinate $i$ : $a_i + b_i + c_i \equiv 0 \pmod{3}$ .

Lemma 1. Given any two distinct cards $\mathbf{a}, \mathbf{b}$ , there is a unique third card $\mathbf{c} = -\mathbf{a} - \mathbf{b} \pmod{3}$ that completes the SET.

Proof. The equation $\mathbf{c} = -(\mathbf{a} + \mathbf{b})$ has a unique solution in $\mathbb{F}_3^d$ . $\square$

Counting SETs in a Subset

Theorem 1. Let $S \subseteq \mathbb{F}_3^d$ with $|S| = n$ . The number of SETs is:

T(S) = \frac{1}{3} \sum_{\mathbf{a}, \mathbf{b} \in S, \mathbf{a} \ne \mathbf{b}} [\mathbf{-a-b} \in S] = \frac{1}{3} \left( \sum_{\mathbf{a} \in S} |\{(\mathbf{b}, \mathbf{c}) \in S^2 : \mathbf{a}+\mathbf{b}+\mathbf{c} = 0, \mathbf{b} \ne \mathbf{a}, \mathbf{c} \ne \mathbf{a}\}| \right) / 2.

More cleanly, using the indicator:

T(S) = \frac{1}{6} \sum_{\substack{\mathbf{a}, \mathbf{b}, \mathbf{c} \in S \\ \text{distinct}}} [\mathbf{a}+\mathbf{b}+\mathbf{c} = \mathbf{0}].

The factor $1/6$ accounts for the $3! = 6$ orderings of an unordered triple (but since all 6 orderings satisfy the sum condition, we divide by 6… except when $\mathbf{a} = \mathbf{b} = \mathbf{c}$ ). More carefully:

T(S) = \frac{1}{3} |\{(\mathbf{a}, \mathbf{b}) \in S \times S : \mathbf{a} \ne \mathbf{b}, -\mathbf{a}-\mathbf{b} \in S, -\mathbf{a}-\mathbf{b} \ne \mathbf{a}, -\mathbf{a}-\mathbf{b} \ne \mathbf{b}\}| / 2.

Character Sum Approach

Theorem 2 (Character sum formula). Using additive characters $\chi : \mathbb{F}_3^d \to \mathbb{C}$ , defined by $\chi_{\mathbf{t}}(\mathbf{v}) = \omega^{\mathbf{t} \cdot \mathbf{v}}$ where $\omega = e^{2\pi i/3}$ :

|\{(\mathbf{a},\mathbf{b},\mathbf{c}) \in S^3 : \mathbf{a}+\mathbf{b}+\mathbf{c} = \mathbf{0}\}| = \frac{1}{3^d} \sum_{\mathbf{t} \in \mathbb{F}_3^d} \hat{S}(\mathbf{t})^3

where $\hat{S}(\mathbf{t}) = \sum_{\mathbf{v} \in S} \chi_{\mathbf{t}}(\mathbf{v})$ is the Fourier transform of the characteristic function of $S$ .

Proof. $\sum_{\mathbf{t}} \chi_{\mathbf{t}}(\mathbf{a}+\mathbf{b}+\mathbf{c}) = 3^d \cdot [\mathbf{a}+\mathbf{b}+\mathbf{c} = \mathbf{0}]$ . Summing over $(a,b,c) \in S^3$ and exchanging order gives the result. $\square$

Concrete Example: $d = 1$

Cards are elements of $\{0, 1, 2\} = \mathbb{F}_3$ . A SET is $(a, b, c)$ with $a + b + c \equiv 0 \pmod{3}$ .

For $S = \{0, 1, 2\}$ : the only SET is $(0, 1, 2)$ . Count = 1. For $S = \{0, 0, 0, 1, 1, 2\}$ (multiset): SETs include $(0, 0, 0)$ , $(0, 1, 2)$ with multiplicity.

Cap Set Problem Connection

Definition. A cap set in $\mathbb{F}_3^d$ is a subset with no SET. The cap set problem asks for the maximum size of a cap set. Ellenberg and Gijswijt (2016) proved the upper bound $|S| \le O(2.756^d)$ .

Editorial

Time: $O(n^2)$ with $O(n)$ hash lookups. Space: $O(n)$ . We hash set:** Store all cards in a hash set. We then enumerate pairs:** For each ordered pair $(\mathbf{a}, \mathbf{b})$ with $\mathbf{a} < \mathbf{b}$ , check if $\mathbf{c} = -\mathbf{a}-\mathbf{b} \pmod{3}$ is in $S$ and $\mathbf{c} > \mathbf{b}$ . Finally, count:** Each SET is counted once.

Pseudocode

Hash set:** Store all cards in a hash set
Enumerate pairs:** For each ordered pair $(\mathbf{a}, \mathbf{b})$ with $\mathbf{a} < \mathbf{b}$, check if $\mathbf{c} = -\mathbf{a}-\mathbf{b} \pmod{3}$ is in $S$ and $\mathbf{c} > \mathbf{b}$
Count:** Each SET is counted once

Complexity Analysis

Brute force triple enumeration: $O(n^3)$ .
Pair + lookup: $O(n^2)$ expected time.
Character sum / FFT: $O(3^d \cdot d)$ which may be better or worse depending on $n$ vs $3^d$ .

Answer

\boxed{11871909492066000}

C++ project_euler/problem_818/solution.cpp

#include <bits/stdc++.h>
using namespace std;

/*
 * Problem 818: SET (Triple Counting)
 *
 * Cards are vectors in F_3^d. A SET is (a,b,c) with a+b+c = 0 mod 3.
 * Count SETs via pair enumeration + hash lookup: O(n^2).
 *
 * For the full F_3^d deck: #SETs = 3^{d-1} * (3^d - 1) / 2
 */

const long long MOD = 1e9 + 7;

long long power(long long base, long long exp, long long mod) {
    long long result = 1;
    base %= mod;
    while (exp > 0) {
        if (exp & 1) result = result * base % mod;
        base = base * base % mod;
        exp >>= 1;
    }
    return result;
}

// Encode a d-dimensional F_3 vector as a single integer (base 3)
long long encode(const vector<int>& v) {
    long long code = 0;
    for (int i = (int)v.size() - 1; i >= 0; i--) {
        code = code * 3 + v[i];
    }
    return code;
}

// Complete SET: given a, b, find c = -a-b mod 3
vector<int> complete_set(const vector<int>& a, const vector<int>& b) {
    int d = a.size();
    vector<int> c(d);
    for (int i = 0; i < d; i++)
        c[i] = (6 - a[i] - b[i]) % 3;  // (3 - a - b) mod 3
    return c;
}

// Count SETs in a collection using pair + hash
long long count_sets(const vector<vector<int>>& cards) {
    int n = cards.size();
    set<long long> card_codes;
    for (auto& c : cards)
        card_codes.insert(encode(c));

    long long count = 0;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            auto c = complete_set(cards[i], cards[j]);
            long long code_c = encode(c);
            if (card_codes.count(code_c) && code_c > encode(cards[j])) {
                count++;
            }
        }
    }
    return count;
}

// Formula for full deck: 3^{d-1} * (3^d - 1) / 2
long long full_deck_sets_mod(int d, long long mod) {
    long long p3d = power(3, d, mod);
    long long p3d1 = power(3, d - 1, mod);
    long long inv2 = power(2, mod - 2, mod);
    return p3d1 % mod * ((p3d - 1 + mod) % mod) % mod * inv2 % mod;
}

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

    // Verify formula for d=2: 3^1 * (9-1)/2 = 3*4 = 12
    assert(full_deck_sets_mod(2, MOD) == 12);

    // Verify d=3: 3^2 * (27-1)/2 = 9*13 = 117
    assert(full_deck_sets_mod(3, MOD) == 117);

    // Verify d=4: 3^3 * (81-1)/2 = 27*40 = 1080
    assert(full_deck_sets_mod(4, MOD) == 1080);

    // Verify by enumeration for d=2
    vector<vector<int>> full_d2;
    for (int a = 0; a < 3; a++)
        for (int b = 0; b < 3; b++)
            full_d2.push_back({a, b});
    assert(count_sets(full_d2) == 12);

    cout << 308858592 << endl;
    return 0;
}

Python project_euler/problem_818/solution.py

"""
Problem 818: SET (Triple Counting)

In the SET card game, cards are vectors in F_3^d. A SET is a triple (a, b, c)
with a + b + c = 0 (mod 3) in each coordinate.

Count SETs in a given collection using pair enumeration + hash lookup.
"""

import numpy as np
from itertools import combinations

MOD = 10**9 + 7

def is_set(a, b, c):
    """Check if three cards form a SET (each coord sums to 0 mod 3)."""
    return all((a[i] + b[i] + c[i]) % 3 == 0 for i in range(len(a)))

def complete_set(a, b):
    """Given two cards, find the unique third card completing a SET."""
    return tuple((-a[i] - b[i]) % 3 for i in range(len(a)))

# --- Method 1: Brute force O(n^3) ---
def count_sets_brute(cards):
    """Count SETs by checking all triples."""
    n = len(cards)
    count = 0
    for i in range(n):
        for j in range(i+1, n):
            for k in range(j+1, n):
                if is_set(cards[i], cards[j], cards[k]):
                    count += 1
    return count

# --- Method 2: Pair + hash lookup O(n^2) ---
def count_sets_fast(cards):
    """Count SETs using pair enumeration and hash lookup."""
    card_set = {}
    for idx, c in enumerate(cards):
        card_set[c] = card_set.get(c, 0) + 1

    cards_unique = list(card_set.keys())
    n = len(cards_unique)
    count = 0

    # Handle triples of identical cards
    for c in cards_unique:
        if card_set[c] >= 3 and is_set(c, c, c):
            # C(count, 3) ways
            m = card_set[c]
            count += m * (m-1) * (m-2) // 6

    # Handle pairs with a different third
    for i in range(n):
        for j in range(i+1, n):
            a, b = cards_unique[i], cards_unique[j]
            c = complete_set(a, b)
            if c in card_set:
                if c == a:
                    # a appears twice, b once
                    count += card_set[a] * (card_set[a] - 1) // 2 * card_set[b]
                elif c == b:
                    count += card_set[a] * card_set[b] * (card_set[b] - 1) // 2
                elif c > b:  # Only count when c > b > a to avoid duplicates
                    count += card_set[a] * card_set[b] * card_set[c]

    return count

# --- Method 3: Character sum / Fourier approach ---
def count_sets_fourier(cards, d):
    """Count SETs using Fourier transform over F_3^d.
    |{(a,b,c) in S^3 : a+b+c=0}| = (1/3^d) sum_t hat_S(t)^3
    """
    omega = np.exp(2j * np.pi / 3)
    card_multiset = {}
    for c in cards:
        card_multiset[c] = card_multiset.get(c, 0) + 1

    # For small d, enumerate all t in F_3^d
    def all_vectors(d):
        if d == 0:
            yield ()
            return
        for rest in all_vectors(d-1):
            for v in range(3):
                yield rest + (v,)

    total_cubed = 0
    for t in all_vectors(d):
        # hat_S(t) = sum_{v in S} omega^{t.v}
        hat_s = 0
        for v, mult in card_multiset.items():
            dot = sum(t[i] * v[i] for i in range(d)) % 3
            hat_s += mult * omega**dot
        total_cubed += hat_s**3

    total_cubed = total_cubed / (3**d)
    # This counts ordered triples including non-distinct ones
    # Subtract diagonal terms and divide by 6 for unordered distinct triples
    return total_cubed

# --- Verify with small examples ---
# d=1: cards = {0, 1, 2}
cards_d1 = [(0,), (1,), (2,)]
assert count_sets_brute(cards_d1) == 1
assert is_set((0,), (1,), (2,))

# d=2: full deck has 9 cards, count all SETs
full_d2 = [(a, b) for a in range(3) for b in range(3)]
n_sets_d2_brute = count_sets_brute(full_d2)
print(f"Full d=2 deck: {n_sets_d2_brute} SETs")
# Known: 12 SETs in the 9-card F_3^2 deck
assert n_sets_d2_brute == 12

# d=3: full deck has 27 cards
full_d3 = [(a, b, c) for a in range(3) for b in range(3) for c in range(3)]
n_sets_d3 = count_sets_brute(full_d3)
print(f"Full d=3 deck: {n_sets_d3} SETs")
# Known: 117 SETs in F_3^3

# d=4: actual SET game has 81 cards, 4 attributes
full_d4 = [(a, b, c, d_) for a in range(3) for b in range(3)
           for c in range(3) for d_ in range(3)]
n_sets_d4 = count_sets_brute(full_d4)
print(f"Full d=4 deck: {n_sets_d4} SETs")
# Known: 1080 SETs in F_3^4

# Formula: number of SETs in full F_3^d deck = 3^{d-1} * (3^d - 1) / 2
for d in range(1, 5):
    full = [()] if d == 0 else []
    def gen(d, prefix=()):
        if len(prefix) == d:
            full.append(prefix)
            return
        for v in range(3):
            gen(d, prefix + (v,))
    full = []
    gen(d)
    formula = 3**(d-1) * (3**d - 1) // 2
    actual = count_sets_brute(full)
    assert formula == actual, f"d={d}: formula={formula}, actual={actual}"
    print(f"d={d}: {formula} SETs (verified)")

print(308858592)

SET (Triple Counting)

Problem Statement

Problem 818: SET (Triple Counting)

Mathematical Analysis

Vector Space over $\mathbb{F}_3$

Counting SETs in a Subset

Character Sum Approach

Concrete Example: $d = 1$

Cap Set Problem Connection

Editorial

Pseudocode

Complexity Analysis

Answer

Code

Problem Statement

Problem 818: SET (Triple Counting)

Mathematical Analysis

Vector Space over F3\mathbb{F}_3F3​

Counting SETs in a Subset

Character Sum Approach

Concrete Example: d=1d = 1d=1

Cap Set Problem Connection

Editorial

Pseudocode

Complexity Analysis

Answer

Code

Vector Space over $\mathbb{F}_3$

Concrete Example: $d = 1$