Int. J. Communications, Network and System Sciences, 2010, 3, 793-800
doi: 10.4236/ijcns.2010.310106 Published Online October 2010 (http://www.SciRP.org/journal/ijcns)
Winning Strategies and Complexity of Nim-Type
Computer Game on Plane*
Boris S. Verkhovsky
Computer Science Department, College of Computing Sciences
New Jersey Institute of Techno logy, Newark, USA
Received June 10, 2010; revised July 17, 2010; accepted August 22, 2010
Abstract
A Nim-type computer game of strategy on plane is described in this paper. It is demonstrated that winning
strategies of this two-person game are determined by a system of equations with two unknown integer se-
quences. Properties of winning points/states are discussed and an O(loglogn) algorithm for the winning states
is provided. Two varieties of the Game are also introduced and their winning strategies are analyzed.
Keywords: Nim-type Game, Two-person Strategy Game, Winning Strategies, Newton Algorithm, Fibonacci
Numbers
1. Introduction
A Nim game is probably one of the most ancient of all
known games. There are several varieties of Nim: cate-
gorical games in which no draw is possible; futile games
which permit a tie (draw); Grundy’s game is a special
type of Nim. The game is played by the following rules:
given a heap of size n, two players alternately select a
sub-heap and divide it into two unequal parts. A player
loses if he or she cannot make a legal move. The Misere
form of Nim is a version in which the player taking the
last piece is the loser, [1].
In Fibonacci Nim, two players deal with a pile of n
stones, where n>1. The first player may remove any
number of stones, provided that at least one stone is left.
Players alternate moves under the condition that if one
player removed x stones, then another one may remove
at most 2x stones. Some of them are described in [1-5].
Several years ago the author of this paper introduced a
Nim game with a heap of N stones, where each player is
allowed to take at most m stones, provided that he/she
does not repeat the last move of her/his opponent (“do
not be a copycat”). The player taking the last stone is the
winner. However, a player loses if he/she cannot make a
feasible move. Winning strategies for an arbitrary m>1
were provided by the author of this paper and imple-
mented in [6] an d [7] by his graduate students.
In the late 1980’s the author also introduced a variety
of the Nim-game that is discussed in this paper. In the
paper we study properties of winning points, provide an
algorithm for direct computation of winning points and
analyze its complexity. It is demonstrated that the algo-
rithm has O(loglogn) time complexity and does not re-
quire any storage, save a couple of numbers that are
pre-computed at the beginning of the game. Preliminary
results of this paper are published in [15].
2. Two-player Game on Plane
1) The Game starts after two distinct non-negative inte-
gers


00
,SL are selected randomly; here.
0
1pS

< ;; (1)
00
qS L0 :;:SSLL
0
Remark 1: In the following discussion (S, L) is a point
on a two-dimensional plane with integer coordinates; all
further points are located in the positive quadrant of the
plane; p and q determine a “level” of the Game. It is as-
sumed that 0

S <L holds, otherwise we swap the co-
ordinates.
2) Three types of moves that allowed are: horizontal,
vertical and diagonal.
The players on their move may decrease either
a). The first coordinate on an integer t, (S, L)(S – t, L),
{horizontal move, h-move, for short} or
b). The second coordinate on an integer u, *© Boris S. Verkhovsky April, 2001

