Problem 1014: Steiner Club

Project Euler Problem 1014 Solution

Count how two nights of the Steiner system S(5,8,24) can meet, which is only in 0, 2 or 4 members, then test the 969 eight-member sets that contain C, G, J, L and V against the 11 given nights; exactly one of them survives. Implementations are available in C++, Python and Java.

Detailed mathematical approach

Problem Summary

A club has $24$ members, named $\mathtt A$ to $\mathtt X$. Every night $8$ of them come, and every combination of $5$ members comes together on exactly one night. The members of the first $11$ nights are given, and we must find all eight members of the night on which $\mathtt C$, $\mathtt G$, $\mathtt J$, $\mathtt L$ and $\mathtt V$ all come, written in alphabetical order. ^[1] In the language of design theory the nights are the blocks of a Steiner system $S(5,8,24)$: there are $24$ points, every block has $8$ points, and every set of $5$ points lies in exactly one block. The warm-up example of the statement, with $7$ members, $3$ per night and every pair together once, is the Steiner system $S(2,3,7)$, the Fano plane. ^[2]

Mathematical Approach

The given nights do not have to be completed to the whole schedule. Two counting arguments show that two different nights always share $0$, $2$ or $4$ members, and this alone singles out the requested night among the $969$ sets of eight members that contain $\mathtt C$, $\mathtt G$, $\mathtt J$, $\mathtt L$ and $\mathtt V$.

1. How many nights contain a given set

Fix a set $S$ of $s\le5$ members and count the pairs $(T,N)$ in which $N$ is a night, $T$ is a set of $5$ members and $S\subseteq T\subseteq N$. Each of the $\binom{24-s}{5-s}$ sets $T$ of five members with $S\subseteq T$ lies on exactly one night, and each night $N$ with $S\subseteq N$ contains $\binom{8-s}{5-s}$ such sets $T$. Counting the pairs in both ways shows that the number of nights containing $S$ is ^[2] ^[4]

$$\lambda_s=\binom{24-s}{5-s}\Big/\binom{8-s}{5-s},$$

which does not depend on the choice of $S$: $\lambda_5=1$, $\lambda_4=5$, $\lambda_3=21$, $\lambda_2=77$, $\lambda_1=253$ and $\lambda_0=759$. The club therefore meets on $759$ nights, and as a consistency check these nights contain $759\cdot\binom85=759\cdot56$${}=42504=\binom{24}5$ sets of five members, exactly as many as there are such sets.

2. How two nights can meet

Fix one night $B$ and let $n_i$ be the number of nights $N$ with $|N\cap B|=i$. Then $n_8=1$, for the night $B$ itself, and $n_5=n_6=n_7=0$, because two different nights with five common members would contradict the uniqueness of the night of those five. Counting the pairs $(S,N)$ with $|S|=s$ and $S\subseteq N\cap B$ in two ways gives, for $s=0,1,\dots,5$,

$$\sum_{i=s}^{8}\binom{i}{s}\,n_i=\binom{8}{s}\,\lambda_s.$$

Solving these equations from $s=4$ downward:

$s=4$: $n_4+70=70\cdot5$, so $n_4=280$;
$s=3$: $n_3+4\cdot280+56=56\cdot21$, so $n_3=0$;
$s=2$: $n_2+6\cdot280+28=28\cdot77$, so $n_2=448$;
$s=1$: $n_1+2\cdot448+4\cdot280+8=8\cdot253$, so $n_1=0$;
$s=0$: $n_0+448+280+1=759$, so $n_0=30$.

Every night therefore meets $B$ in $0$, $2$, $4$ or $8$ members, and two different nights share $0$, $2$ or $4$ members. ^[3]

3. The night of the five given members

The night $N^{*}$ on which $\mathtt C$, $\mathtt G$, $\mathtt J$, $\mathtt L$ and $\mathtt V$ all come consists of these five members and three of the other $19$, so there are $\binom{19}{3}=969$ candidates. None of the $11$ given nights contains all five, so by Section 2 the night $N^{*}$ meets each of them in $0$, $2$ or $4$ members. Testing all $969$ candidates against the $11$ given nights leaves exactly one candidate, and since $N^{*}$ passes the test, that candidate is $N^{*}$.

