MATH.4:5 - Archetypal Grounding

MATH.4:5.1 - Obtain quotient and remainder together

Given a natural number n and a fixed positive integer d, construct natural numbers q,r such that n=q*d+r and 0≤r<d.

At n=0, return (0,0). The equation holds, and positivity of d gives the remainder bound.

Suppose the result for n is (q,r). To obtain the result for n+1:

• if r+1<d, return (q,r+1);
• otherwise return (q+1,0).

Because r<d and the values are integers, the second branch has r+1=d. In the first branch, n+1=q*d+(r+1); in the second, n+1=(q+1)*d+0. Both branches preserve the required bound. This proves the recursive construction for all natural-number inputs.

For d=3, successive witnesses include:

The output for 8 determines both two completed groups of three and a remainder of two. Keeping only the remainder would lose the number of completed groups. MATH.2 explains which questions such a reduced result can still answer.

The construction takes one successor step per unit of n. It exposes the witness and proof economically as mathematics, but a large encoded integer can call for a different division algorithm. If division with the same convention is already supplied, use that operation.

Changing the parameter to d=0 defeats the specification: no natural r satisfies 0≤r<0. This returns a failed input condition before any recursive step. Extending the input to negative integers also requires a new case; the natural-number recursion does not cover that extension.

MATH.4:5.2 - Strengthen the construction to color a tree

Consider finite binary trees formed as Leaf or Branch(left,right). A leaf is one vertex. A branch adds a new root with edges to the roots of its two constituent trees. The constituent vertices occur separately in the constructed tree.

The required output colors each vertex 0 or 1 so that each edge joins different colors. Suppose a first attempt always colors a root zero. At a new branch, using those subtree results unchanged would give edges from zero to zero.

Generalize the construction: Color(t,c) takes a tree and a required root color c∈{0,1}. Its result must have root color c and different colors across every edge.

• For Leaf, return its single vertex with color c.
• For Branch(left,right), color the new root c, and use Color(left,1-c) and Color(right,1-c) for its constituent trees.

The leaf has no edge to violate the property. At a branch, the induction hypotheses supply the property within each constituent tree. Their roots have color 1-c, so both new edges also join different colors. The construction therefore satisfies the specification for both choices of c.

For Branch(Leaf,Branch(Leaf,Leaf)) with root color 0, the two children receive color 1 and the two grandchildren receive color 0. The strengthened parameter made the recursive step possible.

Now add edges beyond the tree construction. On a triangle, choosing colors 0 and 1 for two adjacent vertices forces the third to be 0 to differ from the second, but it then agrees with the first. The tree result therefore cannot provide the requested coloring for every graph. The new edge condition leads to a different construction or an obstruction, while the tree method retains its original use.