794 B. VERKHOVSKY
(S, L)(S, L – u), {vertical move, v-mo ve, for short} or
c). Both coordinates on the same integer x,
(S, L) (S – x, L – x), {diagonal move , d-move, for short}; 
The first player that reaches (0,0)-point on her/his
move is the winner of the Game. An analogous Nim
game was introduced by Wythoff [14]. Whytoff’ game is
played with two heaps of coun ters: a player is allowed to
take any number from either heap or the same number
from both. The player taking the last counter wins.
As in every two-person game with complete informa-
tion, this Game has a winning strategy for one of the
players [8-10]. In the following discussion we consider
that a Human (Hugo) plays against a Computer (Cora).
All points can be divided onto two classes: winning
points for Cora and losing points for Cora. It is clear that
a winning point for Cora is a losing point for Hugo, and
vice versa.
Definition 1: We will say that the Game is in a win-
ning state if after Cora’s move it is in a winning point.
Let’s denote Cora’s winning states as, for.
Here = (0, 0). n
w0n
0
Example 1: The 1= (1, 2) point is a Cora’s winning
point, because Hugo cannot reach 0= (0, 0) point on
his move. The 2= (3, 5) is another winning point for
Cora, because on his move Hugo cannot reach either
= (0,0) point or = (1,2) point.
ww
w
w
w
0
w1
On the other hand, after any move by Hugo, Cora
reaches either (0,0) or (1,2).
3. Seven Properties of Winning Points
P1. It is easy to see that if (c,d) is a winning point, then
(d,c) is also a winning point.
P2. With exception of the (0 ,0)-point, in all other win-
ning points . Indeed, let (c,c) be a winning point
for Cora. Then Hugo can reach the (0,0)-point using a
diagonal move, {via subtracting the same y = c from
both coordinates}.
cd
P3. If the Game is in a winning point w after Cora’s
move, then there is no move by which Hugo can reach
another winning state . On the other hand, if the Ga me
is in a losing point l, then there exists at least one move
that transforms the Game into a winning state. For ex-
ample, if after Hugo’s move the Game is in the state (7,
9), then there are two winning moves for Cora: (4,7) and
(3,5).
w
In general, let W be a set of all winning points and L
be a set of all losing points. Then after one move the
Game is transformed from W to L. However, if the Game
is in L, then there exists at least one move that transforms
the game into W. Formally it means that, if (,)SL W

,
then for any positive integer u, or
(,)L WSu
(, )SL uW

 or (,)SuLu W


k
w,
kk
cd
ii kk
dcdc
.
P4. Proposition 1: There are no two winning points
= () and = () such that
i
w,
ii
cd
r

 (2)
where r is an integer.
Proof: Let's assume that for i < k Equation (2) holds
and i :k vdd


i
w
i
w
,
ii
cd
Then after Cora’s move Hugo can
reach via a diagonal move, i.e., by subtracting from
both coordinates the same integer v.
k
w
P5. Let and be two distinct winning points.
Then all , are distinct integers, otherwise
Hugo would be able to transform the Game into another
winning state.
k
w
,
kk
cd

,SL
nn
dcn
P6. Proposition 2: Let . Then for every
n=1,2,…holds W


)
m:
. (3)
Proof: Let’s assume that there exists at least one win-
ning point , for which , and m is
the smallest integer; and let
(,
m
cd mm dcm
mm
s
dc
)
.
Consider(,
s
s: if s < m, then since by
assumption m is the smallest.
cd ss dcs
Therefore, mm ss dcsdc


ms
c,
or ms
ddc


ms
dc c
.
Let :zd
ms


)
. Then there is a diagonal
move that transforms one winning point into
another winning point(, (, )
mm
cd
s
s
cd , which contradicts with
the definition of a winning point. Therefore, 1sm


is impossible.
Let’s now assume that . 1sm
1
mk
dd Observe that

, otherwise for k1m


.
km
cc
1
m
d
Consider Hugo’s move(, , 1)
mm
cd
m
cm where


mm
cd

1)
. But in this case Cora cannot
make either a horizontal move or a diagonal move that
transforms the Game into a winning state. The latter im-
plies that (,

is a winning state, which in its
turn contradicts the earlier assumption that is
the winning state. Q.E.D.
(, )
mm
cd
P7. Theorem 1: {Fundamental property of the win-
ning point s}:
a) Let 0 1x2;

 and for all 0k



2
:1/2
kk k
xx x

1
1


k

; (4)
b) Let limGx
k

;
c) (S, L) is a winning point if


SLSG



 (5)

B. VERKHOVSKY
795
StepL6: :
nn
ban