The whole schedule can also be rebuilt, which confirms the result independently. Write every night as a vector in $\mathbb F_2^{24}$ with a $1$ for each member who comes; the dot product of two such vectors is the parity of the number of members they share. The $11$ given nights and the all-ones vector are linearly independent, so they span a code $C$ with $2^{12}=4096$ words. By Section 2 two nights share $0$, $2$, $4$ or $8$ members, a night has $8$ members and the all-ones vector has $24$, so these $12$ generators are orthogonal to one another and to themselves. Hence $C\subseteq C^{\perp}$, and since both spaces have dimension $12$, $C=C^{\perp}$. Every night of the club is orthogonal to all $12$ generators for the same reason, so it lies in $C^{\perp}=C$ as a word of weight $8$. Exactly $759$ words of $C$ have weight $8$, and the club meets on $759$ nights, so the words of weight $8$ are exactly the nights of the club. The only one of them that contains $\mathtt C$, $\mathtt G$, $\mathtt J$, $\mathtt L$ and $\mathtt V$ is the candidate found above.

The code $C$ has dimension $12$, and its nonzero words have weight at least $8$, as the verification below confirms, so any two of its words differ in at least $8$ positions. Up to a relabelling of the coordinates there is only one such code, the extended binary Golay code, and its words of weight $8$, the octads, are the blocks of $S(5,8,24)$. ^[3]

How the Code Works

The C++ program ^[5] stores a set of members as a 24-bit mask in which bit $i$ stands for the $i$-th letter. encode and decode convert between names and masks and check that the names are valid and distinct, and weight counts the set bits. intersection_counts() starts from $n_8=1$ and evaluates the equations of Section 2 for $s=4,3,\dots,0$; it checks that every $\lambda_s$ is an integer and that no count becomes negative, while $n_5$, $n_6$ and $n_7$ stay $0$. solve forms the $969$ candidates by adding three of the $19$ remaining members to the mask of the five given members, and keeps a candidate only if its intersection with every given night has a size $i$ with $n_i\ne0$. It stops with an error if no candidate or more than one candidate survives, and the main program prints the surviving night as letters in alphabetical order.

With --self-test, run_tests first checks the distribution $(n_0,n_1,\dots,n_8)$${}=(30,0,448,0,280,0,0,0,1)$. It then forms all $4096$ sums of subsets of the $11$ given nights and the all-ones mask by repeated doubling, checks that they are distinct, so that the generators are independent, and collects the masks of weight $8$. It checks that there are $\binom{24}5/\binom85=759$ of them, that the $11$ given nights are among them, that the submasks of these octads contain every set of five members exactly once, $42504$ sets in total, and that the only octad containing the five given members is the night found by solve. The Python and Java versions mirror the C++ program function by function; Python uses math.comb, and Java uses Integer.bitCount for the weights.

Complexity and Verification

The search tests $969$ candidates against $11$ nights, about $10^4$ bit operations, so the answer appears instantly. The self-test handles $4096$ code words and the $2^8-1=255$ nonempty submasks of each of the $759$ octads, which also takes far less than a second. All three programs print the same night and pass the self-test. As an independent check, Gaussian elimination over $\mathbb F_2$ followed by an enumeration of the span confirms that the $12$ generators have rank $12$, that the $4096$ code words have the weights $0,8,12,16,24$ with multiplicities $1,759,2576,759,1$, the weight distribution of the extended binary Golay code, ^[3] and that exactly one octad contains the five given members, the same night as above. This check is not part of the published solutions.

Footnotes and References

The references below supply the background facts used above. The intersection numbers $n_i$, the test that singles out the requested night among the $969$ candidates and the identification of the rebuilt schedule with the schedule of the club are derived explicitly in this article.

