The Care and Feeding of Enders

• Definitions.
• The Antisymmetry Principle.
• The Quiet End Theorem.
• Long and Short Positions.
• The Enclosure Function.

Definitions.

An ender is a finite position with just one end (which must be t). An ender with a legal move other than 1 must have a win for the first player. If t does not win in S, then the second player can win by answering it with some other move u. Then the first player can win in the original position by playing u, since Su = Stu which is a 𝓟-position. In short, every ender is an 𝓝-position except {2,3}.

A quiet ender is an ender in which every move u less than t eliminates t, using u just once. The standard counterexample is {4,5,7}. Here t=6, and the other legal moves are 1, 2, and 3. They all eliminate 6 in {4,5,7}, so {4,5,7} is an ender. In particular, the move 3 in {4,5,7} eliminates 6, but only by using two 3's. Thus {4,5,7} is not a quiet ender.

The Antisymmetry Principle.

It follows immediately from the Antisymmetry Principle that if S is a quiet ender, t(S) must be odd. Otherwise we should have t = n + n, where n must be both legal and illegal.

An intermediate result of Hutchings's Theorem is that if m and n are coprime, the position {m,n} is an ender. The Antisymmetry Principle can be used to prove this stronger result:

If m and n are coprime, then {m,n} is a quiet ender.

This can probably be proved graphically. Here is a conventional proof.

It is known from number theory that if m and n are coprime and greater than 1, then every integer can be expressed in the form mx + ny for some integers x and y. Moreover, every integer can be expressed in this form uniquely under the condition that 0 ≤ x < n.

Let S = {m, n}. By Sylvester's Formula, t(S) = mn − m − n. Any illegal move in S can be expressed as mx + ny, where x and y are nonnegative. Here x must also be less than n, since mn is strictly greater than t. Moreover, every move of the form mx + ny with x and y nonnegative is illegal. This gives us a characterization of the legal moves in S:

For k such that 0 < k < t, let k be represented as mx + ny where 0 ≤ x < n. Then k is a legal move in S if and only if y is negative.

To show that S is a quiet ender, suppose that t were the sum of two legal moves mx₁ − ny₁ and mx₂ − ny₂, where y₁ and y₂ are positive. Applying Sylvester's Formula gives:

mx₁ − ny₁ + mx₂ − ny₂ = mn − m − n [*]

Reduce modulo m to obtain:

− ny₁ − ny₂ = − n (mod m)

Since m and n are coprime, we conclude that y₁ + y₂ is congruent to 1 modulo m. Since y₁ and y₂ are positive and less than m, the only possible value for y₁ + y₂ in this congruence class is m+1. Substituting in [*] gives:

mx₁ + mx₂ − n(m + 1) = mn − m − n

which reduces to:

m(x₁ + x₂) = 2mn − m

whence x₁ + x₂ = 2n − 1. But this is impossible because both x₁ and x₂ lie in the range from 0 to n−1.

Slightly weakened, the Antisymmetry Principle can be applied to all enders:

Let S be an ender. For any numbers m and n, if m+n=t(S) and m<n, then exactly one of m, n is a legal move in S.

As before, m and n cannot both be illegal, for then t=m+n would be illegal. It remains to show that m and n cannot both be legal. Suppose that n is legal. S is an ender, so n eliminates t. Since m<n, n must exceed t/2. Thus n must eliminate t quietly; that is, with a single instance of n. This means that t−n can be expressed as a sum with repetitions of elements of S; in other words, t−n is illegal. Thus m is illegal.

The Weak Antisymmetry Principle is distinguished by the clause m<n. If t is odd, one of m, n must be less than the other, so the Weak Antisymmetry Principle is no weaker than the original. But if t is even, we may have m=n=t/2. Then S is an ender, seeing that t/2 eliminates t; but it is not a quiet ender.

To summarize:

• S is an ender if and only if S satisfies the Weak Antisymmetry Principle.
• An ender S is a quiet ender if and only if t(S) is odd.

