Exploit symmetry and complementary counting

Two moves dominate the problems below, and they are the same instinct wearing two faces: don't count what you can compute from something smaller. When a set has a symmetry — the answer is unchanged if you permute the digits, reflect the coordinates, or rotate a ring — you count one representative per equivalence class and scale up, instead of walking every member. When the thing you want is awkward but everything you don't want is easy, you count the complement and subtract. Both turn an enumeration you cannot afford into a fraction of it.

The idea

Symmetry, or orbit counting. A symmetry is a transformation that maps the set of interest onto itself. The transformations form a group, and they partition the set into orbits — classes of elements interchangeable under the symmetry. If every element of an orbit contributes the same amount to the answer, you only need to inspect one of them and multiply by the orbit's size. The classic reduction is by a factor equal to the order of the group: reflect across a line and the work halves; a hexagon's six-fold rotation cuts it to a sixth.

Right Triangles with Integer Coordinates is the clean case. Every right angle sits at the origin, at $P$, or at $Q$; the origin cases are a trivial $3N^2$, and the reflection $(x,y)\!\leftrightarrow\!(y,x)$ across the diagonal pairs "right angle at $P$" with "right angle at $Q$", so counting one and doubling covers both:

triangles_at_p_or_q = sum(
    min(x * m // y, m * (limit - y) // x)
    for x in range(1, limit + 1)
    for y in range(1, limit)
    for m in [math.gcd(x, y)]
)
triangles_at_p_or_q *= 2                 # reflection covers the other vertex
triangles_at_origin = 3 * limit**2

The orbit need not be geometric. In Square Digit Chains the chain a number falls into depends only on its digit-square-sum, so two numbers with the same multiset of digits share a fate: the solution counts strings by that sum — the orbit under digit permutation — and classifies only the $\le 81d$ distinct sums instead of all $10^d$ numbers. Few Repeated Digits, Larger Digit Permutation and Dominating Numbers lean on the same digit symmetry, counting by how many of each digit appears rather than by the specific number. In Maximal Polygons the invariance is a theorem about the objective rather than the input. The largest polygon with given sides is the cyclic one, and permuting its sides only rearranges the isosceles triangles around the centre, so the area depends on the side multiset alone. The average over ordered compositions becomes a sum over integer partitions, each weighted by its orbit size, the multinomial $n!/\prod_j m_j!$, and the enumeration falls from binomially many orderings to about $p(n)$ shapes.

The same collapse happens whenever parts are interchangeable. Sliders is the 15 puzzle with coloured rather than numbered tiles, so two boards are the same board whenever their colours agree: the state space falls from the numbered puzzle's $\approx 10^{13}$ permutations to $16\binom{15}{7} = 102\,960$, and a plain breadth-first search is suddenly enough. In $250250$ an element matters only through its residue mod $250$, so the $250250$ elements become a census of $250$ counts and each residue class contributes one factor $(1+x^{r})^{c_r}$ rather than $c_r$ separate ones. Chandelier finds interchangeability at the level of whole sub-problems: the $360$ sockets split into $12$ interleaved copies of $\mathbb{Z}_{30}$ that must each balance independently, so one census of $\mathbb{Z}_{30}$, convolved with itself, stands in for all twelve.

Canonical representatives. Dividing by the group's order is one way to count orbits; choosing one member of each orbit by rule is another, and often a cleaner one, because nothing has to be divided back out. Binary Circles counts arrangements of bits around a circle, where every rotation is the same circle. The problem's encoding reads each circle starting from its unique all-zeros window, and that is a canonical form. So the solution never generates rotations to deduplicate later: it searches only strings with that prefix, and each one it finds is a different circle. Hexagonal Orchards picks its representatives geometrically. It counts one $60^\circ$ sector of the hexagon and multiplies by six. The sector, $a \ge 1,\ b \ge 0,\ a + b \le n$, is chosen half-open, so each of its two bounding rays belongs to exactly one of the six copies, and the centre to none. Hyperbolic Plane takes the other route through the same boundary problem. Its point set and its geodesics are invariant under the eight symmetries of the square, so it anchors only the points in the closed octant $0 \le y \le x$ and weights each by its orbit size: $8$ in the interior, $4$ on an axis or the diagonal, $1$ at the origin. The orbit–stabiliser theorem supplies those weights, since a point fixed by a reflection has half as many images. A closed domain with weights and a half-open domain with weight $|G|$ give the same total; pick whichever makes the boundary easier to state.

Label first, divide after. Unordered objects are awkward to count and ordered ones are often easy, so a solution can add labels on purpose and take them back out at the end. The division is exact only when the group acts freely, meaning no labelling is left unchanged by a non-trivial relabelling. Music Festival is the free case. Its trios are disjoint and non-empty, so swapping two of them always gives a different labelling, and numbering the $4n$ trios multiplies the count by exactly $(4n)!$. Once they are numbered, an arrangement reduces to a 0/1 incidence matrix of quartets against trios, and each matrix comes from exactly $4!$ assignments per quartet, because a quartet's members are interchangeable too. Both factors come out by double counting, which leaves only the matrices to count. A row-by-row dynamic program does that with a state that records how many columns hold each fill level, and binomial weights stand in for which columns they were.

Nim Square is the case that isn't free. Permuting the three heaps preserves the losing condition, and an XOR convolution of the Grundy values naturally counts ordered triples, but the problem wants $a \le b \le c$: one triple per orbit of $S_3$. A triple with a repeated heap has a smaller orbit, so dividing by six undercounts. In the statement's small case, $6040$ ordered losing triples would give $1006$, and the true count is $1160$. Burnside's lemma repairs this by averaging fixed points over the group, which for triples reads $\tfrac{1}{6}(T + 3F_2 + 2F_3)$: all $T$ ordered triples for the identity, $F_2$ fixed by each of the three transpositions, and $F_3$ fixed by each of the two $3$-cycles. There is no case split over which entries coincide, and the correction terms are cheap, because a repeated heap cancels itself under XOR and leaves a condition on one heap alone.

Symmetry in the search, not just the set. The symmetry can also act on the algorithm's own state. Consonant Circle Crossing keeps a table of every signed sum of the chosen vectors; the table is closed under negation, so of the two candidates $t \pm a$ only $t + a$ needs testing. Flipping signs only translates the configuration or swaps it with its dual, so just two of the $2^{K-1}$ signings are genuinely different. In Pythagorean Tree every subtree is the whole tree, scaled and rotated, and its orientation depends only on its depth and on how many right turns it took mod $4$. The $2^n$ subtrees at depth $n$ therefore fall into four direction classes, and the exponential tree becomes a four-wide dynamic program over depth. In Colouring a Strip the symmetry is a relabelling of the four colours, and it shrinks a transfer matrix. A column boundary naively has to remember each row's tile colour as well as its overhang, which comes to over a hundred states. But the two tiles at a boundary are always adjacent, so their colours always differ, and every ordered pair of distinct colours is the same pair once the colours are permuted. So the state keeps only the two overhangs plus a "vertical domino" flag, ten states in all, and the colours move into the matrix weights: each entry is how many colours a new tile may take (two, three, or six for a pair). Drop the label from the state and keep its count as a multiplier. Translation symmetry counts here too. In Infinite String Tour the string is one block repeated forever, so the answer for digit sum $k$ depends only on $k \bmod T$, and every substring start beyond the first block repeats one inside it. In A Winding Path the symmetry acts on a trajectory. Both height profiles satisfy $H(1-x) = 1 - H(x)$, so the level-set path from $(0,0)$ to $(1,1)$ is its own image under the point reflection through the centre. A deterministic walk that is its own mirror only has to be run to its midpoint and doubled. The one subtlety is recognising the midpoint: either a cell that is its own mirror, which is counted once, or a step whose next cell mirrors the current one, where the two halves meet without a shared cell.

A moving frame. When a rule reads only differences, shifting every value by a constant is a symmetry, and you can quotient it out by measuring everything from where you currently stand. $3$-Like Numbers runs a finite-state machine over digit strings. A substring is divisible by $3$ exactly when the prefix sums at its two ends agree mod $3$, so the machine tracks how many prefixes sit at each residue, along with the running residue and the count so far. Adding a constant to every residue changes none of those agreements, so the state stores the prefix counts relative to the current residue and rotates them after each digit. The running residue drops out and $243$ states become $81$. The digit weights $(4, 3, 3)$ are not symmetric across residues, and that does no harm: a digit is a step, which is already a relative quantity, so its weight is the same in every frame. Whenever a state holds positions and the rule reads only their differences, try storing it relative to the current position.

The Gathering quotients out the same kind of shift, then puts the symmetry to a second use. Balls move on a ring of bowls and the walk stops when they all coincide; rotating every ball together changes nothing, so the configuration lives in the quotient group $\mathbb{Z}_n^m / \Delta$, and the whole diagonal of absorbing states collapses to the single identity element. A random walk on an abelian group is diagonalised by the group's characters, so the expected hitting time is a sum of $1/(1-\lambda)$ over the eigenvalues, with no linear system to solve. That sum still has $n^{m-1}$ terms, and a last symmetry groups them: $\cos(2\pi k/n) = \cos(2\pi(n-k)/n)$, so a term depends only on how many coordinates fall in each cosine class. When the symmetry is a group acting on a Markov chain, it does more than shrink the state space: its Fourier transform hands you the spectrum.

Symmetry among the terms of a sum. The object with the symmetry can be a formula rather than a set. Subset Sums picks out the sums divisible by a prime $p$ with a roots-of-unity filter, an average of a generating function over all $p$-th roots of unity. That is $p$ terms, for every prime up to $10^8$. But each non-trivial root generates the same cycle of powers in a different order, and the term depends only on which powers appear and how often, so all $p - 1$ non-trivial terms are equal. The average collapses to two evaluations: a binomial coefficient from the trivial root and one small constant from the rest. Primality is what makes that a single class. For composite $n$ a term depends on the order of its root, so there is one class per divisor of $n$: for $6$-subsets of $\{1, \dots, 12\}$ the six terms are $924, -2, 6, -20, 6, -2$. The shape is Burnside's again, an average over a group whose elements fall into a few classes, and the question to ask of any such sum is how many distinct terms it really has.

Pair up, and count only the fixed points. The smallest group is an involution, a map that undoes itself, and it splits a set into pairs plus the elements it fixes. When each pair contributes something known, the fixed points are the only thing left to compute. In Fractions of Powers, for odd $k$ the map $i \mapsto n - i$ sends $i^k$ to $-i^k \bmod n$, so the non-zero residues pair off as $r$ and $n - r$, each pair summing to $n$. A sum of fractional parts that looked like it needed every term becomes $(n - z)/2$, where $z$ counts the $i$ with $n \mid i^k$: a multiplicative function, where the original sum was not. Partisan Nim uses the same move as a sign symmetry. Swapping the two players' sides negates the advantage $k$, so the settings with $k \ge 1$ and $k \le -1$ are equally many, and the count wanted is $\tfrac12(\text{All} - Z_0)$ less one correction diagonal. Only the fixed slice $k = 0$, and that correction, are ever computed; the full two-dimensional convolution is never built. Distinct Rows and Columns finds the involution on the answer set. Complementing every entry of a $0/1$ matrix keeps its complexity and sends $k$ ones to $n^2 - k$, so every set of reachable $k$ is closed under reflection. The case analysis classifies block patterns only up to complement, and the final flag array is mirrored in one line, flags |= flags[::-1].

Complementary counting. When $|A|$ is hard but the universe $U$ and the complement $A^{c}$ are easy, use $|A| = |U| - |A^{c}|$ — the complement rule. Non-Abundant Sums wants the integers that are not a sum of two abundant numbers; it marks every sum that is one (over unordered pairs — the swap symmetry again, abundant_numbers[i:] counts each pair once) and sums whatever is left. A Game of Chance reduces fairness to "the deck contains a run of length exactly $2$". That is an "at least one" condition, awkward to count head-on. Its complement, "no run has length $2$", is a pair of compositions of $n$ with a forbidden part, which is easy to count. Hexagonal Orchards does the same in its sector: it counts the visible lattice points, the coprime pairs, and subtracts them from the sector's total.

Symmetry also settles expectations without any enumeration. When the parts of a random object are exchangeable, every part has the same distribution. In Tidying Up A, a uniform composition of $E$ cells into $P$ parts therefore has mean part $E/P$ outright, since the $P$ equal means must add up to $E$. That is what lets the gap widths, which looked indispensable, be averaged out of the Markov chain.

A close cousin is partitioning the answer into mutually exclusive cases and counting each once. Obtuse Angled Triangles turns on the fact that a triangle has at most one obtuse angle, so "obtuse at $O$", "obtuse at $B$" and "obtuse at $C$" are disjoint events whose counts simply add — no inclusion–exclusion needed — and each region is then counted over one symmetric wedge of the taxicab diamond. Dominating Numbers does the same up front: at most one digit value can occupy more than half the positions, so the "digit $v$ dominates" events are exclusive across $v$, and $D(N)$ is a clean sum over $(v, k)$ with no double counting to unwind.

How to reason about it

Reach for symmetry when the object has a transformation that leaves the answer invariant — a reflection, a rotation, a relabelling of interchangeable parts, a permutation of digits, a constant shift of values only compared by difference, a sign flip or complement that undoes itself. Reach for complementary counting when the negation is structurally simpler than the thing itself ("at least one" is usually easier as "not none"), or when the whole splits into disjoint cases you can count separately. The payoff ranges from a constant factor to a change of asymptotics. The constant factors are the familiar ones: halve the coordinate plane, take a sixth of a hexagonal spiral as in Hexagonal Tile Differences, one sector of Pascal's Pyramid, or one quadrant of the band around the ellipse in Tangents to an Ellipse, using its two mirror axes. In Runner and Swimmer the core shares the pool's dihedral symmetry, so checking one vertex and one side checks them all. The change of asymptotics comes when collapsing to orbits turns an exponential enumeration into a polynomial count, as with Sliders' interchangeable tiles and Pythagorean Tree's four direction classes.

The pitfalls all live at the places the symmetry doesn't act freely:

  • Fixed points and self-paired elements. An element the symmetry maps to itself is its own orbit and must not be double-counted or double-scaled. Reflecting across a diagonal, the points on the diagonal are shared; pairing elements, a thing paired with itself is one, not two. Before dividing by $|G|$, ask whether the action is free, as it is in Music Festival. If it isn't, use Burnside's lemma, as Nim Square does; a half-open fundamental domain, as in Hexagonal Orchards' sector, sidesteps the problem by giving every shared boundary to exactly one copy, and weighting by orbit size, as in Hyperbolic Plane, handles it head-on. Under an involution the fixed points are often the whole difficulty: in Fractions of Powers and Partisan Nim they are the only terms left to compute.
  • Boundary cases the group breaks. Digit symmetry is exact until a leading zero makes a shorter number, so the count for the top digit position differs from the rest — a special case every digit-orbit solution here carries explicitly.
  • The complement must cover the universe exactly. $|U| - |A^{c}|$ is only right if $U$ is finite and fully characterised (Non-Abundant Sums leans on the proven bound that every integer above $28123$ is an abundant sum), and disjoint-case counting is only right if the cases truly cannot overlap — verify the exclusivity, don't assume it.
  • Confirm the invariance. A "symmetry" that changes the answer even slightly corrupts everything downstream silently. Check it on a small case: fold the count, and separately brute-force the whole, and make them agree before trusting the fold.
  • Don't assume the answer is built from symmetric pieces. In Chandelier the tempting assumption is that every balanced set of sockets is a union of regular polygons. That is a theorem when $n$ has at most two distinct prime factors. It is false for $360$, which has three: $\mathbb{Z}_{30}$ already has $525$ balanced $6$-subsets but only $495$ unions of polygons. A count built on that pattern would look right and still be wrong. Use the symmetry you can prove, and count the rest exactly.

Problems71 / 71

  • ● 0012 — Highly Divisible Triangular Number
  • ● 0023 — Non-Abundant Sums
  • ● 0027 — Quadratic Primes
  • ● 0034 — Digit Factorials
  • ● 0041 — Pandigital Prime
  • ● 0051 — Prime Digit Replacements
  • ● 0053 — Combinatoric Selections
  • ● 0060 — Prime Pair Sets
  • ● 0068 — Magic 5-gon Ring
  • ● 0091 — Right Triangles with Integer Coordinates
  • ● 0092 — Square Digit Chains
  • ● 0099 — Largest Exponential
  • ● 0107 — Minimal Network
  • ● 0109 — Darts
  • ● 0110 — Diophantine Reciprocals II
  • ● 0116 — Red, Green or Blue Tiles
  • ● 0118 — Pandigital Prime Sets
  • ● 0125 — Palindromic Sums
  • ● 0128 — Hexagonal Tile Differences
  • ● 0130 — Composites with Prime Repunit Property
  • ● 0154 — Exploring Pascal's Pyramid
  • ● 0155 — Counting Capacitor Circuits
  • ● 0156 — Counting Digits
  • ● 0172 — Few Repeated Digits
  • ● 0177 — Integer Angled Quadrilaterals
  • ● 0185 — Number Mind
  • ● 0187 — Semiprimes
  • ● 0194 — Coloured Configurations
  • ● 0199 — Iterative Circle Packing
  • ● 0210 — Obtuse Angled Triangles
  • ● 0219 — Skew-cost Coding
  • ● 0220 — Heighway Dragon
  • ● 0223 — Almost Right-angled Triangles I
  • ● 0224 — Almost Right-angled Triangles II
  • ● 0227 — The Chase
  • ● 0238 — Infinite String Tour
  • ● 0243 — Resilience
  • ● 0244 — Sliders
  • ● 0246 — Tangents to an Ellipse
  • ● 0250 — $250250$
  • ● 0253 — Tidying Up A
  • ● 0265 — Binary Circles
  • ● 0310 — Nim Square
  • ● 0331 — Cross Flips
  • ● 0346 — Strong Repunits
  • ● 0351 — Hexagonal Orchards
  • ● 0395 — Pythagorean Tree
  • ● 0420 — $2 \times 2$ Positive Integer Matrix
  • ● 0475 — Music Festival
  • ● 0478 — Mixtures
  • ● 0564 — Maximal Polygons
  • ● 0565 — Divisibility of Sum of Divisors
  • ● 0635 — Subset Sums
  • ● 0670 — Colouring a Strip
  • ● 0706 — $3$-Like Numbers
  • ● 0761 — Runner and Swimmer
  • ● 0768 — Chandelier
  • ● 0782 — Distinct Rows and Columns
  • ● 0788 — Dominating Numbers
  • ● 0804 — Counting Binary Quadratic Representations
  • ● 0850 — Fractions of Powers
  • ● 0862 — Larger Digit Permutation
  • ● 0926 — Total Roundness
  • ● 0930 — The Gathering
  • ● 0939 — Partisan Nim
  • ● 0951 — A Game of Chance
  • ● 0961 — Removing Digits
  • ● 0972 — Hyperbolic Plane
  • ● 0975 — A Winding Path
  • ● 0983 — Consonant Circle Crossing
  • ● 1000 — Problem $1000$