Project Euler 1014 — Steiner Club. The official statement describes a club of 24 members in which 8 members come every night and every combination of 5 members comes together on exactly one night, lists the members of the first 11 nights and asks for the night on which C, G, J, L and V all come. Its warm-up example with 7 members, 3 per night and every pair together once has the answer BEG.
Wikipedia — Steiner system. The article defines S(t, k, n), gives λᵢ = C(n − i, t − i) / C(k − i, t − i) for the number of blocks that contain a given set of i points, notes that the Fano plane is an S(2, 3, 7), and states for the Witt design S(5, 8, 24) that every element lies in 253 octads, every pair in 77, every triple in 21, every quadruple in 5 and every set of five in exactly one.
Wikipedia — Binary Golay code. The extended binary Golay code is a 12-dimensional subspace of 𝔽₂²⁴ in which any two distinct words differ in at least 8 coordinates, and up to relabelling the coordinates it is unique. Its code words have the weights 0, 8, 12, 16 and 24, its 759 words of weight 8, the octads, are the blocks of S(5, 8, 24), there are 2576 words of weight 12, and two octads meet in 0, 2 or 4 positions.
Wikipedia — Double counting (proof technique). Counting the elements of one set in two different ways proves that the two resulting expressions are equal; Sections 1 and 2 use this argument for λₛ and for the equations satisfied by the numbers nᵢ.
C++ — Euler1014.cpp. The linked immutable C++ revision contains intersection_counts, solve and the checks run by --self-test. It is the implementation record for this article.

Problem 1014 source code

C++

#include <algorithm>
#include <array>
#include <cstdint>
#include <cstdlib>
#include <iostream>
#include <stdexcept>
#include <string>
#include <unordered_set>
#include <vector>

namespace {

using Mask = std::uint32_t;
constexpr unsigned MEMBERS = 24;
constexpr Mask ALL = (Mask{1} << MEMBERS) - 1;
constexpr std::array<const char*, 11> GIVEN = {
    "ABCDKMPR", "ABJKLMNW", "ACIOQTUW", "ADFMPQTU", "AEFNPTVX", "AEFQRSTW",
    "AEGIMQSU", "BDEKORUX", "BEFGHIKU", "DEFHKOSW", "FHIJKRST"
};

void require(const bool condition, const std::string& description) {
    if (!condition) throw std::runtime_error("Check failed: " + description);
}

unsigned binomial(const unsigned n, const unsigned k) {
    if (k > n) return 0;
    unsigned result = 1;
    for (unsigned i = 1; i <= k; ++i) result = result * (n - i + 1) / i;
    return result;
}

unsigned weight(Mask mask) {
    unsigned count = 0;
    for (; mask; mask &= mask - 1) ++count;
    return count;
}

Mask encode(const std::string& names) {
    Mask mask = 0;
    for (const char name : names) {
        require(name >= 'A' && name <= 'X', "member name");
        const Mask bit = Mask{1} << (name - 'A');
        require((mask & bit) == 0, "distinct members");
        mask |= bit;
    }
    return mask;
}

std::string decode(const Mask mask) {
    std::string names;
    for (unsigned i = 0; i < MEMBERS; ++i) {
        if (mask & (Mask{1} << i)) names += static_cast<char>('A' + i);
    }
    return names;
}

std::array<unsigned, 9> intersection_counts() {
    std::array<unsigned, 9> counts{};
    counts[8] = 1;
    for (unsigned s = 5; s-- > 0;) {
        const unsigned numerator = binomial(24 - s, 5 - s);
        const unsigned denominator = binomial(8 - s, 5 - s);
        require(numerator % denominator == 0, "integral subset multiplicity");
        counts[s] = binomial(8, s) * (numerator / denominator);
        for (unsigned i = s + 1; i <= 8; ++i) {
            const unsigned contribution = binomial(i, s) * counts[i];
            require(counts[s] >= contribution, "nonnegative intersection count");
            counts[s] -= contribution;
        }
    }
    return counts;
}

Mask solve(const std::vector<Mask>& blocks, const Mask target) {
    require(weight(target) == 5, "five target members");
    const auto counts = intersection_counts();
    std::vector<Mask> remaining;
    for (unsigned i = 0; i < MEMBERS; ++i) {
        const Mask bit = Mask{1} << i;
        if (!(target & bit)) remaining.push_back(bit);
    }
    Mask answer = 0;
    for (std::size_t a = 0; a + 2 < remaining.size(); ++a) {
        for (std::size_t b = a + 1; b + 1 < remaining.size(); ++b) {
            for (std::size_t c = b + 1; c < remaining.size(); ++c) {
                const Mask candidate = target | remaining[a] | remaining[b] | remaining[c];
                const bool possible = std::all_of(blocks.begin(), blocks.end(), [&](const Mask block) {
                    return counts[weight(candidate & block)] != 0;
                });
                if (!possible) continue;
                require(answer == 0, "unique compatible night");
                answer = candidate;
            }
        }
    }
    require(answer != 0, "compatible night exists");
    return answer;
}

void run_tests(const std::vector<Mask>& given, const Mask target, const Mask answer) {
    const auto counts = intersection_counts();
    require(counts == std::array<unsigned, 9>{30, 0, 448, 0, 280, 0, 0, 0, 1},
        "intersection distribution");

    std::vector<Mask> generators = given;
    generators.push_back(ALL);
    std::vector<Mask> span{0};
    for (const Mask generator : generators) {
        const std::size_t size = span.size();
        for (std::size_t i = 0; i < size; ++i) span.push_back(span[i] ^ generator);
    }
    std::sort(span.begin(), span.end());
    require(std::adjacent_find(span.begin(), span.end()) == span.end(), "independent generators");

    std::vector<Mask> blocks;
    for (const Mask word : span) {
        if (weight(word) == 8) blocks.push_back(word);
    }
    const auto group_count = static_cast<std::size_t>(binomial(24, 5));
    require(blocks.size() * binomial(8, 5) == group_count, "total number of nights");
    for (const Mask block : given) {
        require(std::binary_search(blocks.begin(), blocks.end(), block), "given night retained");
    }

    std::unordered_set<Mask> covered;
    covered.reserve(group_count);
    Mask reconstructed = 0;
    for (const Mask block : blocks) {
        for (Mask subset = block; subset; subset = (subset - 1) & block) {
            if (weight(subset) == 5) require(covered.insert(subset).second, "five-member group occurs once");
        }
        if ((block & target) == target) {
            require(reconstructed == 0, "unique reconstructed night");
            reconstructed = block;
        }
    }
    require(covered.size() == group_count, "all five-member groups covered");
    require(reconstructed == answer, "agreement with full design reconstruction");
    std::cout << "All checks passed; " << blocks.size() << " nights cover " << covered.size()
              << " five-member groups exactly once.\n";
}

}