This furnishes an easy proof of our earlier result that if g(m,n)=1, then {m,n} is a quiet ender. Hutchings's Theorem shows that {m,n} is an ender, and t=(m−1)(n−1)−1 must be odd because m and n cannot both be even.

The Quiet End Theorem

In the Quiet End Theorem the move n need not be legal in S, which makes the theorem especially useful. For example, let S = {2,3} and m=2, so S×m = {4,6}. S is already a quiet ender. The theorem holds for illegal values of n that are coprime with 2: 5, 7, 9, ..., which means that the positions {4,6,5}, {4,6,7}, {4,6,9}, ... are all quiet enders. And since quiet enders are 𝓝, we deduce that {4,6} is 𝓟.

Long and Short Positions

If S is a quiet ender and p is a prime, then all sufficiently large moves in S×p produce quiet enders.

Such positions S×p are called short. Quiet enders are 𝓝, so sufficiently large moves in a short position cannot win. This is easy to prove. If S is a quiet ender, it must have g=1, so every sufficiently large move n is illegal and leaves S unchanged. Thus Sn is a quiet ender. By the Quiet End Theorem, so is (S×p)n.

A strong converse result holds:

If S is not a quiet ender and p is a prime, then all sufficiently large moves in S×p produce non-enders.

Applying the Quiet End Theorem similarly, we know that for sufficiently large n, (S×p)n is not a quiet ender. When n is large enough that t((S×p)n) < 2n, then (S×p)n cannot be an ender at all.

Such positions S×p are called long. Short positions with g=2 are often 𝓟; long ones hardly ever are. For prime values of g greater than 2, little is known. When g=2 the recursion can be computed by a finite-state automaton; for higher values of g it cannot.

Much computing may be needed to find a winning move in a long position with g=2. For example, {4,15,17} is not a quiet ender, so {8,30,34} is long. Its unique winning move is 49337.

The Enclosure Function

Let S be a position with g=1. Let the pairs of distinct legal moves in S that sum to t be (x₁,y₁), (x₂,y₂), . . ., (x_k,y_k), with x_i<y_i for 1≤i≤k. Define E(S) as the position formed by adjoining y₁, y₂, . . ., y_k to S. Then E(S) is an ender.

To prove this, it suffices to show that each adjoined move y[i] does not eliminate t and does not eliminate any legal non-adjoined move. Since y_i>t/2, if it eliminates t it does so quietly. That is, t−y_i must be illegal. But this value is x_i, which is legal by hypothesis.

Suppose that y_i eliminates some legal non-adjoined move z. Since z is not being adjoined, t−z must be illegal. Again, y_i>t/2, so it must eliminate z quietly, and z−y_i must be illegal. On the other hand, it is given that x_i=t−y_i is legal. But t−y_i = (t−z) + (z−y_i), so a legal move is the sum of two illegal moves. This is absurd.

The function E is called the enclosure. It can be seen to preserve the value of t. The enclosure of a position is minimal in the following sense:

Let S be a position with g=1. If T is an ender with S≤T≤E(S), then T=E(S).

However, E(S) is not minimum (uniquely minimal). For example, let S={5,6,8,9}. Then t=7, and the only legal antisymmetric pair is (3,4). We form E(S) by adjoining 4 to obtain {4,5,6}; but we can instead adjoin 3 to obtain {3,5}. This is likewise an ender with t=7.

For another example of enclosure, let S={7,11,13,15}; then t(S)=23. The legal moves in S are 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 16, 17, 19, 23. Two pairs violate antisymmetry: 19+4=23 and 17+6=23. Adjoining 19 and 17 to S produces E(S) = {7,11,13,15,17,19}, which is an ender. Since t is odd, E(S) is a quiet ender.

Like the t function, the E function can be extended to positions with g>1. Divide the position by g, take the enclosure, and multiply g back in.