Three-colour solutions from four-colour cubes

Introduction

Berkove, Eickemeyer and Schulman (BES) [1 Problem 2] ask for the least number of four-colour cubes that guarantees a choice of eight cubes forming a three-colour corner solution: a $2 \times2 \times2$ cube whose exterior faces are monochromatic and use exactly three colours. Touching interior faces need not match. As in BES [1 Section 1], every source cube uses all four colours of one fixed palette; every target uses exactly three of them. A variety is a face colouring up to proper rotation. Collections are multisets of varieties, so repeated copies are allowed.

We prove a sharp threshold for every side length. An $n$-frame consists of the corners and edges of an $n \times n \times n$ cube, using $12n-16$ pieces. The least number of source cubes guaranteeing a three-colour $n$-frame is $16n-3$ (Theorem 4). Exactly two collections of $16n-4$ cubes fail: $4n-1$ copies of each of four varieties, one with a monochromatic corner of each colour, all in the same orientation class. Reflection or any odd colour permutation exchanges these collections. Figure 1 shows the first case, $n=2$. More generally, every failure of size at least $14n$, for $n \ge3$, is confined to one ordinary class with bounded buckets (Theorem 5). Counting pair multiplicities and bucket slacks gives explicit binomial formulas for a band of failures (Theorem 6). This includes the 32 failures of size $16n-5$, twenty-four of which cannot be enlarged; the same counts hold separately at $n=2$ (Theorem 7).

Filling the face interiors gives the complete-cube threshold $\max\{n^3,16n-3\}$ (Corollary 3). In particular, any 64 cubes, each using all four colours of a fixed palette, can all be assembled into a $4 \times4 \times4$ cube with monochromatic faces using exactly three colours. Four is the smallest side length for which this guarantee holds without spare cubes; it holds for every larger side length as well.

For comparison, BES [1 Theorem 5] show that any $12n-16$ four-colour cubes build a four-colour $n$-frame when $n \ge3$. Requiring exactly three exterior colours raises the sharp threshold to $16n-3$.¹ Their completion argument [1 Section 1] gives a four-colour complete cube from any $n^3$ sources when $n \ge3$; our result guarantees exactly three exterior colours when $n \ge4$.

The classification explains the form $16n - 4 = 4(4n - 1)$. Mixing orientation classes allows new corner matches, while repeated-colour demands limit the capacity of each colour bucket. Together these restrictions force an extremal collection into one orientation class and then force the four multiplicities to be equal. We first prove the corner case, including its restricted-target corollary, and then extend the argument to frames.

Model and geometric facts

Reflections are not allowed as moves. Only exterior faces must match the target; internal faces are unrestricted.

A corner type is a cyclically ordered triple of face colours, read counterclockwise when viewed from outside along the corner’s body diagonal. Equivalently, order the three outward face normals to form a positively oriented basis. A trichromatic corner has three distinct colours and two orientations, $abc$ and $acb$. BES [1 Section 2] use clockwise order; our convention reverses every triple, preserving containment and matching. A source cube fits a target corner by a proper rotation if and only if it has the same cyclic corner type: the cyclic alignments of two corner frames are exactly those realised by proper rotations of the cube. Only the presence of a corner type on a source matters: a physical copy occupies one position. Target occurrences remain separate requirements. For the corner problem ($n = 2$), a target is represented by its multiset of eight corner types. A collection builds a corner solution modelled on that target exactly when these eight occurrences can be matched to distinct cubes having the required types.

For distinct colours $a$, $b$, $c$, write $Q(a; b, c)$ for a target whose $b$ and $c$ faces are opposite and whose other four faces have colour $a$. Its corner multiset is $4aab + 4aac$. Write $R(a; b, c)$ for the analogous target with $b$ and $c$ adjacent; its corners are

Finally, write $D(a, b, c)$ for the target with opposite pairs $aa$, $bb$, $cc$; it has four corners of each orientation on $\{a, b, c\}$. These three families suffice for the corner argument. § 5 introduces one further target for larger frames.

The target families test complementary constraints:

The two ordinary classes below supply opposite cyclic orientations. The balance lemma explains why confining a collection to one class obstructs all targets with trichromatic corners.

