The Care and Feeding of Enders

Last revised 2001-02-28.

Definitions.

In a Sylver Coinage position, an end is a legal move that eliminates no other legal move. In a finite position (a position with g=1), t is always an end, being greater than all other legal moves. In a position S with g>1 the ends are just g times the ends of the position obtained by dividing S by g.

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 P-position. In short, every ender is an N-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.

Quiet enders may be characterized as those finite positions whose legal moves are antisymmetric to their illegal moves. More precisely, S is a quiet ender if and only if for any positive m and n such that m + n = t(S), exactly one of m and n is legal is S. This follows readily from the definition of a quiet ender. First, t is legal by definition and cannot be the sum of two illegal moves. Now suppose that m is legal and less than t. Then m eliminates t using m only once; that is, t = m + some combination of elements of S. By the rules of Sylver Coinage, any combination of elements of S is illegal in S. Thus n is illegal.

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) = mnmn. 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 mx1ny1 and mx2ny2, where y1 and y2 are positive. Applying Sylvester's Formula gives:

mx1ny1 + mx2ny2 = mnmn [*]

Reduce modulo m to obtain:

ny1ny2 = − n (mod m)

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

mx1 + mx2n(m + 1) = mnmn

which reduces to:

m(x1 + x2) = 2mnm

whence x1 + x2 = 2n − 1. But this is impossible because both x1 and x2 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 tn can be expressed as a sum with repetitions of elements of S; in other words, tn 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:

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

The Quiet End Theorem states that if m and n are coprime, then (S×m)n is a quiet ender if and only if Sn is. The original form of the Quiet End Theorem uses two multipliers, m1 and m2, and states that (S×m1)n is a quiet ender if and only if (S×m2)n is; but this is an immediate corollary of the statement above and is not significantly more useful. See Winning Ways for a visual proof of the 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 N, we deduce that {4,6} is P.

Long and Short Positions

An important consequence of the Quiet End Theorem is:

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 N, 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 n cannot be an ender at all.

Such positions S×p are called long. Short positions with g=2 are often P; 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 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

Enders are useful, especially quiet enders. With the Antisymmetry Principle, they are also easy to find.

Let S be a position with g=1. Let the pairs of distinct legal moves in S that sum to t be (x1,y1), (x2,y2), . . ., (xk,yk), with xi<yi for 1≤ik. Define E(S) as the position formed by adjoining y1, y2, . . ., yk 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 yi>t/2, if it eliminates t it does so quietly. That is, tyi must be illegal. But this value is xi, which is legal by hypothesis.

Suppose that yi eliminates some legal non-adjoined move z. Since z is not being adjoined, tz must be illegal. Again, yi>t/2, so it must eliminate z quietly, and zyi must be illegal. On the other hand, it is given that xi=tyi is legal. But tyi = (tz) + (zyi), 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 STE(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.


Back to the Sylver Coinage Page
Col. G. L. Sicherman [ HOME | MAIL ]