.
For the sake of simplicity of further discussion, we
assume that in every point (c,d) c<d. Then the conditions (9)-(11) also hold for k = n. Q.E.D.
Applying the Steps L1-L6, we sequentially generate
the winning points
4. Game in Progress: An Example W={(1,2); (3,5); (4,7); (6,10); (8,13); (9,15); (11,18);
(12,20); (14,23); (16,26); (17,28); (19,31); (21,34);
(22,36); (24,39); (25,41); (27,44);…},
Let (S0,L0) = (29,51) be a randomly generated initial point;
Hugo makes the 1st move; in italics are shown Hugo’s
moves; in bold are Cora’s winning points Table 1. i.e.,


17 17
,ab= (27,44).
Therefore from the StepL3 J = {11, 12, 13, 14, 15, 16,
17}, and u = 29.
5. System of Equations with Infinite Sequ ences Then


18 18
,ab = (29,47).
Proposition 3: 1). Let A:={n a}; B:={n b} be monotone
increasing sequences of positive integers; here 11a

and n = 1,2,…;
6. Alternative Formulation of L1-L6 Algo-
rithm
2). Let the sequences A and B satisfy the following
system of equations: W1:
BA (6)
BAN (7)
BAN (8)
where in (7) ={ , BA}
nn
ba
i.e. is a sequence of pair-wise differences of
corresponding elements of B and A, and N is the set of all
natural numbers {1,2,3,…}. Then the system of Equa-
tions (6)-(8) with unknown sequences A and B has a so-
lution.
BA
Proof {by induction}: The following algorithm is a
constructive proof that a solution of (6)-(8) exists.
Indeed, the sequences A={ n
can be itera-
tively generated using an analogue of the Sieve of
Eratosthenes:
};{ }
n
aBb
StepL1: ;

11
,:(1,2ab 
:{A
)
1
StepL2: Let };
1k
..,b12 1
112 1k be sequences such that for every
k<n the following conditions hold:
,,..,
k
aaa


:
k
B

,,bb
12
.. k aaa

;
12
.. k bb b

1

(9)
11kk
AB

 (10)
and for every 11ik 
ii
ba i (11)
StepL3: Let J = {j: ;
1
StepL4: Compute an integer u := minx, where x >
1}
jn
ba


1n
a

and for all x; iJ:ai b
StepL5: u;
n
1:1;a

1:2;c

1:1;j

W2: for n=1,2,… do
1: n
a1;
n
c
W3: if 11
n
nj
aa

n


: then 1n c

1;cn

1n:j

;
n
j
else 1:
n
c2;
n
c


1:
n
j1;
n
j

Here, n stands for the largest index k of k that
was used in , and n stands for the largest number
of the set {1,2,...,k} which we cover for
j b
{}
n
acand
j
j
ab for
jn

[11].
7. Sequences A, B and Winning Points
Theorem 2: For every integer 1n


:,
nnn
wab (12)
Proof: The following sequence of steps is a construc-
tive proof of Th eorem1. Indeed, let
:mLS

 (13)
T1. If m Sa

, then by (3), (7) and (13) m bL

;
{Hugo is now in the winning point}.
T2. If m, then Cora selects y := S – am; S := S – y
and L := L – y; since S > am implies that L > bm. Indeed
Sa
ma
mm
LS mb


Sa
.
T3. {If m

, then Cora finds either an index k < m
such that k
aS

or an index i < m such that i bS

}.
T3a. If there exists an integer k < m such that k
aS

,
then we select :k
Lb

; {both m and k SaaS

imply that k < m and k. Indeed, an assumption that
leads to a contradiction, because implies
that S <
Lb
kmmk
m
aa
k

, but k aS

}.
Table1
Player Hugo Cora Hugo Cora Hugo Cora
Examples of moves (23,51) (14,23) (6,15) (6,10) (4,6) (3,5)
Type of move h-move v-move d-move v-move v-move d-move

B. VERKHOVSKY
796
T3b. If there exists an integer i < t such that i bS