If every corner type of a variety $v$ occurs on a variety $w$, replacing a copy of $w$ by $v$ cannot create a solution to any target. In particular, it preserves unsolvability. Table 1 records the reduction. Face tuples use the order $+x$, $-x$, $+y$, $-y$, $+z$, $-z$. The rows represent the seven orbits under colour permutations, with rotations already identified. They cover all 68 varieties; four orbits are retained.

Representative	Orbit size	Retained type	Replacement
001123	6	checkerboard $C$	—
010203	8	monochromatic-corner $T$	—
010213	12	pair type $P$	—
010223	12	pair type $P$	—
000123	12	—	001123
001213	12	—	001123
010123	6	—	001123

A reduced variety belongs to bucket $a$ if it has at least two of the three corner types $aab$ with $b \ne a$. The reduction, 38 minimal varieties, orientation classes, checkerboards and buckets below are from BES [1 Section 2, Table 8 and Definition 3]; we count each bucket’s seven mirror pairs as fourteen individual varieties.

The 32 ordinary varieties ($T$ and $P$) split into two classes of 16, corresponding to BES’s $K_o$ and $K_m$ (up to interchanging the names). Every member of a class has exactly the same four trichromatic corner types, one for each three-element colour set. The two classes have opposite orientations. In our convention one class has the trichromatic corner set

one set of BES’s universal corners. Each class contains exactly one $T$ variety for each repeated colour. Even colour permutations preserve the classes; odd colour permutations and reflection exchange them.

Proof. The face-colour multiplicities are 3 + 1 + 1 + 1 or 2 + 2 + 1 + 1. In the first case, the three equal faces either meet at a vertex or contain an opposite pair, giving two orbits. In the second case, both repeated pairs can be opposite, exactly one can be opposite, or both can be adjacent. In the last case, the two monochromatic edges either have perpendicular directions, giving two mirror configurations represented by 010213 and 010223, or are parallel, represented by 010123. These cases cover all varieties. The orbit sizes in Table 1 sum to 68, the total number of varieties [1], so the seven orbits are distinct. The three non-retained representatives contain the corner types of 001123; colour permutations transport these containments to their whole orbits. Table 2 gives the corner sets of the retained representatives. All three ordinary representatives in Table 2 belong to the class of $\Omega$. Even colour permutations preserve $\Omega$ and odd ones reverse it, with triples read cyclically. Applying colour permutations to Table 2 gives the stated incidences and orientation classes. The eight $T$ varieties split evenly between the classes, and even permutations act transitively on the four colours, so each class contains exactly one $T$ variety for each repeated colour. Reflection reverses every trichromatic corner.

Representative	Corner-type set
001123	{012, 013, 021, 031}
010203	{000, 001, 002, 003, 012, 023, 031, 132}
010213	{001, 003, 011, 012, 023, 031, 112, 132}
010223	{002, 003, 012, 022, 023, 031, 122, 132}

The extremal collections

(ii) No minority cubes: $M = 0$. Let $t_a$ and $p_a$ count only majority-class $T$ and $P$ cubes in bucket $a$, and let $n_T$, $n_P$ be their respective totals, so $A = n_T + n_P$. By Lemma 3, $t_a + p_a \le7$. Each $T$ cube belongs to one bucket and each $P$ cube to two. This is BES’s double-count [1 equation (1)]; summing the bucket bounds and using $n_T + n_P = 28 - M$ gives

We use the following construction. If six majority cubes supply $2aaa + 2aab + 2aac$ and a minority cube supports $\{a,b,c\}$, then the minority cube supplies the opposite trichromatic orientation and an unused majority cube supplies the other. Such a cube is available since $A \ge22$. This builds $R(a;b,c)$.

Suppose $M > 0$. We claim that $t_a \ge4$ forces $t_a + p_a \le5$. Otherwise choose six majority cubes in bucket $a$, including at least four $T$ cubes. Any minority cube supports some triple containing $a$, say $\{a,b,c\}$, since a checkerboard’s two supported triples together contain every colour. Each of the at most two $P$ cubes has two of the three types $aax$, so it has $aab$ or $aac$; since $R(a;b,c)$ needs two of each, each $P$ cube can take a position of a type it has. The $T$ cubes have $aaa$ and every type $aax$, so they fill the remaining positions of $2aaa + 2aab + 2aac$, and the construction above gives a solution, a contradiction. In particular, $t_a \le5$ for every $a$.

