Problem 106: Special Subset Sums: Meta-testing

Project Euler Problem 106 Solution

EulerSolve provides an optimized solution for Project Euler Problem 106, Special Subset Sums: Meta-testing, with C++, Python, Java, and a step-by-step mathematical explanation.

Problem Summary Let $A=\{a_1<a_2<\cdots<a_{12}\}$ be a candidate special sum set. The second special-sum rule already says that whenever one disjoint subset has more elements than another, its sum must be larger. Therefore the only remaining ambiguity comes from two disjoint subsets $B$ and $C$ with the same size. Problem 106 asks how many unordered pairs $(B,C)$ still need an explicit test for $S(B)\neq S(C)$. The count depends only on the relative positions inside the ordered set, and for $n=12$ the total is $21384$. Mathematical Approach The implementations work entirely with indices $0,1,\dots,n-1$, not with the actual set values. That is the key invariant of the problem: once the set is strictly increasing, the question of whether two equal-size subsets are automatically ordered depends only on how their positions interleave. Why only equal-size pairs survive If $|B|\neq |C|$, the second special-sum condition already rules out equality. If $|B|=|C|=1$, equality is impossible because all elements are distinct....

Detailed mathematical approach

Problem Summary

For a set $A$ of numbers, $S(A)$ is the sum of its elements. A set of $n$ numbers is called a special sum set if any two non-empty disjoint subsets $B$ and $C$ of it satisfy two rules: first, $S(B)\ne S(C)$; second, if $B$ contains more elements than $C$, then $S(B)\gt S(C)$. In this problem the $n$ elements are strictly increasing, $a_1\lt a_2\lt\dots\lt a_n$, and the set is assumed to satisfy the second rule already. A subset pair is an unordered pair of non-empty disjoint subsets. For some pairs these assumptions alone guarantee different sums; the others need to be tested for equality, that is, against the first rule. For $n=4$ only $1$ of the $25$ subset pairs needs to be tested, and for $n=7$ only $70$ of the $966$. We must find how many of the $261625$ subset pairs of a set with $n=12$ elements need to be tested for equality. ^[1] It belongs with Problems 103 and 105, which ask for the optimum special sum set with seven elements and for the total of $S(A)$ over the special sum sets among one hundred given sets; the result here tells a program for those problems which comparisons it may skip. ^[2] ^[3]

The whole solution in one sentence: a pair has to be tested exactly when its two subsets have the same number of elements and, after both are sorted, neither subset is smaller than the other in every place, and these pairs are counted by turning each pair into a walk that steps up at the elements of one subset and down at the elements of the other, which leads to a short sum of binomial coefficients and Catalan numbers. The sections below start with sets small enough to check by hand.

Mathematical Approach

We first sort out the pairs that the two assumptions settle, then prove that every other pair can really have equal sums, and finally count the remaining pairs, once with Catalan numbers and once with a closed form built from two classical sequences.

1. All subset pairs

We describe a subset by the positions of its elements, so $\{1,4\}$ stands for $\{a_1,a_4\}$. For $n=3$ there are six subset pairs: $\{1\},\{2\}$; $\{1\},\{3\}$; $\{2\},\{3\}$; $\{1\},\{2,3\}$; $\{2\},\{1,3\}$; and $\{3\},\{1,2\}$. To count them for any $n$, give each position one of three labels: in $B$, in $C$, or in neither. There are $3^n$ labellings. Those with $B$ empty use only the two other labels, so there are $2^n$ of them; likewise $2^n$ labellings have $C$ empty, and exactly one has both empty. By the inclusion–exclusion principle, which counts the elements of a union of two sets as $|X\cup Y|=|X|+|Y|-|X\cap Y|$, ^[4] exactly $2^n+2^n-1$ labellings have an empty side, so $3^n-2^{n+1}+1$ labellings describe an ordered pair $(B,C)$ of non-empty disjoint subsets. Exchanging the labels of $B$ and $C$ gives the same unordered pair, so the number of subset pairs is

$$N(n)=\frac{3^n-2^{n+1}+1}{2}.$$

For $n=3$ this gives $(27-16+1)/2=6$, and it reproduces the three totals of the statement: $N(4)=(81-32+1)/2=25$, $N(7)=(2187-256+1)/2=966$ and $N(12)=(531441-8192+1)/2$${}=261625$.

2. What the two assumptions settle

Two kinds of pairs never need a test. If $B$ and $C$ have different sizes, the second rule already says that the larger subset has the larger sum. If both subsets have one element, $\{a_i\}$ and $\{a_j\}$ with $i\ne j$, the sums differ because the elements are strictly increasing. For $n=4$ the $25$ pairs split by sizes into $6$ pairs of one element against one, $12$ of one against two, $4$ of one against three and $3$ of two against two. Only the last three pairs are still open.

From $n=4$ on, pairs of equal size are a minority. To build a pair of two subsets with $k$ elements each, choose the $2k$ positions that are used and then the $k$ of them that form $B$. The binomial coefficient $\binom{m}{r}$ is the number of ways to choose $r$ things out of $m$. For $0\le r\le m$ it equals $\frac{m!}{r!\,(m-r)!}$, where $m!=1\cdot2\cdots m$ and $0!=1$; ^[5] for $r\lt0$ and for $r\gt m$ there is no way to choose, and $\binom{m}{r}=0$. Hence there are $\tfrac12\binom{n}{2k}\binom{2k}{k}$ unordered pairs of size $k$, the factor $\tfrac12$ because exchanging $B$ and $C$ gives the same pair. For $n=7$ this gives $21$ pairs of size $1$, $105$ of size $2$ and $70$ of size $3$: $196$ of the $966$ pairs have equal sizes, and the second rule settles the other $770$. Without the $21$ pairs of single elements, $175$ pairs remain open, and $70$ of them will turn out to need a test.