,
then we assign ; ; {since implies
that : }, [6].
:LS
ii
ab:i
Sa
SL i
bS
i
aL
8. Iterative Algorithm and its Complexity
In applications for computer games, an iterative compu-
tation of n a for a large n is time consuming,
since its time complexity T(n) and space complexities
S(n) are both of order O(n). For instance, if ,
then we need to generate and store one trillion pairs of
integers. A brief analysis shows that this is well beyond
of current size of memory for PC. A more efficient algo-
rithm is described below.
and
n
b
)
n
t
t
12
10n
9. Direct Computation of an and bn
To decrease the complexity of computation of an and bn
and avoid excessive storage, let's find a closed-form ex-
pression for:= v(n). Then from (11)
n
a
:
n
bv(n)+n (14)
Conjecture 1: (prope rties of winnin g points):
C1. ; /(
m
amzom
and (15) lim /
m
mamz  
where z is a constant.
C2. For every integer 1n
n
anz

(16)
The property (16) and the asymptotic behavior (15)
are observed in numerous computer experiments.
Conjecture 2: For large n
/
n
ba= z + o(n) (17)
Remark 2: The Conjecture 2 is also based on extensive
computer experiments.
Theorem 3: Conjecture 1 implies that z is an irrational
number.
Proof: An assumption that z is a rational number leads
to contradiction. Assume that z = q/s, where both q and s
are relatively prime integers. Then there exis ts an infinite
number of pairs and such that =. Indeed,
select n
ar bn ar b
n := (q+s)st and r := qst (18)
Then for the integer t = 1,2,3,… it follows from (16)
and (14) that

n
aqsq (19)
and , (20)
2
r
bqtqs
which is a violation of the conditions (6) and (10).
Conjecture 3: z=g+1, where g is a golden ratio,
i.e.,


51/2g (21)
The property (21) is observed in numerous computer
experiments. It plausibility follows from the following:
Since for a large n = nz + o(n)
n
a
and = (z+1)n + o(n) (22)
n
b
then it follows from (17) and (22) that
/
n
ba
n

(z+1)/zz (23)
Then for large n's, z is a positive solution of the equa-
tion. 210xx

 (24)
i.e., z

(51

)/2, {the value of the golden ratio +1}.
Let the Game be in the state (S, L) after Hugo’s move
and let
m := (13). LS
Then the Game is implicitly in one of five states
{where by convention holds that S < L}:
A. (S, L) = (), {the game is in a winning state
for Hugo}; ,
mm
ab
B. (S, L) = () , where ; ,
ij
aa
,abij C. (S, L) = (); where either or ;
ij
,ba ijij
D. (S, L) = (),
ij ij

;
E. (S, L) = (), ,bb
ij ij

.
However, from th e condition (11) alone we do not know
yet in which of the states A, B, C, D or E the Gam e is.
10. Algorithm for Winning Points (AWP)
A1: Let m := LS

;
A2: Using (16) and (21), compute ;
m
if m
a
aS

then by (11) ; {Hugo is now in the
winning state }; m
bL
m
w
a A3: if then do y :=; S :=
m
Sm SaSy

and
L := Ly

;
A4: if there exists an integer k < m such that k aS

then :;
k
Lb

else find an integer i < m such that ;
i
bS:LS

;
:i Sa

.
11. Validation of AWP
V1. In A3, S > am implies that L > bm.
Then mm LSmamb

 
Sa ; V2. If m

, then there exists either an integer k < m
such that k aS

or an integer i < m such that i bS

;
V3. Both m Sa

and k imply that k < m and
k. Indeed, an assumption that leads to a
contradiction, because
aS
mk
Lbkm

implies that S<mk aa

,
but k
aS

;

B. VERKHOVSKY
797
V4. In A4, implies that . Hence
. i
bS
S
i
aL
ii
abSL
Example 2 {case m}: Let the Game be in the
state (S, L) = (19, 26) after the Hugo’s move.
a
Because m = 26 –19 = 7, compu te =11
and 18. 7
a7( 1)g


7
Since 11 < 19 and 18 < 26, then Cora moves
b
S := S – m = S – 7 and L := L – m = L – 7;
Example 3 {case}: Let now after Hugo’s move
(S, L) = (15, 32). m
Sa
Since m = 32–15 =17, compute =27.
17
Since 17 , but 15 = , then Cora’s move is
L := 15 and S := L – 6 = 9.
a17( 1)g


15 a6 b
Example 4: {case}: Let (S, L) = (14, 29) after
Hugo’s move. m
Sa
Since m = 15, compute 15 a

15( 1)g


=24.
Since , but 14 =, then Cora moves
15
L := 29 – 6 = 23.
14ab9 a
9
Example 5: {casem}: Then , and the
game is in the winning state for Hugo.
aSm
bL
12. Fibonacci Properties of Winning Points
1. If n is an odd Fibonacci number, i.e., if 21k nF


,
then
n
a=2k
F
(25)
2. If n is an even Fibonacci number, i.e., if 2k nF

,
then
n
a= (26)
21 1 k
F
Indeed, ;
357 9
3; 8;21; 55
FFF F
aaa a 
1;4; 12;aaa 33a
But .
24 6
FF F8 F
13. Solution of Equation with Un known Index
On the step A4 of the algorithm we must solve either
equation k or i in order to respectively
determine the indices k or i. In order to determine the
indices we must solve either the equation
aSbS
k
aS (27)
or the equation
i
bS (28)
This can be done by using (16)
k
a==S (29) (1)kg

 
S
I 1) Find the smallest integer satisfying the ine-
quality kg > S; if then
*
k
*
kg S



