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

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.

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*_{1} −
*ny*_{1}
and *mx*_{2} − *ny*_{2},
where *y*_{1}
and *y*_{2} are positive.
Applying Sylvester's Formula gives:

*mx*_{1} − *ny*_{1} +
*mx*_{2} − *ny*_{2} =
*mn* − *m* − *n* [*]

Reduce modulo *m* to obtain:

− *ny*_{1} − *ny*_{2} =
− *n* (mod *m*)

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

*mx*_{1} + *mx*_{2}
− *n*(*m* + 1) =
*mn* − *m* − *n*

which reduces to:

*m*(*x*_{1} + *x*_{2})
= 2*mn* − *m*

whence *x*_{1} + *x*_{2} = 2*n* − 1.
But this is impossible because both
*x*_{1} and *x*_{2}
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.

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**.

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*) < 2*n*,
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.

Let *S* be a position with *g*=1.
Let the pairs of distinct legal moves in *S* that sum to *t* be
(*x*_{1},*y*_{1}),
(*x*_{2},*y*_{2}), . . .,
(*x*_{k},*y*_{k}),
with *x*_{i}<*y*_{i}
for 1≤*i*≤*k*.
Define *E*(*S*) as the position formed by adjoining
*y*_{1}, *y*_{2}, . . .,
*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.

Back to the Sylver Coinage Page

Col. G. L. Sicherman [ HOME | MAIL ]