If $t_a \le3$, the bucket bound gives $2t_a + p_a \le t_a + 7 \le10$. If $4 \le t_a \le5$, the claim gives $2t_a + p_a \le t_a + 5 \le10$. Thus $2t_a + p_a \le10$ in all cases. Each majority $T$ cube contributes two through its single bucket, and each majority $P$ cube contributes one through each of its two buckets. Summing gives

contradicting $A \ge22$ from (2). Therefore $M = 0$.

(iii) Equal multiplicities: $t_a = 7$. With $M = 0$, (3) forces $n_P = 0$. All 28 cubes are majority-class $T$ cubes, and the four bucket bounds force each $t_a = 7$.

Since the reduced collection contains no checkerboards, no replacement occurred: the original collection was already reduced. $\square$

Proof. Otherwise every 28-cube subcollection would have the form in Theorem 1. Take one such subcollection $S$ and let $v$ be the remaining cube. Remove from $S$ a cube of a variety different from $v$, and insert $v$. The multiplicity of $v$’s variety is now 1 or 8, whereas every variety in a collection described by Theorem 1 has multiplicity 0 or 7, a contradiction. $\square$

Sharpness

Proof. Take seven copies of each of the following four face tuples (Figure 1):

010203, 011213, 021223, 031323.

These are $T$ cubes with repeated colours 0, 1, 2, 3, respectively, all in the same ordinary orientation class. A target with any trichromatic corner requires both orientations by Lemma 1, whereas the collection supplies only one. A target without one is $Q(a;b,c)$; every one of its eight corners has colour $a$ twice, so only the seven $T$ cubes of repeated colour $a$ are usable. No three-colour target is possible. Reflection gives the analogous example in the other orientation class. Theorem 1 excludes all other collections. Every odd colour permutation exchanges the two orientation classes and hence these two collections. □

Remark (Allowing fewer colours). If targets may use at most three colours, 28 cubes suffice. In either exceptional collection, four $T$ cubes of repeated colour $a$ and four of repeated colour $b$ supply $aaa + 3aab + bbb + 3bba$. These are the corners of a two-colour cube whose three $a$ faces meet at one vertex and whose three $b$ faces meet at the opposite vertex. Every other 28-cube collection builds a three-colour target by Theorem 3. This gives an upper bound, not an exact threshold, for that variant.

Proof. By Theorems 1 and 3, a 28-cube collection avoiding these families is unsolvable. The swap in the proof of Theorem 2 rules out a 29-cube collection avoiding them. There are $\binom{4}{3}=12$ varieties each of $Q$ and $R$: choose $a$ and the unordered pair $\{b,c\}$. There are $\binom{4}{3}=4$ varieties of $D$, one for each three-colour set.

Remark. For the palette $\{0,1,2,3\}$, write $\delta(xyz)=\nu(xyz)-\nu(xzy)$. Applying (1) to the different colour pairs gives

This common integer is the cube’s degree, relative to $\Omega$. Reflection negates the degree, as does each transposition of colour labels; thus even colour permutations preserve it and odd ones negate it. Each ordinary representative in Table 2 has eight distinct corner types, so each occurs once; the two ordinary classes therefore have degrees $+1$ and $-1$. The checkerboard representative has neither 023 nor 032, so its degree, and that of every checkerboard, is zero.

Frames of arbitrary side length

An $n$-frame consists of the eight corner cubes and the $n-2$ further cubes on each of the twelve edges of an $n \times n \times n$ cube. Thus it contains $L=12n-16$ cubes. Its six exterior faces are monochromatic and use exactly three colours; face interiors are not part of the frame. This is the frame model of BES [1 Section 1], with three target colours instead of four.

The corner-containment reduction also preserves edge availability: an edge occurs in a corner, so containment of corner types implies containment of edge types [1 Section 2, after Definition 2]. An edge type is an unordered pair of colours, allowing repetition. Every ordinary variety has all six bichromatic edge types. A checkerboard has five, missing precisely the pair of its singleton colours; different checkerboards miss different pairs. These facts follow from the representatives in Table 2, and also appear in BES’s frame arguments [1 proofs of Lemmas 7–8 and Table 5]. A reduced cube has an $aa$ edge if and only if it belongs to bucket $a$.

Proof. If a checkerboard variety occurs at least $4n$ times, use eight copies for a supported $D$ corner solution. Its remaining copies supply at least $4(n-2)$ neighbours for each required edge type. Otherwise every checkerboard variety occurs at most $4n-1$ times. Remove any $D$ corner solution. Each of its three bichromatic edge types then has at least