int main(int argc, char* argv[]) {
    try {
        const bool self_test = argc == 2 && std::string(argv[1]) == "--self-test";
        if (argc != 1 && !self_test) throw std::invalid_argument("Usage: Euler1014 [--self-test]");
        std::vector<Mask> blocks;
        for (const char* names : GIVEN) {
            blocks.push_back(encode(names));
            require(weight(blocks.back()) == 8, "eight members per given night");
        }
        const Mask target = encode("CGJLV");
        const Mask answer = solve(blocks, target);
        if (self_test) run_tests(blocks, target, answer);
        else std::cout << decode(answer) << '\n';
    } catch (const std::exception& error) {
        std::cerr << error.what() << '\n';
        return EXIT_FAILURE;
    }
    return EXIT_SUCCESS;
}

Python

#!/usr/bin/env python3
"""Project Euler Problem 1014 - Steiner Club."""

import sys
from math import comb

MEMBERS = 24
ALL = (1 << MEMBERS) - 1
GIVEN = (
    "ABCDKMPR", "ABJKLMNW", "ACIOQTUW", "ADFMPQTU", "AEFNPTVX", "AEFQRSTW",
    "AEGIMQSU", "BDEKORUX", "BEFGHIKU", "DEFHKOSW", "FHIJKRST",
)


def require(condition, description):
    if not condition:
        raise RuntimeError("Check failed: " + description)


def weight(mask):
    return bin(mask).count("1")


def encode(names):
    mask = 0
    for name in names:
        require("A" <= name <= "X", "member name")
        bit = 1 << (ord(name) - ord("A"))
        require(mask & bit == 0, "distinct members")
        mask |= bit
    return mask


def decode(mask):
    return "".join(chr(ord("A") + i) for i in range(MEMBERS) if mask >> i & 1)