3. The case $n=4$ by hand

For $n=4$ the three open pairs are:

$\{1,2\}$ against $\{3,4\}$: since $a_1\lt a_3$ and $a_2\lt a_4$, adding gives $a_1+a_2\lt a_3+a_4$, so no test is needed;
$\{1,3\}$ against $\{2,4\}$: since $a_1\lt a_2$ and $a_3\lt a_4$, we get $a_1+a_3\lt a_2+a_4$, and again no test is needed;
$\{1,4\}$ against $\{2,3\}$: here $a_1\lt a_2$ but $a_4\gt a_3$. The two comparisons point in opposite directions, and nothing follows.

The last pair can really have equal sums. Take $A=\{3,4,5,6\}$. With four elements, the second rule compares two or three elements with a single one, and already the two smallest elements beat the largest, $3+4=7\gt6$; so every subset with two or three elements has a larger sum than every single element, and the second rule holds. Yet $3+6=4+5=9$. A program that checks the first rule must therefore compare this pair, which confirms the count of $1$ for $n=4$. For $\{3,5,6,7\}$, the optimum special sum set with four elements listed in Problem 103, the test is passed: $3+7=10$ and $5+6=11$. ^[2]

4. One subset below the other

The first two pairs above were settled by one argument that works in general. Let $B$ and $C$ have $k$ elements each, and write their positions in increasing order as $b_1\lt\dots\lt b_k$ and $c_1\lt\dots\lt c_k$. We say that $B$ lies below $C$ if $b_i\lt c_i$ for every $i$: the smallest position of $B$ is smaller than the smallest position of $C$, the second smallest is smaller than the second smallest, and so on. Then every element $a_{b_i}$ is smaller than $a_{c_i}$, and

$$S(C)-S(B)=\sum_{i=1}^{k}\bigl(a_{c_i}-a_{b_i}\bigr)\gt0.$$

So if one subset of a pair lies below the other, the sums differ and the pair needs no test; pairs of single elements are the simplest case. The comparison must be made after sorting. For $B=\{1,3,4\}$ and $C=\{2,5,6\}$ the places give $1\lt2$, $3\lt5$ and $4\lt6$, so $B$ lies below $C$, and $S(B)\lt S(C)$ in every increasing set. For $B=\{1,5,6\}$ and $C=\{2,3,4\}$ the first place gives $1\lt2$, but the other two give $5\gt3$ and $6\gt4$, so neither subset lies below the other.

We call a pair of equal size crossing when neither of its subsets lies below the other. The central claim is that the pairs settled so far are all that can be settled: for every crossing pair there is a strictly increasing set that satisfies the second rule and in which the two subsets have equal sums. The pairs that need to be tested are therefore exactly the crossing pairs. Sections 5 to 7 prove the claim, and Sections 10 to 13 count the crossing pairs.

5. Pairs as walks

Read the positions $1,2,\dots,n$ from left to right and take a walk: at a position of $B$ step up by one, at a position of $C$ step down by one, and at an unused position stay at the same height. Let $h_j$ be the height after position $j$. It is the number of positions of $B$ among the first $j$ minus the number of positions of $C$ among them, and $h_0=0$. The walk ends at height $0$ exactly when the two subsets have the same size. The three open pairs for $n=4$ give the heights $1,2,1,0$, then $1,0,1,0$, and finally $1,0,-1,0$. Only the last walk goes below zero, and only the last pair is crossing.

This is no accident: for a pair of equal size, $B$ lies below $C$ exactly when the walk never goes below zero, that is, $h_j\ge0$ for every $j$. Suppose first that $B$ lies below $C$, and look at the first $j$ positions. If they contain $i$ positions of $C$, these are $c_1,\dots,c_i$, and since $b_1\lt c_1$, …, $b_i\lt c_i$, they also contain the $i$ positions $b_1,\dots,b_i$ of $B$; so $h_j\ge0$. Suppose now that $h_j\ge0$ for every $j$, and take $j=c_i$. The first $c_i$ positions contain exactly $i$ positions of $C$, hence at least $i$ positions of $B$, and these all come before $c_i$, because the position $c_i$ itself belongs to $C$; so $b_i\lt c_i$. In the same way $C$ lies below $B$ exactly when $h_j\le0$ for every $j$. A pair of equal size is therefore crossing exactly when its walk goes above zero at some point and below zero at another. For $B=\{1,5,6\}$ and $C=\{2,3,4\}$ the heights are $1,0,-1,-2,-1,0$, and the pair is crossing. The condition $h_j\ge0$ is the condition of Bertrand's ballot problem with ties allowed: if the votes for two candidates are counted one at a time, the first candidate is never behind. ^[6]

6. The difference of the sums as an area

The walk also measures the difference of the two sums. Write the gaps between neighbouring elements as $d_j=a_{j+1}-a_j$, which are positive, for $j=1,\dots,n-1$. The crossing pair $B=\{1,4\}$, $C=\{2,3\}$ of Section 3 has $S(B)=a_1+a_4$ and $S(C)=a_2+a_3$, so

$$\begin{aligned}&S(C)-S(B)\\&\quad=(a_2-a_1)-(a_4-a_3)\\&\quad=d_1-d_3.\end{aligned}$$