*
k=; ; (30) k*
k
a
I 2) If is the smallest integer satisfying the ine-
quality (g+1) > S
*
i
*
i
then
i = and (31)
*
i*
i
bS
If (16) has an integer solution, then from (29) we find
the smallest integer k = satisfying the inequality
*
k
*
k(g+1)>S (32)
Otherwise, {if (1)kg



S} we solve the equation
i
bS

.
Then from (1 4) and (29)
i
b

(1)ig



+ i = S (33)
Example 6: Find an integer index k such that
102
k
a

. Then * k

64 is the smallest integer for which
holds
*
k102/(g+1) {see (29)}.
14. Required Accuracy for g
It is assumed that in the Examples 3-6 and 8 we know the
exact value of an irrational number g. However, to find
an integer solution of (17) for an arbitrary large index k
or i we must compute g with a high precision. Let
2
12
/10/10 ../10..
n
n
gd dd

 (34)
where is the i-th decimal digit of g
i
d
and g(t):= =
10 /10
tt
g


2
/10 /10dd
12
.. /10t
t
d (35)
i.e., g(t) contains only the first t decimal digits of g.
Theorem 4: Let 10k n

. an = S (36)
Then for all also holds that kt


:
t
n
angt



= S. (37)
15. O(loglogn) Time Complexity for Win-
ning Strategies
It is easy to verify that a positive root of (24) can be
computed using a Newton iterative process



2
1:1/2 rr r
xxx
1

 ,
Where
0:1.618x

(38)
The process (38) has the following properties:
a).It converges to (15)/2, i.e., for large r
r
x

(15)/2+ r

, (39)
where r

is a degree of accuracy ( error) after r iterati on s.

798 B. VERKHOVSKY
b). The error r

satisfies the inequality
2
00
r
r
r
x
g   ,
i.e., it has a quadratic rate of convergence, and
3
00.001 10



, [12]. (40)
Then from the inequality 32 10 10
rk



32
rk

n


we derive that
(41)
Thus

2
log/ 3rk



210 1010
loglog/3log logn





(42)
The inequalities (42) are derived from (36), (40) and
(41). Then from analysis of (37) it follows that the time
complexity T(n) for solution of (16) is equal
T(n)=O(loglogn).
The Table 2 shows how many Newton iterations r(n)
are required to compute as a function of n.
n
In addition, we do not need to store any winning
points. Instead, as it is demonstrated below, only a single
real value of
a
*
g
must be stored.
However, =103 64( 1)g


102

. Hence the equa-
tion does not have a solution. On the other
hand, i does have a solution. Indeed, from (33)
it follows that i102/(g+2)=38.961, i.e., =39. And
finally .
102
k
a
b
39(g
102 
2) 102