available suppliers. In either case, the union of the supplier sets for two edge types is the entire residual collection, since no reduced cube misses two bichromatic types. There are at least $12(n-2)$ remaining cubes, so Hall’s inequalities hold for all edge positions.

One more target supplies the growing repeated-colour demands. For distinct $a,b,c$, let $U(a,b;c)$ have face tuple $(a,b,a,b,a,c)$. Its corner and edge multisets are respectively

Write $T_a$ for the $T$ variety with repeated colour $a$ in a given ordinary class. Thus an ordinary class supplies a $U$-frame using $3n-2$ of its $T_a$ cubes, $n$ of its $T_b$ cubes, and $1+8(n-2)$ other cubes, together with one minority cube supporting $\{a,b,c\}$. The $T_a$ cubes fill four corners and the $3(n-2)$ monochromatic $aa$ edge positions; the $T_b$ cubes fill two corners and the $n-2$ monochromatic $bb$ positions. The minority cube and one further cube from the same ordinary class fill the two trichromatic corners. Every remaining edge is bichromatic and can use any ordinary cube.

Proof. Reduce a failing collection as before. Let $A \ge B$ count the two ordinary classes, let $C$ count checkerboards, and put $M=B+C$. Write $t_a,p_a,n_T,n_P$ for the majority-class counts. Lemma 4 excludes a $D$ corner solution. The orientation count from Theorem 1 therefore gives

A majority bucket of size $4n$ would build a $Q$-frame: eight of its cubes supply the corners, $4(n-2)$ supply the monochromatic edge positions, and $8(n-2)$ other majority cubes supply the bichromatic positions. There are enough since $A \ge12n-16$. Thus

Some $t_a \ge3n-2$. At most one colour has fewer than $n$ majority $T$ cubes, since two such colours would give

If $M>0$, a minority cube supports a triple containing $a$ and another colour $b$ with $t_b \ge n$. The $U(a,b;c)$ construction then applies. After its $4n-1$ majority corner and monochromatic-edge cubes have been selected, at least $A-(4n-1) \ge10n-5 \ge8(n-2)$ ordinary cubes remain. This contradiction gives $M=0$. No checkerboards remain, so the reduction made no replacements in the original collection.

Conversely, one ordinary class cannot supply both orientations of a trichromatic corner. Lemma 1 leaves only $Q$ targets. Their corners and monochromatic edges require $4n$ cubes from one bucket, exceeding its capacity $h$.

:::

Proof of Theorem 4. For $n=2$, use Theorem 3. For $n \ge3$, apply Theorem 5. At size $4h$, purity and $n_T+2n_P \le4h=n_T+n_P$ force $n_P=0$, and all four $T$ multiplicities equal $h$. Both collections fail by the converse. At size $4h+1$ the bucket inequalities are impossible, proving the upper bound.

distinct cubes with an $aa$ edge for its corners and monochromatic edges, while bucket $a$ has at most $h=4n-1$ cubes. Every listed collection therefore fails. Finally, adding any cube to a pair case produces a collection of size $16n-4$ still containing a $P$ cube; Theorem 4 excludes it from the failing collections of that size.

Corollary 2. For $n \ge3$, every collection of at least $16n-3$ source cubes has an $n$-frame modelled on one of the $40$ targets of types $Q,D,U$.

Proof. The frame counting argument uses only these three types: avoiding them forces purity and four bucket capacities of $4n-1$, hence at most $16n-4$ cubes. There are twelve $Q$ targets and four $D$ targets. The ordered choice of three distinct colours in $U(a,b;c)$ gives $4\cdot3\cdot2=24$ varieties: their face multiplicities $3,2,1$ recover $a,b,c$, respectively. These families are disjoint.

Corollary 3 (Complete cubes). For every integer $n \ge2$, the sharp threshold for a complete $n \times n \times n$ cube with exactly three exterior colours is

In particular, $G(2)=29$, $G(3)=45$, and $G(n)=n^3$ for $n \ge4$.

Proof. Both terms are necessary: an assembly uses $n^3$ pieces, and contains an $n$-frame. Conversely, construct a frame using Theorem 4. Each face-interior position prescribes just one colour, which every unused source cube has; interior positions prescribe none. Thus arbitrary unused cubes complete the assembly whenever at least $n^3$ pieces are available.