def intersection_counts():
    counts = [0] * 9
    counts[8] = 1
    for s in range(4, -1, -1):
        numerator = comb(24 - s, 5 - s)
        denominator = comb(8 - s, 5 - s)
        require(numerator % denominator == 0, "integral subset multiplicity")
        counts[s] = comb(8, s) * (numerator // denominator)
        for i in range(s + 1, 9):
            contribution = comb(i, s) * counts[i]
            require(counts[s] >= contribution, "nonnegative intersection count")
            counts[s] -= contribution
    return counts


def solve(blocks, target):
    require(weight(target) == 5, "five target members")
    counts = intersection_counts()
    remaining = [1 << i for i in range(MEMBERS) if not target >> i & 1]
    answer = 0
    for a in range(len(remaining) - 2):
        for b in range(a + 1, len(remaining) - 1):
            for c in range(b + 1, len(remaining)):
                candidate = target | remaining[a] | remaining[b] | remaining[c]
                if not all(counts[weight(candidate & block)] != 0 for block in blocks):
                    continue
                require(answer == 0, "unique compatible night")
                answer = candidate
    require(answer != 0, "compatible night exists")
    return answer


def run_tests(given, target, answer):
    counts = intersection_counts()
    require(counts == [30, 0, 448, 0, 280, 0, 0, 0, 1], "intersection distribution")

    span = [0]
    for generator in list(given) + [ALL]:
        span += [word ^ generator for word in span]
    span.sort()
    require(len(set(span)) == len(span), "independent generators")

    blocks = [word for word in span if weight(word) == 8]
    group_count = comb(24, 5)
    require(len(blocks) * comb(8, 5) == group_count, "total number of nights")
    block_set = set(blocks)
    for block in given:
        require(block in block_set, "given night retained")

    covered = set()
    reconstructed = 0
    for block in blocks:
        subset = block
        while subset:
            if weight(subset) == 5:
                require(subset not in covered, "five-member group occurs once")
                covered.add(subset)
            subset = (subset - 1) & block
        if block & target == target:
            require(reconstructed == 0, "unique reconstructed night")
            reconstructed = block
    require(len(covered) == group_count, "all five-member groups covered")
    require(reconstructed == answer, "agreement with full design reconstruction")
    print(f"All checks passed; {len(blocks)} nights cover {len(covered)} five-member groups exactly once.")


def main(argv):
    try:
        self_test = len(argv) == 2 and argv[1] == "--self-test"
        if len(argv) != 1 and not self_test:
            raise ValueError("Usage: Euler1014.py [--self-test]")
        blocks = []
        for names in GIVEN:
            blocks.append(encode(names))
            require(weight(blocks[-1]) == 8, "eight members per given night")
        target = encode("CGJLV")
        answer = solve(blocks, target)
        if self_test:
            run_tests(blocks, target, answer)
        else:
            print(decode(answer))
    except (ValueError, RuntimeError) as error:
        print(error, file=sys.stderr)
        return 1
    return 0


if __name__ == "__main__":
    sys.exit(main(sys.argv))

Java

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class Euler1014 {
    private static final int MEMBERS = 24;
    private static final int ALL = (1 << MEMBERS) - 1;
    private static final String[] GIVEN = {
        "ABCDKMPR", "ABJKLMNW", "ACIOQTUW", "ADFMPQTU", "AEFNPTVX", "AEFQRSTW",
        "AEGIMQSU", "BDEKORUX", "BEFGHIKU", "DEFHKOSW", "FHIJKRST"
    };

    private static void require(boolean condition, String description) {
        if (!condition) throw new IllegalStateException("Check failed: " + description);
    }

    private static int binomial(int n, int k) {
        if (k > n) return 0;
        int result = 1;
        for (int i = 1; i <= k; ++i) result = result * (n - i + 1) / i;
        return result;
    }

    private static int encode(String names) {
        int mask = 0;
        for (char name : names.toCharArray()) {
            require(name >= 'A' && name <= 'X', "member name");
            int bit = 1 << (name - 'A');
            require((mask & bit) == 0, "distinct members");
            mask |= bit;
        }
        return mask;
    }

    private static String decode(int mask) {
        StringBuilder names = new StringBuilder();
        for (int i = 0; i < MEMBERS; ++i) {
            if ((mask & (1 << i)) != 0) names.append((char) ('A' + i));
        }
        return names.toString();
    }

    static int[] intersectionCounts() {
        int[] counts = new int[9];
        counts[8] = 1;
        for (int s = 4; s >= 0; --s) {
            int numerator = binomial(24 - s, 5 - s);
            int denominator = binomial(8 - s, 5 - s);
            require(numerator % denominator == 0, "integral subset multiplicity");
            counts[s] = binomial(8, s) * (numerator / denominator);
            for (int i = s + 1; i <= 8; ++i) {
                int contribution = binomial(i, s) * counts[i];
                require(counts[s] >= contribution, "nonnegative intersection count");
                counts[s] -= contribution;
            }
        }
        return counts;
    }

    static int solve(int[] blocks, int target) {
        require(Integer.bitCount(target) == 5, "five target members");
        int[] counts = intersectionCounts();
        List<Integer> remaining = new ArrayList<>();
        for (int i = 0; i < MEMBERS; ++i) {
            int bit = 1 << i;
            if ((target & bit) == 0) remaining.add(bit);
        }
        int answer = 0;
        for (int a = 0; a + 2 < remaining.size(); ++a) {
            for (int b = a + 1; b + 1 < remaining.size(); ++b) {
                for (int c = b + 1; c < remaining.size(); ++c) {
                    int candidate = target | remaining.get(a) | remaining.get(b) | remaining.get(c);
                    boolean possible = true;
                    for (int block : blocks) {
                        if (counts[Integer.bitCount(candidate & block)] == 0) {
                            possible = false;
                            break;
                        }
                    }
                    if (!possible) continue;
                    require(answer == 0, "unique compatible night");
                    answer = candidate;
                }
            }
        }
        require(answer != 0, "compatible night exists");
        return answer;
    }

    private static void runTests(int[] given, int target, int answer) {
        int[] counts = intersectionCounts();
        require(Arrays.equals(counts, new int[] {30, 0, 448, 0, 280, 0, 0, 0, 1}), "intersection distribution");

        int[] generators = Arrays.copyOf(given, given.length + 1);
        generators[given.length] = ALL;
        int[] span = new int[1 << generators.length];
        int size = 1;
        for (int generator : generators) {
            for (int i = 0; i < size; ++i) span[size + i] = span[i] ^ generator;
            size *= 2;
        }
        Arrays.sort(span);
        for (int i = 1; i < span.length; ++i) require(span[i] != span[i - 1], "independent generators");

        List<Integer> blocks = new ArrayList<>();
        for (int word : span) {
            if (Integer.bitCount(word) == 8) blocks.add(word);
        }
        int groupCount = binomial(24, 5);
        require(blocks.size() * binomial(8, 5) == groupCount, "total number of nights");
        Set<Integer> blockSet = new HashSet<>(blocks);
        for (int block : given) require(blockSet.contains(block), "given night retained");

        Set<Integer> covered = new HashSet<>(2 * groupCount);
        int reconstructed = 0;
        for (int block : blocks) {
            for (int subset = block; subset != 0; subset = (subset - 1) & block) {
                if (Integer.bitCount(subset) == 5) require(covered.add(subset), "five-member group occurs once");
            }
            if ((block & target) == target) {
                require(reconstructed == 0, "unique reconstructed night");
                reconstructed = block;
            }
        }
        require(covered.size() == groupCount, "all five-member groups covered");
        require(reconstructed == answer, "agreement with full design reconstruction");
        System.out.println("All checks passed; " + blocks.size() + " nights cover " + covered.size()
            + " five-member groups exactly once.");
    }

    public static void main(String[] args) {
        try {
            boolean selfTest = args.length == 1 && args[0].equals("--self-test");
            if (args.length != 0 && !selfTest) throw new IllegalArgumentException("Usage: java Euler1014 [--self-test]");
            int[] blocks = new int[GIVEN.length];
            for (int i = 0; i < GIVEN.length; ++i) {
                blocks[i] = encode(GIVEN[i]);
                require(Integer.bitCount(blocks[i]) == 8, "eight members per given night");
            }
            int target = encode("CGJLV");
            int answer = solve(blocks, target);
            if (selfTest) runTests(blocks, target, answer);
            else System.out.println(decode(answer));
        } catch (RuntimeException error) {
            System.err.println(error.getMessage());
            System.exit(1);
        }
    }
}