*
i
16. Solution of Index Equations Revisited
R0.1. Let S := s; L := l; where both integers (s, l) are gen-
erated randomly at the beginning of the Game; let t :=L – S;
R0.2. r := ; using the iterative process (36),
compute logt

 
r
x
; (43)
R0.3. Let
*
g
:= r
x
; (44)
{during the entire Game use *
g
as an approximation of
g in the Equations (29) or (33)};
R1. Find the smallest integer satisfying the ine-
quality
*
k
k*
g
>S (45)
if
**
kg S



then k=; ; (46)
*
k*
k
aS
R2. If is the smallest integer satisfying the ine-
quality
*
i
*
i (*
g
+1) > S (47)
Table 2. Logarithmic growth of r(n).
10k n [0,3] [4,6] [7,12] [13,24]
r(n) 0 1 2 3
then i = and (48)
*
i*
i
bS
Example 7: Let at the beginning of the Game s := 2,718,282
and l := 3,141,593.
Then m :=L – S = l – s = 323,311<. From the ine-
quality 6, {see (40) and (41)}, it follows that r =1.
Hence, only one iteration of (38) is necessary to find
6
10
32
r

*
g
with required accuracy.
17. The Algorithm
It is assumed that Hugo makes the first move by ran-
domly generating positive integers and such
that 0
S0 L


00
1LeSQ  (49)
where e is Euler number, {see Remark3 belo w};
V: m := L – S;
if m = 0 then z := S; S := S – z; L := L – z; {end of the Game:
Cora is the winner};
else
10
:log;tm



;


2
:log /3rt



;
0:1.618;x
for k from 0 to 1r

do
2
1:(1)/(21)
kk k
xx x


 ;
:r Gx

; ; :
m
aGm

if S =m then the Game is already in the winning state
for Hugo;
a
{Nevertheless Cora might decide to continue the
Game hoping that Hugo will make a mistake, i.e., he will
“miss the point”};
if L > 3 then with prob = 1/2 c: = 1 or 2; :LLc

};
goto V;
else if
m
Sa
zS
then :;:;:
m
aLLzS Sz;

 goto V; else
:/kSG



; (50)
kG S


 then
:;:ymkLLy;

 (51)
else :/(1)iSG



; ; : i
aGi

:;:;:;:
i
uLatempSS LuL temp

; goto V.

B. VERKHOVSKY
799


0
S
Remark 3: In order to assure that the first randomly
generated point is not a winning point, it is sufficient to
select such and that
0
S0 L

000
(1)SLSg

 
 (52)
That is guaranteed by (47) and (15), since
00
1.718 1.618LS.
18. Randomization
Let a and be the number of integers on inte rval [1,
M] such that and 1 respectively,
i.e., + =M.
n
n
b
n
1k aM k bM
a
Then b
n

/( 1)
a
nMMg
and (53)

2
/( 1)
b
nMM g
Hence, if a pair of integers (S, L) is generated ran-
domly, then it is more likely that they will be elements of
the sequence A, than the sequence B.
Remark 4: The sequence of the operations (50) and (51)
in the Algorithm is based on the observation that for
every M, .
 
ab
nM nM
That is why on the A4 we first check whether there is
a solution of and only then whether there is a
solution of i. This sequence of verifications de-
creases the average complexity of the algorithm. Another
approach is to randomize the sequence of these operators:
Namely, with the probability g = 0.618 to execute (50)
and then, if necessary, to execute (51). And with the
probability g = 0.382 to execute (51) and only then, if
necessary, to execute (50).
k
aS
bS
Example 8: If M = 50, then

50 31
a
n

and
. Thus, if u is an arbitrary selected integer on
the interval [1, 50], then with probability g there exists
an index k such that k, and with probability

