\documentclass[12pt]{article}

\usepackage{amsmath,amsthm,latexsym,amssymb}



\textwidth= 6.25in

\textheight= 9.0in

\topmargin = -10pt

\evensidemargin=10pt

\oddsidemargin=10pt

\headsep=25pt

\parskip=10pt

\font\smallit=cmti10

\font\smalltt=cmtt10

\font\smallrm=cmr9





%%\def\text{\rm}

%

\def\refeq#1{\if\workingver y(\ref{#1})-[[#1]]\else(\ref{#1})\fi}

\def\refth#1{\if\workingver y\ref{#1}-[[#1]]\else\ref{#1}\fi}

\def\mylabel#1{\if\workingver y\label{#1}{\bf\ \ [[#1]]\ \ }

\else\label{#1}\fi}

\def\mybibitem#1{\if\workingver y\bibitem{#1}{\bf\ \ [[#1]]\ \ }

\else\bibitem{#1}\fi}

%

%

%\def\institute#1{\gdef\@institute{#1}}

%

%\def\institutename{\par

% \begingroup

% \parskip=\z@

% \parindent=\z@

% \setcounter{@inst}{1}%

% \def\and{\par\stepcounter{@inst}%

% \noindent$^{\the@inst}$\enspace\ignorespaces}%

% \setbox0=\vbox{\def\thanks##1{}\@institute}%

% \ifnum\c@@inst=1\relax

% \else

%   \setcounter{footnote}{\c@@inst}%

%   \setcounter{@inst}{1}%

%   \noindent$^{\the@inst}$\enspace

% \fi

% \ignorespaces

% \@institute\par

% \endgroup}

%

%

\newtheorem{thm}{Theorem}

\newtheorem{lem}[thm]{Lemma}

\newtheorem{defn}[thm]{Definition}

\newtheorem{cor}[thm]{Corollary}

\newtheorem{prop}[thm]{Proposition}

\newtheorem{ex}[thm]{Example}

\newtheorem{algo}[thm]{Algorithm}

\newtheorem{rem}[thm]{Remark}

\newtheorem{conj}[thm]{Conjecture}

%

%\def\oarrow{{\mathrel{\longrightarrow\mkern-25mu\circ}\;\;}}

%

%

%\def\begeq#1{\begin{equation}\mylabel{#1}}

%\def\endeq{\end{equation}}

%

%\def\begalg{\begin{alg}}

%\def\endalg{\end{alg}}

%

%\def\implies{\;\Rightarrow\;}

%\def\leqs{\;\leq\;}

%\def\subsets{\;\subset\;}

%

%\newcounter{li}

%

%

%

\let\workingver=n

\newcommand{\bb}{\bar}

\newcommand{\hs }{\hspace{.6cm}}

\newcommand{\beq}{\begin{equation}}

%\newcommand{\gata}{\end{equation}}

\newcommand{\Z }{{\bf Z}_2^n}

%

%\textheight=21.2cm

%\textwidth=15.2cm

%\oddsidemargin=0.7cm

%\evensidemargin=0cm

%\topmargin=0cm



\font\tenrm=cmr10

\font\tensl=cmsl10

\font\ninerm=cmr9

\font\erm=cmr8

\def\sms{\small\scshape}







%%%%%%%%%%%%%%%%%%%%%%%

\def\eps{\epsilon}

\def\ga{\gamma}

\def\de{\delta}

\def\al{\alpha}

\def\be{\beta}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\def\b{\bar}

\def\st{\star}

\def\Mod{{\rm Mod}}

\def\dbl{\left[\left[}

\def\dbr{\right]\right]}

\def\Det{{\rm Det}}

\def\ZZ{{\bf Z}_2^n}

\def\Z{{\bf Z}_2}

\def\Zz{{\bf Z}_2^{n-1}}

\def\op{\oplus}

\def\Llr{\Longleftrightarrow}



%%%%%%%%%%%%%%%%%%%%%%%



\begin{document}



\begin{center}
{\bf COMPLY/CONSTRAIN GAMES OR GAMES WITH A MULLER TWIST}
\vskip 20pt
{\bf Furman Smith} and {\bf Pantelimon St\u anic\u a}\footnote{Also
associated with the {\em
Mathematical Institute
of the Romanian Academy}, Bucharest, Romania}\\
{\smallit Auburn University Montgomery, Department of Mathematics,\\
P.O.Box {\tenrm 244023},
Montgomery, AL {\tenrm 36124-4023}, USA}\\
{\smallit  \{furman,stanica\}@sciences.aum.edu}
\end{center}

\vskip 30pt
\centerline{\smallit Received: 7/16/02, Revised: 9/25/02, Accepted: 12/10/02, Published:
12/18/02 }

\vskip 30pt



\centerline{\bf Abstract}
\noindent
In this paper we call attention to a category
of combinatorial games, which we call {\em comply/constrain games} or {\em
games with a Muller twist}. We say that we put a {\em Muller twist} on a
familiar game if we modify that game so that each move in the familiar
game is followed by a
constraint on the next player's
move.
We solve {\em Odd-or-Even Nim},
which is a variant of {\em Nim}
with the Muller twist that each player specifies whether
their opponent's next removal is to be of an odd or even number
of objects,
solve a generalization of {\em Tall-or-Short Wyt Queens},
which puts a Muller twist on {\em Wyt Queens},
report some results for {\em Fibonacci-or-Not Nim},
which is a take-away game in which the possible constraints are that the
number removed be a
Fibonacci number or not,
and propose some other games,
such as {\em Nought-or-Cross}.





\pagestyle{myheadings}
\markright{\smalltt INTEGERS: \smallrm ELECTRONIC JOURNAL OF
COMBINATORIAL NUMBER THEORY \smalltt 2 (2002), \#G03\hfill}



\thispagestyle{empty}
\baselineskip=15pt
\vskip 30pt





%\baselineskip=2.04\baselineskip





%\noindent {\em $2000$ AMS Classification Numbers}: 11B37,11B39, 05A10,

%05A19



%\noindent {\em Keywords.} Binary Sequences, Fibonacci, Finite Sums,

%Generating Functions.



\section*{\normalsize  1. Motivation}
The game {\em Quarto$^{\circledR}$},
created by Blaise Muller
and published by Gigamic,
was one of the five Mensa Games
of the Year in 1993
and has received other international awards.
The sixteen game pieces show all combinations of size ({\em short} or {\em
tall}), shade
({\em light} or {\em dark}), solidity ({\em shell} or {\em filled}), and
shape ({\em circle} or {\em square}).
Two players take turns placing pieces on a four by four board and the
object is
to get four in a line with the same characteristic - all short, for
example. Only one piece can go
in a cell and, once placed, the pieces stay put.  Blaise
Muller's brilliant twist is that you choose the piece that
your opponent must place and they return
the favor after placing it.



We will say that we put a {\em Muller twist} on a familiar combinatorial game if we
modify that game so that
each player's move of game pieces in the familiar game is followed by that
player's
choice of a constraint, from a well defined set of constraints, on the
next player's move.
We will refer to such a game as a {\em comply/constrain game}.





Constraints are common in games.  If our opponent in {\em Tic-Tac-Toe}
\cite{MG1} takes the center
square, we cannot play there.  However, since that
constraint does not involve a choice after the physical move, we do not
consider
Tic-Tac-Toe in the comply/constrain category of games.



Nor would we call {\em Fibonacci Nim} (see \cite{BCG, MG9,Knuth_I}) a
comply/constrain game.
(It is  traditionally thought of as being played with a single pile
of beans, in which the first player
can take any number of beans provided they do not take them all. 
Thereafter the
players alternate with the constraint that no player can take more than
twice
the amount just taken by the previous player.)  Although the constraint
cannot be
deduced by a newcomer observing the pile of beans, the constraint is
strictly
determined by the previous physical move and thus is not in the
comply/constrain
category.





A position in a comply/constrain game consists of both a physical
configuration of game pieces and a
constraint which is not automatic from the current configuration or the
move which was made from the
previous configuration.



Muller's Quarto$^{\circledR}$ is the first comply/constrain game that we know of and we
know
of only a few others in the literature.



The second comply and constrain game that we have seen is
introduced
in the Nov-2001 issue of
{\it The College Mathematics Journal} as Problem 714.
The problem posers,
A. Holshouser and H. Reiter, called the game {\em Blocking Nim}.
The game is built on {\em Nim}, which is
reviewed in the next section of this paper.
Their modification involves a pile-specific restriction on the number that
might be removed from each pile.
A typical position might be
$(7\ not\ 3, 5\ not\ 2, 6\ not\ 6)$ which means that from the pile of 7 we
can take any number except
3, and we cannot take exactly $2$ from the pile of $5$, nor can we take
all of the pile of $6$.  One
of the many options for that position is
$(7\ not\ 7, 5\ not\ 5, 2\ not\ 1)$



The other comply and constrain games that we know of are due to the same energetic
pair, Holshouser and Reiter.  One game involves three piles with one
configuration blocked.
A typical position might be $(5,4,3)$ with the restriction that we cannot
present the configuration $(5,4,1)$.
The authors have completely solved
the three pile problem. Their paper \cite{HR_16}
mentions that the problem with a larger number of piles at the time of
writing is still unsolved.
Another paper \cite{HR_18} allows blocking several configurations with
a single pile.
After we submitted the original version of this paper, we
found another of their papers \cite{HR-BlockComb2}, in which
they consider a composite of subgames with blocking in each subgame.





\section*{\normalsize 2. Definitions}
If we present our opponent with certain positions
and play optimally after that, we are guaranteed to win.  Such positions
are called $\cal P$-positions, indicating that the previous player wins
if they
play optimally
for the remainder of the game \cite{BCG,G}.
If we are ever able to present to our
opponent a $\cal P$-position,
our opponent must present to us a non-$\cal P$-position and,
from there, we will be able to present a $\cal P$-position.



An option is a position that might occur while a move is the position that
does occur.
We will call an option $B$ of a position $A$ a {\em child} of $A$
and will refer to $A$ as a {\em parent} of $B$.



It is clear that two properties characterize the set of
$\cal P$-positions.  A subset $C$ of all possible game positions is the
set of $\cal P$-positions if
and only if it satisfies both of the following 
\vskip 5pt
\noindent
{\bf $\cal P$-Properties:} \vskip -5pt \noindent
{\em
$(P1)$  No position in $C$ has a child in $C$; in other words, no option
available to a position
\vskip -10pt 
\hskip 11pt in
 $C$ is an element of $C$.\\
$(P2)$  Every position not in $C$ has a child
in $C$; that is, every position not in $C$  has an
\vskip -10pt 
\hskip 11pt
 option
in $C$.
}



Obviously, as a special case of $(P2)$, the terminal positions are in $C$,
since they are childless positions.



The game of {\em Nim} involves piles of counters -- say piles of beans.
Players take turns removing beans.  Each
player in their turn must take a positive number of beans from one pile of
their choosing.
The first player that cannot move loses.



It is well known (see \cite{BCG,MG1,G}) that the $\cal P$-positions in Nim
are easily recognized.  Express the pile sizes in binary notation so
that each pile size has either
a zero or a one in each of the units place, the two's place, the four's
place, etc.  A position is a
$\cal P$-position in Nim if and only if those binary representations have
an even number of ones for each
power of two.  For example, three piles with 4, 8, and 12 beans have
binary representations
100, 1000, and 1100 so there are no one's in the units or twos place and
two ones in each of
the fours and eights place;  therefore three piles with 4, 8, and 12 beans
is a $\cal P$-position in Nim.
Succinctly put, the $\cal P$-positions of Nim are precisely those
positions for which the
nim-sum (binary sum without carry) of the pile sizes is zero.





\vskip 30pt



\section*{\normalsize 3. Odd-or-Even Nim }
In this section we put our first Muller twist on classical Nim,
introducing
 {\em Odd-or-Even Nim}:
The first
player in Odd-or-Even Nim specifies whether the second player is to take an
odd or an
even number of beans.  Each move after that consists of a comply phase and
a constrain phase.
In the comply phase, the player gets to choose the pile but must comply
with the
odd or even restriction on the number of beans removed.  In the constrain
phase, the player
specifies that the opponent must take an odd or even positive number of
beans on their next move.
A position in this game is of the form $(n_1,\ldots,n_s;even)$ or
$(n_1,\ldots,n_s;odd)$,
where $s$ is the number of piles, and $n_i$ is the size of the $i$-th pile.



\begin{thm}
The set of $\cal P$-positions for Odd-or-Even Nim is the set of positions
satisfying
one of the following conditions:\vskip -5pt
$(i)$  pile sizes nim-summing to one and constraint of even,\\
\indent $(ii)$ pile sizes nim-summing to zero and constraint of even, or\\
\indent $(iii)$ all pile sizes even and nim-summing to zero and constraint of odd.
\end{thm}



\begin{proof}
Denote by $C$ the set satisfying $(i),(ii),$ or $(iii)$ ($``C"$ for
``Candidate
set").  Let $C.i$ be
those elements of $C$ who earn membership by satisfying property $(i)$;
define the subsets
$C.ii$ and $C.iii$ in a similar manner.



We will show that $C$ satisfies both properties of $\cal P$-positions. 
For the
first property, $(P1)$, we will consider two cases -- first the children
of positions in $C.i$ and
$C.ii$ and then the children of $C.iii$.



To see that no child of a position in $C$ can be in $C$, note that the
nim-sum of every position in
$C$ is zero or one.  Any position in $C$ must have pile sizes such that we
have an even parity in the
twos place and the fours place and the eights place, etc.  If the
constraint is that an even number is to be removed, the parity must
be switched in at least one
of those places so no child of a position in $C.i$ or $C.ii$ can be in $C$.



Since each position in $C.iii$ involves all pile sizes even as well as a
constraint of odd and a
nim-sum of zero, we have all zeros in the units place and an even number
of zeros in the other places.
We must ``borrow" in order to remove an odd number.  This ``borrowing"
causes at least one parity
switch in the other places and thus makes a nim-sum of zero or one
impossible.  Therefore no
child of a position in $C.iii$ can be in $C$.



To prove $(P2)$, we will consider three cases  -- even constraint, odd
constraint with
nonzero nim-sum, odd constraint with zero nim-sum and at least one pile
size odd.



Consider being faced with a position with an even constraint that is not
in
$C$.  Its nim-sum
cannot be zero or one.  We can make be zero all of the column sums except
possibly the last.  We can
then constrain the next move to be even and present
a member of $C.i$ or $C.ii$.



Consider now being faced with a position with an odd constraint that is
not in $C$.  Then either
the nim-sum is nonzero or not all of the pile sizes are even.  In the case of the Nim-sum being
non-zero, we can make all places except perhaps the last have even parity
and
thus present a member of $C.i$ or $C.ii$.



The only type of position in the complement of $C$ which has not been
considered has an odd
constraint, a zero nim-sum, and at least one pile size odd.  If presented
with such a position,
we can remove a single bean from one of the odd sized piles and thus
produce a position with an
even parity in every place except possibly the last;  thus we can present
a position with a
nim-sum of zero or one and constrain their move to be even.  Therefore,
every position not in $C$ has a child in
$C$.



This proves that the elements of $C$ are the $\cal P$-positions.
\end{proof}



\section*{\normalsize 4. Fibonacci-or-Not Nim }
In Odd-or-Even Nim we partitioned the natural numbers into the
set of odds and its complement.  Any set of natural numbers yields a partition which yields such a
game. We considered sets determined by the range of
functions defined on the set of natural numbers with positive integer values;  the constraint set for
each game consisted of just two elements -- either the player must pick a
number in the range of $f$ or the player cannot.
We concentrated on functions whose values
have a unique representation for the set of natural numbers
as sums of values of $f$, which will always  happen if $f$ satisfies, for
instance $f(k+1)\leq 2f(k)$.



One example of {\em $f$-or-not Nim} that we studied
involves $f(n)=F_{n+1}$ where $F_{n}$ is the $n$-th Fibonacci number.
In particular, {\em One-Pile Fibonacci-or-Not Nim}
is a single pile take-away
game in which the
constraint is either to remove a Fibonacci
number of beans or to remove a non-Fibonacci number of beans.



One approach to finding $\cal P$-positions is similar to the Sieve of
Eratosthenes.  Consider the
terminal position of
having three beans and being constrained to take a non-Fibonacci number of
beans.  This
position, denoted by $(3; not)$, is clearly a $\cal P$-position and thus
any possible parent is a
non-$\cal P$-position.  We can immediately mark the following as
non-$\cal P$-positions:  $(4; Fib)$, $(5; Fib)$,
$(6; Fib)$, $(7; not)$, $(8; Fib)$, $(9; not)$, etc.  So we can start with
$0$ beans and sieve out
positions of each constraint (including $(144; Fib)$ and $(145; not)$);
then go to 1 bean (since $(1; Fib)$
had not been sieved out) and sieve out some more.  We continue with
increasing pile size.
Those positions not sieved out are $\cal P$-positions.



A similar approach looks at possible children rather than possible
parents. For example,
once we have the $\cal P$-positions for up to eleven beans, we can
determine that $(12; Fib)$
is a $\cal P$-position by verifying that none of its children are $\cal
P$-positions.



We list here the pile sizes up to 500 which, with the appropriate
constraints,
give a $\cal P$-position for Fibonacci-or-Not Nim.
This solves the game up to 500 beans.
It would be interesting if we could give some simple rule for determining
whether or
not $(n; Fib)$ was a $\cal P$-position for general $n$.
\\



\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}
  \hline
  % after \\: \hline or \cline{col1-col2} \cline{col3-col4} ...
  0   &1  &   2   & 3  & 12  & 18 &  27  &  38 &  42  &  49 &  53 & 60  &
64 & 71 \\
  \hline
75& 86  & 95 &  102 & 106 & 112 & 118 & 122  &128 & 132  & 148 & 154 & 158
& 165 \\
 \hline
172 & 176 & 190  &194 & 200 & 212 & 216 & 222 & 226 & 232 & 238  &242 
&248 & 252 \\
 \hline
258 & 264  &268  &274 & 278 & 284 & 288 & 294 & 300 & 306 & 310 & 317 
&324 &336  \\
 \hline
342 & 346 & 352  &362  & 368  &374 & 384 & 388 & 394 & 400 & 410  & 414 &
420 & 424 \\
 \hline
436 & 440 & 446 & 456  &460  & 466  &476 & 482 & 488 & 492 & 498 & & & \\
  \hline
\end{tabular}
\\



We list here a few winning positions in lexicographical order for
{\em Two-Pile Fibonacci-or-Not Nim}
with the understanding
that if $(n,p)$ is a winning position then $(p,n)$ is also a winning
position with the same constraint.
The only $\cal P$-positions with a constraint of
$``not-Fibonacci"$ up to $150\times 150$ are:

\[
\begin{tabular}{|c|c|c|c|c|c|c|}
  \hline
  % after \\: \hline or \cline{col1-col2} \cline{col3-col4} ...
 (0, 0) & (0, 1) & (0, 2) & (0, 3) & (1, 1) &  (1, 2) & (1, 3)\\
 \hline
(2, 2) & (2, 3) & (3, 3) & (4, 4) & (4, 5) & (4, 6)  & (4, 7) \\
\hline
(5, 5) & (5, 6) & (5, 7) & (6, 6) & (6, 7) & (7, 7) & (8, 8) \\
\hline
 (8, 9) & (8, 10) & (8, 11) & (9, 9) & (9, 10) & (9, 11) & (10, 10)\\
 \hline
 (10, 11) & (11, 11) & (12, 13) & (13, 13) & (13, 14) & (13, 15) & (14,
14)\\
 \hline
 (14, 15) & (15, 15) & (17, 22) & (18, 21) &  & &\\
\hline
\end{tabular}
\]
and the $\cal P$-positions with constraint $``Fibonacci"$ up to $20\times
50$ are:

\[
\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|c|}
  \hline
  % after \\: \hline or \cline{col1-col2} \cline{col3-col4} ...
 (0, 0) & (0, 12)& (0, 18) &(0, 27) &(0, 38) &(0, 42) &(0, 49) &(1, 17) &(1,
26)\\
  \hline
 (1, 32) &(1, 41) & (1, 48) & (2, 19)& (2, 25)& (2, 29) & (2, 39)& (2, 43)
&(3, 20)\\
  \hline
 (3, 30)& (3, 40) &(3, 44) &(3, 50)&(4, 4) & (4, 16) & (4, 22) &(4, 31) &(4,
42)  \\
  \hline
 (4, 46) &(5, 21)& (5, 32) &(5, 36) &(5, 47) &(6, 23)&(6, 29) &(6, 33)& (6,
43)  \\
  \hline
 (6, 49) &(7, 24) &(7, 30) &(7, 34) &(7, 44)& (7, 48) &(8, 8) &(8, 25)& (8,
35) \\
 \hline
 (8, 39)  &(9, 20)& (9, 27) & (9,  36)& (9, 47)& (10, 26)& (10, 33)& (10,
37)& (10, 49)\\
  \hline
 (11, 28) & (11, 34)& (11, 38)& (11, 48) &(12, 12) &(12, 19) & (12, 23)&
(12, 29)& (12, 35)\\
  \hline
 (12, 39)& (12, 45)& (13, 24) & (13, 30)& (13, 40)& (13, 44)& (13, 50) &
(14, 25) &(14, 31) \\
   \hline
  (14, 37) &(15, 32) &(15, 38) &(15, 42) &(16, 16)& (16, 22)& (16, 26) &(16,
33)& (16, 45) \\
  \hline
  (16, 49) &(17, 17) & (17, 21) &(17, 28) &(17, 40) &(17, 44) &(17, 50) &
(18, 18) &(18, 25) \\
  \hline
  (18, 35) &(18, 41) & (19, 19) &(19, 30) &(19, 39) &(20, 20) & (20, 26)
&(20, 36) &(20, 46)\\
  \hline
\end{tabular}
\]



It is natural to conjecture that the $\cal P$-positions with constraint
$``not-Fibonacci"$ involve relatively
few beans while
$\cal P$-positions with constraint $``Fibonacci"$ can involve arbitrarily
large numbers of beans.
There is an intriguing amount of
near-regularity in the $\cal P$-positions but Fibonacci-or-Not Nim has yet
to be solved.





\section*{\normalsize 5. Tall-or-Short Wyt Queens}
The game pieces in {\em Wyt Queens} all glide in a queenly manner to one
corner of the chessboard.
If they all glide to the northwest corner of the chess board then each
journey must be one of:
due north, due west, or due northwest along a diagonal.  The queens have the
ghost-like qualities
that they can pass through each other and several can occupy the same cell
at the same time.
Just as you would expect, each player in their turn, persuades the queen of
their choice to glide
a non-zero number of cells and the first player that cannot move loses.



It turns out that anyone who can play Nim well can quickly learn to play
Wyt Queens well.  A
queen on a certain cell is equivalent to a certain size pile in Nim, called
the {\em Sprague-Grundy value}. (Sprague-Grundy theory
is fully and beautifully
developed in {\em Winning Ways} \cite{BCG},
{\em Fair Game} \cite{G},
and {\em On Numbers and Games} \cite{JHC},
as well as some earlier sources.)
Once we determine the Sprague-Grundy values of the
various cells on the chessboard, we can apply the results of Nim theory  -- a
position is a $\cal P$-position if and only if the nim-sum of the
Sprague-Grundy values is zero.





%

% 0

%

A queen in the northwest corner is equivalent to a zero sized pile
since such a queen is in a terminal position;  thus, the Sprague-Grundy value of such a location is zero.



%

% 1

%

A game position of a queen in one of the two cells sharing a border
with that northwest corner
cell is equivalent to a nim pile with a single bean since the only option
from such a position is to
glide to a position which is equivalent to no beans.



%

% 2,2

%

Similarly, a game position of a single queen two cells below the northwest corner is
equivalent to two beans
since it has options equivalent to zero beans or one bean.  Another
position equivalent to two beans is the
location immediately
southeast of the northwest
corner since it has options of zero (glide like a bishop) and one (glide like a rook).





%

% reversible 0

%

The cell adjacent to the previous two cells that we have discussed is very interesting.
The only options are 1 and 2 so 0 is not an option from this cell.  However,
from any of its options, we can move to a zero cell.
 This is called a {\em non-terminal} zero position.



A non-terminal zero position acts just
like an empty pile of beans except that there might be a finite
number of moves, each of which can be ``reversed", until we reach a terminal
zero.



%

% 5

%

We can continue in this manner and assign an equivalent heap size to each of
the cells.  It
turns out that a single queen in the southeast corner of a standard eight by
eight chessboard
is equivalent to a nim heap of five beans.



The Sprague-Grundy value of a position in Wyt Queens is the Nim-sum
of the Sprague-Grundy values of the locations of the queens.
We have discussed six cells so far and the locations are equivalent to pile
sizes $0, 1, 2, 2, 0, 5$.
The
nim-sum expressed in binary is 100 and removing four from the pile of five will
produce a position
with a nim-sum of zero.   We know that we can do this since the Wyt Queen in the
southeast corner must be able to glide to some cell
with Sprague-Grundy value one because to have a value of five it
must have one as an option.



The game of {\em Tall-or-Short Wyt Queens} involves game pieces of two
heights -- say three tall and
five short Wyt Queens.  There are two elements of the constraint set --
``She who glides must be tall." and ``A short must glide.".



We can think of playing Tall-or-Short Wyt Queens as two subgames and, in our
turn, we are constrained
to make a single move in
two subgame specified by our opponent and
we are to constrain our opponent's next move to one of the two subgames.
You may prefer a
greater variety of queens, say blonds, redheads, etc., so our
theorem will concern $k$ subgames.





\begin{defn}
Given $k$ ordinary impartial games $G_1,\ldots,G_k$, the forced-subgame sum is the comply/constrain
variation where the constraint consists of forcing your opponent to play in a specific game.
\end{defn}



Since it is easily verified that the Sprague-Grundy values for the Wyt
Queens have the property that no
position with value one has only options with non-terminal zero Sprague-Grundy
values, we can use the
following theorem to play well the game of Tall-or-Short Queens.



\begin{thm}
If none of the subgames of $G_1,\ldots,G_k$ have a reachable position of
Sprague-Grundy value $1$ whose only options are non-terminal subgames of value
$0$, then the $\cal P$-positions in the forced-subgame sum of $G_1,\ldots,G_k$ all have the
constraint in a subgame of value $0$ and are of two types:\\
$(i)$  Positions in which the constraint is to play in a terminal game.\\
$(ii)$ Positions in which the total number of non-terminal subgames of value $0$ is odd, and there
are no terminal subgames.
\end{thm}



\begin{proof}
Let $C$ be the set of positions that the theorem claims forms the set of
$\cal P$-positions, and
let $C.i$ be the set of positions that are in $C$ by virtue of case
$(i)$ above and $C.ii$ be
the set of positions in $C$ in case $(ii)$ above.



The proof will involve four steps.  The first two, in which we will show
that $(P1)$ holds, are:  the children of positions in
$C.i$ cannot have a child in $C$,  nor can the children of $C.ii$.



Positions in $C.i$ are terminal, and thus have no children in $C$.



If we present a member of $C.ii$, the only children will have a nonzero
value for the subgame that
we constrained our opponent to.  The opponent will thus have to present a position with
an even number of
subgames with zero value.  None of those zero values are terminal.
Thus, positions
in $C.ii$ have no children in $C$.



In the remaining two steps, in which we show that $(P2)$ holds, we consider
the ways in which we could be presented
with a position in the complement of $C$:  Either we have a nonzero value in
the game that we are
constrained to or we have a non-terminal zero in that subgame and an odd
number of other zero values.



Assume that we are constrained to play in a subgame with a value 1.
Then we can move to a terminal 0, and constrain our opponent
to play in the same game. (This is why we needed
the assumption that no subgame has a value of one whose only children have
non-terminal zero values.)
If we are constrained to play in a subgame with a value $\not=1$,
we can either reply with a zero value in that subgame or to reply
with a nonzero value
in that subgame, in order to present an odd number of zero values.
In either case, we will reply constraining to a subgame with a
zero value.  If we
can reply with an terminal zero in any subgame, we should constrain to
that subgame; otherwise, we make that subgame be zero or not in order to present an odd number of
zeros.





If we are presented with a position in which we must play in a subgame with
a non-terminal zero value
and an odd number of other zero values, we should constrain to one of the odd number of zero valued
subgames.
\end{proof}



White Knights \cite{BCG} must always approach the northwest corner of the chessboard.
We cannot use the theorem above to play {\em Tall-or-Short White Knights}
since it is easily verified
that there are locations with value one whose only options are non-terminal
zeros.



In {\em Non-sovereign Wyt Queens} we point the queen just moved to face north or west or northwest.
The next player to move that queen must move in the direction that the queen is pointed.  This is not
a comply/constrain game since the constraint is not necessarily on the opponent's next move.
By the work of Holshouser and Reiter [12], Non-sovereign Wyt Queens can be solved by constructing a dictionary
of Sprague-Grundy values associated with each position, where a position is a pair of a cell and a
direction.



\section*{\normalsize 6. More Unsolved Games with a Muller Twist}
Any classical game where a move involves placing a piece of some type and attempting to
create some configuration can be given a Muller twist by constraining the piece type to be used.
For example, {\em Nought-or-Cross} is  Tic-Tac-Toe played on a three by three board \cite{BCG} with the
twist that we specify whether the opponent is to next place a nought or a cross;  the first to get three
in a line of the same symbol wins.   Similar examples are Tic-Tac-Toe on a 4 by 4 by 4 board \cite{MG10},
on other graphs [4, 7, 8], and Toe-Tac-Tic \cite{MG1}.



If we applied that particular Muller twist to Chess, each player would specify the color of
the piece to be moved next.  If I tell you to move a white piece and you put either king in
checkmate, then you win by constraining me to move that king.



Another type of Muller twist on Chess would keep the concept of ownership of the pieces but
would put a constraint on the color of the next cell a move is made to.  In Dots and Boxes
\cite{BCG} we might constrain the first line of the next move to be vertical or horizontal.  Moves
in Checkers could be constrained so that the first piece movement of a turn be slanted left or slanted right.



Recall that Muller’s Quarto$^{\circledR}$ pieces have four attributes, such as height, and each attribute
has two values, such as short or tall.  Each of the sixteen Quarto$^{\circledR}$ pieces could be a Wyt
Queen on an eight by eight chessboard, with one of the possible constraints being
``She who glides must be square.";  seven other constraints would be based on other values of Quarto$^{\circledR}$
attributes (short, tall, round,...).
It is easier to name such a game {\em Quarto$^{\circledR}$ Value Wyt Queens}
than to solve it.


\noindent
{\bf Acknowledgement.}
The authors would like to thank the referee for his/her careful reading of our paper,
and for the insightful comments, which significantly improved the paper.



\begin{thebibliography}{99}

\footnotesize

\bibitem{BCG} E.R. Berlekamp, J.H. Conway, R.K. Guy,
{\em Winning Ways},
Academic Press, 1982.
(The second edition, to consist of four volumes, is in publication.)



\bibitem{JHC} John Horton Conway
{\em On Numbers and Games},
A K Peters, 2001 (2nd edition).



\bibitem{MG1} M. Gardner,
{\em Scientific American Book of Puzzles and Games},
Simon and Schuster, 1959, reissued as
{\em Hexaflexagons and Other Mathematical Diversions},
University of Chicago Press, 1988.



\bibitem{MG3} M. Gardner,
{\em New Mathematical Diversions from Scientific American},
Simon and Schuster, 1966.



\bibitem{MG9} M. Gardner,
{\em Mathematical Circus:  More Games, Puzzles, Paradoxes, \&
Other Mathematical entertainments from Scientific American},
Alfred A. Knopf, 1968.



\bibitem{MG10} M. Gardner,
{\em Wheels, Life, and Other Mathematical Amusements},
W. H. Freeman, 1983.



\bibitem{MG11} M. Gardner,
{\em Knotted Doughnuts and Other Mathematical Entertainments},
W. H. Freeman, 1986.



\bibitem{MG14} M. Gardner,
{\em Fractal Music, Hypercards, and More ...},
W. H. Freeman, 1992.



\bibitem{G} R. Guy,
{\em Fair Game: How to play impartial combinatorial games},
COMAP, Arlington, Massachusetts, 1989.



\bibitem{HR_16} A. Holshouser, H. Reiter,
{\em Three Pile Nim with Blocking},
submitted for publication, available at
www.math.uncc.edu/pre\-print/2002/$2002\_16$.pdf.



\bibitem{HR_18} A. Holshouser, H. Reiter,
{\em Dynamic One-Pile Blocking Nim},
submitted for publication, available at
http://www.math.uncc.edu/preprint/2002/$2002\_18$.pdf



\bibitem{HR-BlockComb2} A. Holshouser, H. Reiter,
{\em Blocking Combinatorial Games},
submitted for publication, available at
http://www.math.uncc.edu/\~\/hbreiter/BlockComb2.pdf



%## Knuth is still a great reference for Fibonacci Nim.###

\bibitem{Knuth_I} Donald E. Knuth,
{\em The Art of Computer Programming}, Vol. I:
{\em Fundamental Algorithms} (2nd ed.), 1973.



\end{thebibliography}



\end{document}