That is, the gaps $d_1,d_2,d_3$ are multiplied by the heights $1,0,-1$ of the walk and added: for $\{3,4,5,6\}$ the gaps $1,1,1$ give $1+0-1=0$, the tie of Section 3, and for $\{3,5,6,7\}$ the gaps $2,1,1$ give $2+0-1=1$; indeed $11-10=1$. The same holds for every pair of equal size:

$$S(C)-S(B)=\sum_{j=1}^{n-1}h_j\,d_j.$$

To see this, write every element as the smallest one plus the gaps before it, $a_i=a_1+d_1+\dots+d_{i-1}$. In $S(C)-S(B)$ the copies of $a_1$ cancel, because both subsets have the same number of elements. The gap $d_j$ is part of every $a_i$ with $i\gt j$, so its coefficient is the number of positions of $C$ after $j$ minus the number of positions of $B$ after $j$. Since both subsets have the same size, this equals the number of positions of $B$ up to $j$ minus the number of positions of $C$ up to $j$, which is $h_j$. This rearrangement is called summation by parts. ^[7]

So $S(C)-S(B)$ is an area between the walk and the zero line, in which the step after position $j$ has the width $d_j$. If the walk never goes below zero, no term is negative, and the term of the first used position is positive, because the walk is at height $1$ there and the gap after it is positive; this proves the result of Section 4 a second time. If the walk goes to both sides, the area has positive and negative parts, and they may cancel. The next section shows that suitable gaps always make them cancel.

7. Every crossing pair can have equal sums

Take a crossing pair. Let $P$ be the sum of the positive heights $h_j$ and $Q$ the sum of the absolute values of the negative ones; both are at least $1$. Choose the gaps

$$d_j=\begin{cases}Q, & h_j\gt0,\\ P, & h_j\lt0,\\ 1, & h_j=0.\end{cases}$$

Then the area of Section 6 is $Q\cdot P-P\cdot Q=0$, so $S(B)=S(C)$. The gaps fix the set up to its first element: with the offsets $x_1=0$ and $x_{j+1}=x_j+d_j$, the elements are $a_i=L+x_i$, where the starting value $L$ is still free. Changing $L$ does not change $S(C)-S(B)$, because both subsets have equally many elements. Take $L=1+x_1+x_2+\dots+x_n$. Then the elements are positive and strictly increasing, and the second rule holds. Indeed, let $B'$ and $C'$ be disjoint non-empty subsets, and let $B'$ have more elements than $C'$. Then $S(B')$ contains at least one more copy of $L$ than $S(C')$, and all offsets are at least $0$, so