Formal verification and computation

The frame and complete-cube thresholds and restricted-target corollaries are formalised in Lean 4 and mathlib [2, 3], both at v4.35.0, for arbitrary indexed families of four-colour cubes. Solutions select distinct copies and proper rotations matching the exposed faces at every required position. The frame statements cover every side length $n \ge2$. The threshold and sharpness statements, and the corner restricted-target statements, use no catalogue indices. The forty-target extension specifies its target by a canonical index. The classifications and their counts concern multisets of rotation classes over a fixed palette. Kernel checks establish the catalogue and finite geometry; a palette-independent lemma equates cyclic corner matching with physical placement.

The stability criterion has a physical-family statement. Its counting proof constructs a bijection between failing multisets and the twelve pair multiplicities with four bucket slacks, then applies stars and bars. Inclusion-maximality is formalised using the pointwise order on all source multiplicities. The original comparator challenge covers thirty-five earlier results; the stability, near-extremal and forty-target extensions have library proofs and axiom guards, but are outside that challenge. Appendix § 9 describes the verification scope.

The Lean proof uses counting and finite Hall certificates. Its corner-case proof of the extremal classification treats checkerboards and the smaller ordinary class separately. The stability proof combines them and supplies the larger-frame and near-extremal classifications. Finite checks establish each target’s corner and edge requirements, while the allocation and counting proofs are symbolic in the side length. Neither the written proof nor the formalisation enumerates all source collections.

A computational search found the corner obstruction and agreed with the corner threshold; separate scripts check the geometric tables, incidences, edge constructions and sample frame obstructions. The correctness of these external computations is not assumed in either the written proof or the formalisation.

In the guaranteed range, an assembly can be found by testing just 28 $Q,R,D$ targets when $n=2$ (Corollary 1), or 40 $Q,D,U$ targets when $n \ge3$ (Corollary 2), using capacitated bipartite matching. Testing all 120 targets decides feasibility for arbitrary smaller collections; the restricted-target guarantee alone does not do so. Source varieties have capacities equal to their available multiplicities; corner and edge requirements have capacities equal to their demands. A source is adjacent to a requirement when it has the required corner or edge type. Grouping identical requirements keeps the number of vertices and edges bounded independently of the side length; only the capacities vary. An integral flow meeting all demands determines a frame, and compatible proper rotations can then be chosen. Unused cubes complete the assembly whenever at least $n^3$ pieces are available.

Further questions

Classifying failures below the stability range would extend Theorem 5. Cuboids pose a separate problem: for each $k \ge1$, take $2k$ copies of each of the six checkerboards. These $12k$ cubes cannot fill a $2 \times2 \times3k$ box in exactly three colours. Every target corner must be trichromatic, forcing a $D$ target. Every position then demands the same bichromatic edge type along the long axis, including the corners. One checkerboard lacks that type, so only $10k$ cubes are usable for $12k$ positions. Thus assembly from exactly the volume fails for arbitrarily large cuboids, even though it holds for cubes of side length at least four.

Declaration of AI-generated research and review

GPT-6-Astra (OpenAI), used through Codex, developed the original research argument, computational search, Lean formalisation and manuscript under the author’s direction. Claude Opus 5.5 (Anthropic), used through Claude Code, contributed the minority-cube argument, balance proof, further mathematical simplifications, illustrations and review. Subsequent Codex revisions incorporated and extended these contributions. Detailed attribution and review scope are recorded in the repository’s formalization.yaml. The human author initiated and directed the research and accepts responsibility for the paper’s content and the accuracy of this disclosure.

Verification details

Thirty-five results and the required definitions are restated in a standalone verification file (the comparator challenge) importing only mathlib. The stability and near-extremal classifications, their counts and the forty-target extension are additional library theorems, with physical-family interfaces where appropriate and explicit axiom audits; they are not yet added to that challenge. Automated checks compare the challenge statements with the proof library and replay the proofs through the Lean, NanoDa and con-ron kernels.

The audit reports three standard axioms: propext, Classical.choice and Quot.sound. No proof uses holes or native_decide. The repository³ provides sources, reproduction commands and details of the statement checks. The physical model and palette-independent geometry come from the shared colour-cubes-core library [4]. The challenge restates its definitions locally.

References