50 19
b
n
au2
g
=
0.382 there exists an index i such that .
i
bu
19. The First Move
With out a th ird independent party, it seems impossible to
introduce a random and trustworthy mechanism for de-
ciding whose move is the first. As a palliative solution,
the following procedure is suggested: immediately, after
the first point (0,0) is generated, Hugo has a short
period of time (say, a couple of seconds) to decide who
must make the first move. One way to preclude Hugo
from cheating and to introduce more variety to the Game,
select Q := 2Q on every consecutive run of the Game
with the same player. More detailed analysis of possible
alternatives is beyond the scope of this paper.
S L
20. Varieties of Nim-Game on Plane
Of many possible varieties I consider only two: the Attri-
tion game and the Flip-Flop game.
In both games the moves are the same as in the Game
described above in this paper. Only the goals are differ-
ent.
Attrition game: The first player that reaches point (0,
0) is a loser.
Flip-flop game: Only once during the Game players
on their move can change the goal of the Game if
27LS (54)
21. Winning Strategies
Let the winning points k in the Attrition game. It is
clear that both 1= (0,1) and 2= (2,2) are the win-
ning points for Cora. Indeed, after Cora’s move (0, 1)
Hugo is losing the Game. The same is with (2,2): after
that move Hugo is forced to reach (0,0), because Hugo
can make either (0,2) or (1,1) or (1,2) move. Then Cora
moves (0,1) and Hugo has no other choice but move
(0,0).
w
w w
Winning points k
f
in Flip-Flop game: Although it
seems confusing, actually the winning points for the
Flip-Flop Game are very simple. It follows from an ob-
servation that for all 2k
kw=, (55) k
w
i.e., 2w

(3,5); 3w

(4,7); and only and
1(2,2)w
0w(1, 0)

.
Hence, if the Game is in the attrition phase, then
kk
f
w

, otherwise kk
f
w. (56)
From the (56) winning strategy it follows that “Only
once during the Game” — requirement is inessential and
it is introduced for a psychological reason only. The
Game can be further modified if the flipper must pay for
every flip, and the winner gets the “bank”.
After this paper was completed, the author discovered
that the Game has been described in [13,14] .
22. Acknowledgements
I appreciate H. Wozniakowski for his suggestion, an
anonymous reviewer for several corrections and B. Blake
for comments that improved the style of this paper.

B. VERKHOVSKY
800
23. References
[1] C. L. Bouton, “Nim, a Game with a Complete Mathe-
matical Theory,” Annals of Mathematics, Princeton 3,
35-39, 1901-1902.
[2] M. Gardner, “Mathematical Games: Concerning the Game
of Nim and its Mathematical Analysis,” Scientific Ameri-
can, 1958, pp. 104-111.
[3] M. Gardner, “Nim and Hackenbush,” Chapter 14 in Wheels,
Life, and Other Mathematical Amusements, W. H. Free-
man, 1983.
[4] E. Berry and S. Chung, “The Game of Nim,” Odyssey
Project, Brandeis University, 1996.
[5] S. Pheiffer, “Creating Nim Games,” Addison Wesley,
1997.
[6] R. D. D. Arruda, “Nim-Type Computer Game of Strategy
and Chance,” Master Project, CIS Department, NJIT,
1999.
[7] R. Statica, “Dynamic Randomization and Audio-Visual
Development of Computer Games of Chance and Strat-
egy,” Master Thesis, CIS Department, NJIT, 1999.
[8] J. von Neumann and O. Morgenstern, “Theory of Games
and Economic Behavior,” 3rd edition, 1953.
[9] R. D. Luce and H. Raiffa, “Games and Decisions-Introduction
and Critical Survey,” 2nd ed ition, Dover Publications, 1989.
[10] G. M. Adelson-Velsky, V. Arlazarov and M. V. Donskoy,
“Algorithms for Games,” 1987.
[11] H. Wozniakowski, “Private communication,” Columbia
University, USA, March 2002.
[12] D. Kahaner, C. Moler and S. Nash, “Numerical Methods
and Software,” Prentice Hall, 1989.
[13] C. Berge, “The Theory of Graphs and its Applications,”
Bulletin of Mathematical Biolody, Vol. 24, No. 4, 1962,
pp. 441-443.
[14] W. A. Wythoff, “A Modification of the Game of Nim,”
Nieuw Archiefvoor Wiskunde, 199-202, 1907-1908.
[15] B. Verkhovsky, “Winning Strategies and Complexity of
Whytoff's Nim Computer Game,” Advances in Computer
Cybernetics, Vol. 11, 2002, pp. 37-41.