$$\begin{aligned}&S(B')-S(C')\\&\quad\ge L-\sum_{i\in C'}x_i\\&\quad\ge L-(x_1+\dots+x_n)=1.\end{aligned}$$

So no argument that uses only the two assumptions can rule out equal sums for a crossing pair: every crossing pair needs a test.

A worked example: for $n=6$, $B=\{1,5,6\}$ and $C=\{2,3,4\}$, the heights $h_1,\dots,h_5$ are $1,0,-1,-2,-1$, so $P=1$ and $Q=1+2+1=4$. The gaps are $4,1,1,1,1$, the offsets $0,4,5,6,7,8$ with the sum $30$, and $L=31$. The set is $\{31,35,36,37,38,39\}$, and indeed $31+38+39=108$${}=35+36+37$. This choice of $L$ is generous; here $L=7$ is already enough, giving $\{7,11,12,13,14,15\}$ with $7+14+15=36=11+12+13$. The next section gives a quick way to confirm the second rule for both sets.

8. A quick check of the second rule

The second rule speaks about all pairs of subsets of different sizes, but for an increasing set it comes down to a few inequalities: the set satisfies the second rule exactly when, for every $m\ge1$ with $2m+1\le n$, the $m+1$ smallest elements have a larger sum than the $m$ largest,

$$\begin{aligned}&a_1+\dots+a_{m+1}\\&\quad\gt a_{n-m+1}+\dots+a_n.\end{aligned}$$

These inequalities are necessary, because the two groups are disjoint subsets with $m+1$ and $m$ elements. They are also sufficient. Let $B'$ have more elements than the disjoint subset $C'$. All elements are positive: $B'$ has at least two elements and $C'$ at least one, so $n\ge3$, and the first inequality, $a_1+a_2\gt a_n$, gives $a_1\gt a_n-a_2\gt0$. Let $m$ be the number of elements of $C'$. Removing the largest elements of $B'$ until $m+1$ are left only makes $S(B')$ smaller, so it is enough to treat $B'$ with $m+1$ elements, and then $2m+1\le n$. The $i$-th smallest element of $B'$ is at least $a_i$, so $S(B')\ge a_1+\dots+a_{m+1}$; in the same way $S(C')\le a_{n-m+1}+\dots+a_n$. For $\{31,35,36,37,38,39\}$ the two checks are $31+35=66\gt39$ and $31+35+36=102$${}\gt38+39=77$; for $\{7,11,12,13,14,15\}$ they are $7+11=18\gt15$ and $7+11+12=30\gt14+15=29$. A program for Problem 105 can check the second rule in this way with at most $5$ comparisons for a set of up to $12$ elements, and then test the first rule on the crossing pairs only.

9. Two examples from Problems 103 and 105

Problem 105 gives $\{81,88,75,42,87,84,86,65\}$ as a set that is not a special sum set, because $65+87+88=75+81+84$. ^[3] Sorted, the set is $42,65,75,81,84,86,87,88$. It satisfies the second rule, since the checks of Section 8 give $107\gt88$, $182\gt175$ and $263\gt261$. The equal sums, $240$ on both sides, come from the positions $B=\{2,7,8\}$ and $C=\{3,4,5\}$, whose walk has the heights $0,1,0,-1,-2,-2,-1,0$. It goes to both sides, so the pair is crossing, as it must be; no other pair of this set has equal sums.

Problem 103 lists $\{11,18,19,20,22,25\}$ as the optimum special sum set for $n=6$. ^[2] The checks $11+18=29\gt25$ and $11+18+19=48\gt22+25=47$ of Section 8 confirm the second rule, and then only $20$ of its $301$ subset pairs, the crossing ones, have to be compared. None of them has equal sums, but some come close: the crossing pattern of Section 7, the positions $\{1,5,6\}$ against $\{2,3,4\}$, gives $11+22+25=58$ against $18+19+20=57$. The special sum set with nine elements from Problem 105 has $9330$ subset pairs, and only $735$ of them are crossing.

10. Counting the crossing patterns

By Section 5, whether a pair is crossing depends only on how its positions interleave, not on the numbers in the set, so we count patterns. A pair of size $k$ uses $2k$ positions, which can be chosen in $\binom{n}{2k}$ ways. Read the used positions from left to right and write the letter $\mathtt B$ or $\mathtt C$ for each, according to the subset it belongs to: the pattern of the pair is a word with $k$ letters of each kind. To count every unordered pair once, we always call $B$ the subset that contains the first used position, so the word starts with $\mathtt B$; counting both orders of every pair is an easy mistake that doubles every count. The other $2k-1$ letters contain $k-1$ further letters $\mathtt B$, so there are $\binom{2k-1}{k-1}$${}=\tfrac12\binom{2k}{k}$ words. Since the first letter is $\mathtt B$, the subset $C$ cannot lie below $B$, and by Section 5 the pair is not crossing exactly when no beginning of the word has more letters $\mathtt C$ than letters $\mathtt B$. Such words are called Dyck words, and their number is the Catalan number ^[8]

$$\mathrm{Cat}_k=\frac{1}{k+1}\binom{2k}{k},$$

which gives $1,1,2,5,14,42,132$ for $k=0,1,\dots,6$.

For $k=2$ the three words are $\mathtt{BBCC}$, $\mathtt{BCBC}$ and $\mathtt{BCCB}$. The first two are Dyck words, in agreement with $\mathrm{Cat}_2=2$, and $\mathtt{BCCB}$ is the crossing pair of Section 3. For $k=3$ there are ten words. Five are Dyck words, $\mathtt{BBBCCC}$, $\mathtt{BBCBCC}$, $\mathtt{BBCCBC}$, $\mathtt{BCBBCC}$ and $\mathtt{BCBCBC}$, and five are crossing: $\mathtt{BBCCCB}$, $\mathtt{BCBCCB}$, $\mathtt{BCCBBC}$, $\mathtt{BCCBCB}$ and $\mathtt{BCCCBB}$, the last being the pair of Section 7. Among the $\tfrac12\binom{2k}{k}$ words, the crossing ones make up the fraction $1-\tfrac{2}{k+1}=\tfrac{k-1}{k+1}$: one third for $k=2$, one half for $k=3$, and more than two thirds from $k=6$ on.

11. The reflection trick

The crossing words can also be counted directly, and this gives a proof of the formula for $\mathrm{Cat}_k$. Take a crossing word that starts with $\mathtt B$. Its walk goes below zero, so the word has a first beginning in which the letters $\mathtt C$ outnumber the letters $\mathtt B$ by one. Exchange $\mathtt B$ and $\mathtt C$ in this beginning and keep the rest. The beginning now has one more $\mathtt B$ than $\mathtt C$, so the new word has $k+1$ letters $\mathtt B$ and $k-1$ letters $\mathtt C$, and it starts with $\mathtt C$. For example, the beginning $\mathtt{BCC}$ of $\mathtt{BCCB}$ becomes $\mathtt{CBB}$, so the word becomes $\mathtt{CBBB}$; in the same way $\mathtt{BCCBBC}$ becomes $\mathtt{CBBBBC}$.

The exchange can be undone. In a word that starts with $\mathtt C$ and has $k+1$ letters $\mathtt B$ and $k-1$ letters $\mathtt C$, the walk starts with a step down to $-1$ and ends at $+2$. It moves one step at a time, so it reaches $+1$ for a first time, and exchanging the letters back up to that point gives a word that starts with $\mathtt B$, has $k$ letters of each kind and goes below zero. Both directions choose the same beginning: the old walk stays at height $0$ or above until it first reaches $-1$, and the new walk, its mirror image up to that point, stays at $0$ or below until it first reaches $+1$. So the crossing words correspond one to one to the words that start with $\mathtt C$ and have $k-2$ further letters $\mathtt C$ among the other $2k-1$ places, and their number is

$$X_k=\binom{2k-1}{k-2}.$$

This gives $X_2=1$, $X_3=5$, $X_4=21$, $X_5=84$ and $X_6=330$, the same numbers as a direct listing of all words. There are $\binom{2k-1}{k-1}$ words in all, $1,3,10,35,126,462$ for $k=1,\dots,6$, and subtracting $X_k$ gives the Catalan numbers back. Over the common denominator $(k-1)!\,(k+1)!$ the numerators are $(k+1)\,(2k-1)!$ and $(k-1)\,(2k-1)!$; then numerator and denominator are multiplied by $k$, and $2k\,(2k-1)!=(2k)!$:

$$\begin{aligned}&\mathrm{Cat}_k=\binom{2k-1}{k-1}-\binom{2k-1}{k-2}\\&\quad=\frac{\bigl((k+1)-(k-1)\bigr)\,(2k-1)!}{(k-1)!\,(k+1)!}\\&\quad=\frac{2k\,(2k-1)!}{(k+1)\,k!\,k!}=\frac{1}{k+1}\binom{2k}{k}.\end{aligned}$$

Reflecting a path at its first step across a line is the classical way to prove this formula, and the article on Catalan numbers gives a version of it as its second proof. ^[8]

12. The number of pairs that need a test

Choosing the size $k$, then the $2k$ used positions, then a crossing word, we obtain the number of pairs that need a test:

$$T(n)=\sum_{k=2}^{\lfloor n/2\rfloor}\binom{n}{2k}\binom{2k-1}{k-2}.$$

The sum starts at $k=2$ because $X_1=0$, and it ends at $\lfloor n/2\rfloor$, the largest whole number not above $n/2$, because $2k$ positions must fit among $n$. For $n=4$ there is one term, $T(4)=\binom44\cdot1=1$. For $n=7$ there are two, $T(7)=\binom74\cdot1+\binom76\cdot5$${}=35+35=70$. These are the two values of the statement. For $n=8$ the terms are $70\cdot1$, $28\cdot5$ and $1\cdot21$, so $T(8)=231$; for $n=10$ they are $210\cdot1$, $210\cdot5$, $45\cdot21$ and $1\cdot84$, so $T(10)=2289$. The values for $n=4,\dots,11$ are $1,5,20,70,231,735,2289$ and $7029$. For $n=12$ the sum has five terms, $k=2,\dots,6$.

13. Walks with flat steps: a closed form

The walks of Section 5 give a second formula, in which the size $k$ no longer appears. Every ordered pair $(B,C)$ of disjoint subsets of equal size, including the pair of two empty subsets, is a walk of $n$ steps, each going up, down or straight on, that starts and ends at height $0$. Let $W_n$ be the number of such walks; for $n=2$ there are three: up then down, down then up, and straight on twice. Choosing the $2k$ steps that are not straight and then the half of them that go up gives

$$W_n=\sum_{k\ge0}\binom{n}{2k}\binom{2k}{k}.$$

These are the central trinomial coefficients: $W_n$ is the coefficient of $x^n$ in $(1+x+x^2)^n$. ^[9] Indeed, multiplying out the $n$ factors means choosing one step for each position, and if a step up contributes $x^2$, a straight step $x$ and a step down $1$, the exponent is $n$ plus the final height. For $n=2$, $(1+x+x^2)^2$${}=1+2x+3x^2+2x^3+x^4$, and the coefficient of $x^2$ is $3$.

Let $M_n$ be the number of these walks that never go below zero; these are the Motzkin numbers. ^[10] Choosing the steps that are not straight and then a Dyck word for them gives

$$M_n=\sum_{k\ge0}\binom{n}{2k}\mathrm{Cat}_k.$$

For $n=4$, writing $\mathtt U$, $\mathtt F$ and $\mathtt D$ for a step up, a flat step and a step down, the nine walks are $\mathtt{UUDD}$, $\mathtt{UDUD}$, $\mathtt{UDFF}$, $\mathtt{UFDF}$, $\mathtt{UFFD}$, $\mathtt{FUDF}$, $\mathtt{FUFD}$, $\mathtt{FFUD}$ and $\mathtt{FFFF}$.

Now the inclusion–exclusion principle of Section 1 counts the walks that go to both sides. From all $W_n$ walks, remove the $M_n$ walks that never go below zero and the $M_n$ walks that never go above zero, which are their mirror images. Only the flat walk belongs to both groups, so it was removed twice and is added back: $W_n-2M_n+1$ walks go to both sides. Exchanging $B$ and $C$ mirrors a walk, so each crossing pair appears as exactly two of these walks, and

$$T(n)=\frac{W_n+1}{2}-M_n.$$

The two sequences begin as follows:

for $n=0,\dots,5$: $W_n=1,1,3,7,19,51$ and $M_n=1,1,2,4,9,21$;
for $n=6,\dots,11$: $W_n=141,393,1107,$$3139,8953,25653$ and $M_n$${}=51,127,323,835,2188,5798$.

So $T(4)=(19+1)/2-9=1$ and $T(7)=(393+1)/2-127=70$, as before. The same reasoning splits the pairs of equal size: there are $(W_n-1)/2$ of them, and in $M_n-1$ of them one subset lies below the other. For $n=7$ these numbers are $196$ and $126$, and $196-126=70$.

14. Why so few pairs need a test

The statement calls the small counts surprising. The share $T(n)/N(n)$ of the pairs that need a test is $4.00\%$ for $n=4$, and $5.56\%$, $6.64\%$, $7.25\%$, $7.64\%$, $7.88\%$, $8.03\%$ and $8.12\%$ for $n=5,\dots,11$. Two effects pull in opposite directions. Among the pairs of equal size, the crossing ones become the majority as the subsets grow, because their share among the words of length $2k$ is $\tfrac{k-1}{k+1}$; for $n=11$, already $7029$ of the $12826$ pairs of equal size, $54.80\%$, need a test. But pairs of equal size become rare, because a walk of $n$ random steps rarely ends exactly where it started. The asymptotic formulas

$$W_n\sim\frac{3^{n+1/2}}{2\sqrt{\pi n}},$$

$$M_n\sim\frac{3^{n+3/2}}{2\sqrt{\pi}\,n^{3/2}},$$

in which $\sim$ means that the ratio of the two sides tends to $1$, ^[9] ^[10] show that $M_n$ is smaller than $W_n$ by a factor of about $n/3$. Since $N(n)$ is close to $3^n/2$, the share is approximately

$$\frac{T(n)}{N(n)}\approx\frac{W_n}{3^n}\approx\sqrt{\frac{3}{4\pi n}},$$

which tends to $0$, but slowly. The share computed from the exact counts is $7.91\%$ for $n=20$, $4.59\%$ for $n=100$ and $1.54\%$ for $n=1000$, where the approximation gives $1.55\%$.

How the Code Works

All three programs count the crossing pairs by listing them, as in Sections 2 to 5, without the formulas of Sections 12 and 13. They work with the positions $0,1,\dots,n-1$, one less than in this article, and never with actual numbers, because by Sections 5 and 7 only the interleaving of the positions matters. For every size $k$ from $2$ to $\lfloor n/2\rfloor$ they examine each unordered pair of $k$-element subsets once, skip it if the two subsets share a position or if one lies below the other (Section 4), and count it otherwise. Pairs of single elements and pairs of different sizes are never generated (Section 2).

The C++ program ^[11] keeps the size, $12$ by default, and a checkpoint flag in Options. parse_arguments accepts --n= followed by decimal digits, which parse_int_after_prefix reads, and --skip-checkpoints; it reports any other argument as unknown and rejects sizes below $2$. masks_of_size(n, k) runs through all $2^n$ bit masks, bit $i$ standing for position $i$, and keeps, in increasing order, those with exactly $k$ one-bits, counted by the compiler built-in __builtin_popcount. solve runs a double loop over the indices $i\lt j$ of this list, so every unordered pair is seen once. The test (a & b) != 0 detects a common position, and auto_ordered reads both masks from the lowest bit up into increasing lists of positions and returns true when one list is smaller than the other in every place, the test of Section 4. Every remaining pair increases count. run_checkpoints compares solve(4) and solve(7) with the statement's $1$ and $70$, and the program stops with exit code $2$ if one of them differs; otherwise main prints solve(n).

The Python program fixes $n=12$ in solve. combinations(range(n), k) from itertools yields the subsets as increasing tuples in lexicographic order, ^[12] stored in a list named masks although they are tuples; any(x in b for x in a) detects a common position, and two all(...) tests on the lists sorted(a) and sorted(b) implement Section 4; the sorting changes nothing, because the tuples are already increasing. The Java program also fixes $n=12$: the recursive genCombos fills one array curr with increasing positions and stores a copy, curr.clone(), whenever $k$ of them are chosen, since the next choices overwrite curr; combosOfSize returns these copies as an int[][]. Its double loop compares every position of one array with every position of the other, all $k^2$ comparisons even after a common position has turned up, and the flags allLt and allGt implement Section 4. Neither of these two programs runs checkpoints. The counts fit easily into the 32-bit int of C++ and Java, and Python's integers have no fixed size. The C++ program, the only one that accepts other sizes, sets no upper limit on $n$: the count would exceed the range of int only from $n=23$ on, the loop bound 1 << n no longer fits into an int from $n=31$ on, and parse_int_after_prefix collects the digits in an int without an overflow check, so a value above $2^{31}-1$ overflows already while it is read, which C++ leaves undefined. The running time, however, is the real limit long before.

Complexity and Verification

For a fixed $k$ the double loop examines $\binom{s}{2}$ pairs, where $s=\binom{n}{k}$: in total $15$ pairs for $n=4$, $805$ for $n=7$ and $888162$ for $n=12$. The squares $\binom{n}{k}^2$ for $k=0,\dots,n$ add up to $\binom{2n}{n}$. ^[5] Since $\binom{n}{k}=\binom{n}{n-k}$, the sizes $k\le n/2$, to which the loop is limited, carry half of this sum, except that for even $n$ the middle square $\binom{n}{n/2}^2$, which has no mirror partner, is counted in full. With $\binom{s}{2}\approx s^2/2$, the loop therefore examines about $\tfrac14\binom{2n}{n}$ pairs, plus about $\tfrac14\binom{n}{n/2}^2$ for even $n$; for $n=12$ this estimate gives $889483$. As $\binom{2n+2}{n+1}$${}=\tfrac{2(2n+1)}{n+1}\binom{2n}{n}$, the number grows by a factor of almost $4$ per extra element on average. A pair costs one bitwise AND in C++, up to $k^2$ comparisons in Python and always $k^2$ in Java, and a disjoint pair at most about $n$ more steps for the order test; masks_of_size also scans $2^n$ masks for each $k$. The largest data structure is the list of subsets for $k=\lfloor n/2\rfloor$, with $\binom{n}{\lfloor n/2\rfloor}$ entries, $924$ for $n=12$; C++ stores each subset as one int mask, Python and Java as a tuple or array of its $k$ positions. Timed from start to finish on a laptop with an Apple M4 Max chip, the C++ program, compiled with g++ -O2, takes about $0.01$ seconds for $n=12$ including its checkpoints, the Java program about $0.07$ seconds and the Python program about $0.2$ seconds; the C++ program needs about half a second for $n=16$ and five seconds for $n=18$. The formula of Section 12, in contrast, has fewer than $n/2$ terms.

The C++ program checks itself with the two values of the statement, $1$ pair for $n=4$ and $70$ for $n=7$. For this article the following was verified with separate programs, which are not part of the published solutions:

A brute force over all $3^n$ labellings of Section 1 found, for every $n\le12$, exactly $N(n)$ subset pairs, $(W_n-1)/2$ pairs of equal size and $T(n)$ crossing pairs, as given by Sections 12 and 13. The two formulas agree for every $n\lt200$, and so does, for $n\le120$, a step-by-step count of the walks that remembers the height and whether the walk has been above or below zero.
The C++ program agrees with the formula for every $n$ from $2$ to $18$, and all three programs agree with it for $n=12$.
A linear-programming check confirmed the meaning of "need to be tested" directly from the definition. For each of the $1+6+25+90+301+966$ subset pairs with $2\le n\le7$, SciPy's linprog with the HiGHS solver ^[13] searched for numbers with $a_{i+1}-a_i\ge1$, with $S(B')-S(C')\ge1$ for all disjoint $B'$, $C'$ with $|B'|\gt|C'|$, and with $S(B)=S(C)$. The strict conditions do not change when all numbers are multiplied by the same positive factor, and a large enough factor makes every positive difference at least $1$, so the margin $1$ replaces the strict inequalities without loss. Such numbers exist exactly for the crossing pairs.
The construction of Section 7 produced a valid set with equal sums for every one of the $1$, $5$, $20$, $70$, $231$, $735$ and $2289$ crossing pairs with $n=4,\dots,10$; the second rule was checked in full for $n\le8$ and with the shortcut of Section 8 for $n=9$ and $10$.
The identity of Section 6 held for $60000$ random pairs in random sets; the shortcut of Section 8 agreed with the full second rule on $20000$ random sets and on all $9933$ sets of $2$ to $6$ numbers from $1$ to $15$; and the exchange of Section 11 is a one-to-one correspondence for every $k$ from $2$ to $8$.

Footnotes and References

The references below supply the background facts used above; the classification of the pairs, the construction of equal sums and both counting formulas are derived in this article.

Project Euler 106 — Special Subset Sums: Meta-testing. The official statement defines special sum sets by the rules S(B) ≠ S(C) and S(B) > S(C) whenever B has more elements than C, assumes n strictly increasing elements that already satisfy the second rule, says that 1 of the 25 subset pairs for n = 4 and 70 of the 966 for n = 7 need to be tested for equality, and asks how many of the 261625 subset pairs for n = 12 need to be tested.
Project Euler 103 — Special Subset Sums: Optimum. A special sum set is optimum if S(A) is minimised for its size; the statement lists {3, 5, 6, 7} for n = 4 and {11, 18, 19, 20, 22, 25} for n = 6 and asks for the set string of the optimum set for n = 7.
Project Euler 105 — Special Subset Sums: Testing. The set {81, 88, 75, 42, 87, 84, 86, 65} is not special because 65 + 87 + 88 = 75 + 81 + 84, while {157, 150, 164, 119, 79, 159, 161, 139, 158} satisfies both rules; the task concerns one hundred sets of seven to twelve elements.
Wikipedia — Inclusion–exclusion principle. A counting technique; for two finite sets it reads |A ∪ B| = |A| + |B| − |A ∩ B|.
Wikipedia — Binomial coefficient. C(n, k) = n!/(k!(n − k)!) is the number of ways to choose an unordered subset of k elements from n elements, and the squares C(n, k)² for k = 0, …, n add up to C(2n, n).
Wikipedia — Bertrand's ballot theorem. If candidate A receives p votes and B receives q votes with p > q, A stays strictly ahead throughout the count with probability (p − q)/(p + q); in the variant with ties allowed, the second candidate is never ahead with probability (p + 1 − q)/(p + 1).
Wikipedia — Summation by parts. Also called Abel's lemma or Abel transformation, it is an analogue of integration by parts that rewrites a sum of terms f_k (g_{k+1} − g_k) so that the differences fall on the other sequence.
Wikipedia — Catalan number. C_n = C(2n, n)/(n + 1) is the number of Dyck words of length 2n, strings of n X's and n Y's in which no initial segment has more Y's than X's. The second proof reflects every bad path after its first contact with the line y = x + 1 and obtains C_n = C(2n, n) − C(2n, n + 1).
OEIS A002426 — Central trinomial coefficients. a(n) is the largest coefficient of (1 + x + x²)ⁿ, which is the coefficient of xⁿ, and equals Σ C(n, 2k) C(2k, k); it counts the paths from (0, 0) to (n, 0) with steps (1, 1), (1, −1) and (1, 0), and a(n) ~ d·3ⁿ/√n with d = √(3/π)/2.
Wikipedia — Motzkin number. M_n counts the routes from (0, 0) to (n, 0) in n steps up, down or straight that never dip below the axis; M_n = Σ C(n, 2k) C_k with the Catalan numbers C_k, and M_n ~ (1/(2√π))·(3/n)^(3/2)·3ⁿ.
C++ — Euler106.cpp. The linked immutable C++ revision contains masks_of_size, auto_ordered, solve and run_checkpoints, which checks the values for n = 4 and n = 7 first. It is the implementation record for this article.
Python — itertools.combinations. combinations(iterable, r) returns the subsequences of length r of the input in lexicographic order, so for range(n) every tuple is increasing; their number is n!/(r!(n − r)!).
SciPy — scipy.optimize.linprog. linprog minimises a linear objective under linear equality and inequality constraints and bounds; its default method, highs, uses the HiGHS solvers, and the status 2 reports an infeasible problem. It served only for the independent check above.

Problem 106 source code

C++

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>

namespace {

struct Options {
    int n = 12;
    bool run_checkpoints = true;
};

bool parse_int_after_prefix(const std::string& arg, const std::string& prefix, int& value) {
    if (arg.rfind(prefix, 0U) != 0U) {
        return false;
    }
    const std::string tail = arg.substr(prefix.size());
    if (tail.empty()) {
        return false;
    }

    int parsed = 0;
    for (char c : tail) {
        if (c < '0' || c > '9') {
            return false;
        }
        parsed = parsed * 10 + static_cast<int>(c - '0');
    }
    value = parsed;
    return true;
}

bool parse_arguments(int argc, char** argv, Options& options) {
    for (int i = 1; i < argc; ++i) {
        const std::string arg(argv[i]);
        if (arg == "--skip-checkpoints") {
            options.run_checkpoints = false;
            continue;
        }
        if (parse_int_after_prefix(arg, "--n=", options.n)) {
            continue;
        }

        std::cerr << "Unknown argument: " << arg << '\n';
        return false;
    }

    return options.n >= 2;
}

std::vector<int> masks_of_size(const int n, const int k) {
    std::vector<int> out;
    const int total = 1 << n;
    for (int mask = 0; mask < total; ++mask) {
        if (__builtin_popcount(static_cast<unsigned>(mask)) == k) {
            out.push_back(mask);
        }
    }
    return out;
}

bool auto_ordered(const int a_mask, const int b_mask, const int n) {
    std::vector<int> a;
    std::vector<int> b;

    for (int i = 0; i < n; ++i) {
        if (((a_mask >> i) & 1) != 0) {
            a.push_back(i);
        }
        if (((b_mask >> i) & 1) != 0) {
            b.push_back(i);
        }
    }

    bool a_all_less = true;
    bool b_all_less = true;
    for (std::size_t i = 0; i < a.size(); ++i) {
        if (a[i] >= b[i]) {
            a_all_less = false;
        }
        if (b[i] >= a[i]) {
            b_all_less = false;
        }
    }

    return a_all_less || b_all_less;
}

int solve(const int n) {
    int count = 0;

    for (int k = 2; k <= n / 2; ++k) {
        const std::vector<int> subsets = masks_of_size(n, k);

        for (std::size_t i = 0; i < subsets.size(); ++i) {
            for (std::size_t j = i + 1; j < subsets.size(); ++j) {
                const int a = subsets[i];
                const int b = subsets[j];
                if ((a & b) != 0) {
                    continue;
                }
                if (auto_ordered(a, b, n)) {
                    continue;
                }
                ++count;
            }
        }
    }

    return count;
}

bool run_checkpoints() {
    if (solve(4) != 1) {
        std::cerr << "Checkpoint failed for n=4" << '\n';
        return false;
    }
    if (solve(7) != 70) {
        std::cerr << "Checkpoint failed for n=7" << '\n';
        return false;
    }
    return true;
}

}  // namespace

int main(int argc, char** argv) {
    Options options;
    if (!parse_arguments(argc, argv, options)) {
        return 1;
    }
    if (options.run_checkpoints && !run_checkpoints()) {
        return 2;
    }

    std::cout << solve(options.n) << '\n';
    return 0;
}

Python

# Problem 106: Special subset sums: meta-testing
# For n=12, how many subset pairs need testing (not auto-ordered)?

from itertools import combinations
from math import comb

def solve():
    n = 12
    count = 0
    for k in range(2, n // 2 + 1):
        # Number of pairs of disjoint subsets of same size k from {0,...,n-1}
        masks = list(combinations(range(n), k))
        for i in range(len(masks)):
            for j in range(i+1, len(masks)):
                a, b = masks[i], masks[j]
                if any(x in b for x in a):
                    continue
                # Check if auto-ordered: for sorted a and b, can they be interleaved
                # such that one always dominates? If a[i] < b[i] for all i or vice versa
                sa = sorted(a)
                sb = sorted(b)
                if all(sa[m] < sb[m] for m in range(k)) or all(sb[m] < sa[m] for m in range(k)):
                    continue
                count += 1
    print(count)

solve()

Java

public class Euler106 {
    public static void main(String[] args) {
        int n = 12, count = 0;
        for (int k = 2; k <= n / 2; k++) {
            int[][] ck = combosOfSize(n, k);
            for (int i = 0; i < ck.length; i++)
                for (int j = i + 1; j < ck.length; j++) {
                    boolean disjoint = true;
                    for (int a : ck[i])
                        for (int b : ck[j])
                            if (a == b)
                                disjoint = false;
                    if (!disjoint)
                        continue;
                    int[] sa = ck[i], sb = ck[j];
                    boolean allLt = true, allGt = true;
                    for (int m = 0; m < k; m++) {
                        if (sa[m] >= sb[m])
                            allLt = false;
                        if (sa[m] <= sb[m])
                            allGt = false;
                    }
                    if (!allLt && !allGt)
                        count++;
                }
        }
        System.out.println(count);
    }

    static int[][] combosOfSize(int n, int k) {
        java.util.List<int[]> result = new java.util.ArrayList<>();
        genCombos(n, k, 0, new int[k], 0, result);
        return result.toArray(new int[0][]);
    }

    static void genCombos(int n, int k, int start, int[] curr, int idx, java.util.List<int[]> result) {
        if (idx == k) {
            result.add(curr.clone());
            return;
        }
        for (int i = start; i < n; i++) {
            curr[idx] = i;
            genCombos(n, k, i + 1, curr, idx + 1, result);
        }
    }

    static int[][] combos(int n) {
        return new int[0][];
    }
}