#G4 INTEGERS 25 (2025)
WYTHOFF’S GAME WITH A PASS
Ryohei Miyade a
Keimei Gakuin Junio and High School, Kobe Ci y, Japan
[email p o ec ed]
Hika u Manabe
Uni e si y o Tuskuba, Tsukuba Ci y, Japan
[email p o ec ed]
Masano i Fukui
[email p o ec ed]
[email p o ec ed]
Recei ed: 8/14/25, Accep ed:10/27/25 , Published: 11/5/25
Abs ac
This pape desc ibes Wy ho ’s game wi h a pass, which is a a ian o he classical
Wy ho ’s game. The classical o m is played wi h wo piles o s ones, om which
wo playe s ake u ns o emo e s ones om one o bo h piles. When emo ing
s ones om bo h piles, an equal numbe mus be emo ed om each pile. The
playe who emo es he las s one o s ones wins. In Wy ho ’s game wi h a pass,
we modi y he s anda d ules o allow o a one- ime pass, ha is, a pass mo e ha
may be used a mos once in a game bu no om he e minal posi ion. Once
ei he playe uses a pass, i is no longe a ailable We deno e he posi ion o he
game by (x, y, p), whe e xand ya e he numbe s o s ones in he wo piles, p= 1
i a pass is a ailable, and p= 0 o he wise. The au ho s p o e ha o (x, y, 1) wi h
x≥9 o y≥9, (x, y, 1) is a P-posi ion ( he p e ious playe ’s winning posi ion) i
and only i he G undy numbe o (x, y, 0) is 1. They also p o e, using he esul
o U. Blass and A.S. F aenkel, ha he Euclidean dis ance be ween each p e ious
playe ’s winning posi ion in Wy ho ’s game wi h a pass and a nea by p e ious
playe ’s winning posi ion in Wy ho ’s game wi hou a pass is wi hin √20.
1. In oduc ion
Le Z≥0and Nbe he se s o non-nega i e in ege s and na u al numbe s, espec-
i ely. An in e es ing bu challenging ques ion in combina o ial game heo y has
DOI: 10.5281/zenodo.17535339
2
been de e mining wha happens when s anda d game ules a e modi ied o allow
aone- ime pass. This pass mo e may be used a mos once in he game and no
om he e minal posi ion. Once ei he playe has used a pass, i is no longe
a ailable o use. In he case o classical Nim, he in oduc ion o he pass al e s
he ma hema ical s uc u e o he game, conside ably inc easing i s complexi y, and
inding he o mula ha desc ibes he se o p e ious playe s’ posi ions emains an
impo an open ques ion ha has de ied adi ional app oaches o sol ing i .
The la e ma hema ician Da id Gale o e ed a mone a y p ize o he i s pe son
who de eloped a solu ion o he h ee-pile classical Nim wi h a pass. In [9] (p.
370), Mo ison, F iedman, and Landsbe g conjec u ed ha “sol able combina o ial
games a e s uc u ally uns able o pe u ba ions, while gene ic, complex games will
be s uc u ally s able.”One way o in oduce such a pe u ba ion is o allow a pass.
Howe e , he au ho s o he p esen a icle epo ed some games as coun e examples
o his conjec u e in [5], [7], and [8]. These games a e sol able because he e a e
simple o mulas o he G undy numbe s, and e en when we in oduce a pass mo e
o he games, he e a e simple o mulas o P-posi ions. Based on he esea ch in
[5], [7], and [8], he au ho s o he p esen a icle p opose he ollowing iew on he
combina o ial game wi h a pass.
Some games ha e speci ic ma hema ical s uc u es ha p e en he pe u ba ion
caused by he pass om sp eading o o he posi ions, and hese games ha e o mulas
o P-posi ions, e en i a pass is in oduced. Howe e , he ma hema ical s uc u es
o some games pe mi he pe u ba ion caused by he pass o sp ead all o e he
posi ions.
He e, we p esen esea ch on Wy ho ’s game wi h a pass. Wy ho ’s game wi h
a pass p esen s a pe ec example o speci ic ma hema ical s uc u es ha p e en
he pe u ba ion caused by he pass om sp eading o o he posi ions.
Fo o he esea ch on combina o ial games wi h a pass, see [3], [4], and [6]. In [3]
and [6], Chan, Low, Locke, and Wong desc ibed he se o p e ious playe s’ posi ions
o Nim wi h a pass when he numbe o s ones in each pile is a mos ou . This
s udy shows ha he impac o pe u ba ion is small when he numbe o s ones
in each pile is small. In [4], i was p o en ha he a i hme ic pe iodici y o he
G-sequence can occu when we add a single pass mo e o p ecisely one pile in ini e
oc al games, al hough ini e oc al games a e no a i hme ic pe iodic. The e o e, in
his case, egula i y, no pe u ba ion, occu s by adding a single pass o he ini e
oc al games.
Fo comple eness, we b ie ly e iew some o he necessa y concep s in combina-
o ial game heo y by e e ing o [1] and [10].
De ini ion 1. Le xand ybe non-nega i e in ege s. We ep esen hem in base
2, so ha x=Pn
i=0 xi2iand y=Pn
i=0 yi2iwi h xi, yi∈ {0,1}. We de ine he
3
nim-sum x⊕yby
x⊕y=
n
X
i=0
wi2i,
whe e wi=xi+yi(mod 2).
Wy ho ’s game is an impa ial game wi hou d awings; only wo ou come classes
a e possible.
De ini ion 2. A posi ion is e e ed o as a P-posi ion i i is he winning posi ion
o he p e ious playe ( he playe who has jus mo ed), as long as he playe plays
co ec ly a each s age. A posi ion is e e ed o as an N-posi ion i i is he winning
posi ion o he nex playe , as long as hey play co ec ly a each s age.
De ini ion 3. The disjunc i e sum o he wo games, deno ed by G+H, is a supe
game in which a playe may mo e ei he in Go Hbu no in bo h.
De ini ion 4. Fo any posi ion pin game G, a se o posi ions can be eached by
a single mo e in G, which we deno e as mo e(p).
De ini ion 5. The minimum excluded alue (mex) o a se So nonnega i e in ege s
is he leas nonnega i e in ege ha is no in S.
De ini ion 6. Le pbe a posi ion in he impa ial game. The associa ed G undy
numbe is deno ed by G(p) and is ecu si ely de ined by G(p) = mex({G(h) : h∈
mo e(p)}).
The nex esul demons a es he use ulness o he Sp ague–G undy heo y o
impa ial games.
Theo em 1 ([1]).Le Gand Hbe impa ial ulese s, and GGand GHbe he
G undy numbe s o game gplayed unde he ules o Gand game hplayed unde
hose o H. Then, we ob ain he ollowing:
(i) o any posi ion gin G, we ha e ha GG(g) = 0 i and only i gis he P-
posi ion;
(ii) he G undy numbe o posi ions {g,h}in game G+His GG(g)⊕GH(h).
Using Theo em 1, we can de e mine he P-posi ion by calcula ing he G undy
numbe s and he P-posi ion o he sum o he wo games by calcula ing he G undy
numbe s o he wo games.
2. Wy ho ’s Game
In his sec ion, we e iew some o he heo ems o Wyho ’s game o la e use. Fo
he de ails o Wy ho ’s game, see [11].
4
De ini ion 7. Wy ho ’s game is played wi h wo piles o s ones. Two playe s ake
u ns emo ing s ones om one o bo h piles. When emo ing s ones om bo h
piles, he numbe o s ones emo ed om each pile should be equal. The playe
who emo es he las s one o s ones wins. An equi alen desc ip ion o he game
is ha a single chess queen is placed somewhe e on a la ge g id o squa es, and
each playe can mo e he queen owa ds he uppe -le co ne o he g id, ei he
e ically, ho izon ally, o diagonally, o any numbe o s eps. The winne is he
playe who mo es he queen o he uppe -le co ne .
Figu e 1 shows he g id o squa es, and we deno e by (x, y) he numbe o s ones
in he i s and second piles o he posi ion o he queen, whe e he ho izon al and
e ical coo dina es a e deno ed by xand y. Figu e 2 shows he mo es ha he
queen can make in Wy ho ’s game.
Figu e 1 Figu e 2
Theo em 2 ([11]).The se o P-posi ions o he game in De ini ion 7 is
{(⌊nϕ⌋,⌊nϕ⌋+n) : n∈Z≥0}∪{(⌊nϕ⌋+n, ⌊nϕ⌋) : n∈Z≥0},
whe e ϕ=1+√5
2.
Theo em 2 is a well-known ac in Wy ho ’s game.
Theo em 3 ([2]).Le {(an, bn) : n∈Z≥0}={(x, y) : G(x, y) = 1}. He e, we
assume ha anis inc easing. Then, we ob ain
|bn−(⌊nϕ⌋+n)|≤ 4
and
⌊nϕ⌋−1≤an≤ ⌊nϕ⌋+ 2.
Theo em 3 is Co olla y 5.14 o [2].
Co olla y 1. Fo any posi ion (x, y)wi h G(x, y)=1, he e exis s a posi ion ( , w)
such ha G( , w)=0and p(x− )2+ (y−w)2≤√20.
P oo . This ollows di ec ly om Theo ems 2 and 3.
5
3. Wy ho ’s Game wi h a Pass and he Sum o Wy ho ’s Game and a
Pile o One S one
In his sec ion, we de ine a new a ian o Wy ho ’s game and compa e i o he
sum o Wy ho ’s game and a pile o one s one.
De ini ion 8. Wy ho ’s game wi h a pass is played like he o dina y Wy ho ’s
game, wi h he op ion o a single pass ha can be used by exac ly one playe . Once
a pass is used, i canno be used again. The pass can be used a any ime up o he
penul ima e mo e, bu i canno be used a he end o he game. The playe who
canno make a mo e loses. We deno e by G1 he G undy numbe o his game.
He e, we in oduce he sum o he adi ional Wy ho ’s game and a pile o one
s one. We need his game o s udy P-posi ions o Wy ho ’s Game wi h a Pass.
De ini ion 9. Applying De ini ion 3, we de ine he sum o he classical Wy ho ’s
game wi hou a pass and he game o a pile o one s one. We deno e by G2 he
G undy numbe o his game.
We deno e he posi ion o he game in De ini ion 8 and he game in De ini ion
9 by h ee coo dina es {x, y, p}. The coo dina es x, y de ine he numbe o s ones
in he i s and second piles, o , i we use a queen in he game, he posi ion o he
queen on he chessboa d. Fo he game in De ini ion 8, he addi ional pa ame e p
deno es whe he he pass is s ill a ailable (p= 1) o has al eady been used (p= 0).
Fo he game in De ini ion 9, he pa ame e p= 1 i he e is a s one in he hi d
pile, and p= 0 i he e is no s one in he hi d pile. No e ha when p= 0, he
games in De ini ions 8 and 9 a e he classical Wy ho ’s game.
De ini ion 10. Fo any x, y ∈Z≥0and p= 0,1, le
M1(x, y, p) = {(u, y, p) : u < x and u∈Z≥0},
M2(x, y, p) = {(x, , p) : < y and ∈Z≥0},
M3(x, y, p) = {(x− , y − , p):1≤ ≤min(x, y) and ∈Z≥0},
M4(x, y, p) = ({(x, y, 0)}( i x+y > 0 and p= 1),
∅( i x+y= 0 o p= 0),
and
M′
4(x, y, p) = ({(x, y, 0)}( i p= 1),
∅( i p= 0).
6
The se s M1(x, y, p), M2(x, y, p), and M3(x, y, p) a e he se s o ho izon al, e i-
cal, and diagonal mo es, espec i ely. Se M4(x, y, p) is he se o he pass mo e o
Wy ho ’s game wi h a pass in De ini ion 8, and Se M′
4(x, y, p) is he se o mo es
in he hi d pile o he game in De ini ion 9. No e ha M4(x, y, p) is emp y i and
only i x+y= 0 o p= 0, and M′
4(x, y, p) is emp y i and only i p= 0.
Nex , we de ine mo e1and mo e2, which a e mo es o he games in De ini ions
8 and 9, espec i ely.
De ini ion 11. Fo any x, y ∈Z≥0and p= 0,1, le
mo e1(x, y, p) = M1(x, y, p)∪M2(x, y, p)∪M3(x, y, p)∪M4(x, y, p)
and
mo e2(x, y, p) = M1(x, y, p)∪M2(x, y, p)∪M3(x, y, p)∪M′
4(x, y, p).
4. The Posi ions (x, y, p) such ha x, y ≤8
This sec ion aims o de e mine P-posi ions and N-posi ions in he se {(x, y, p) :
x, y ≤8}in Lemma 1. We now de ine h ee se s, A,B, and C, and s udy hem.
These se s ha e ma hema ical s uc u es ha p e en he pe u ba ion caused by
he pass om sp eading o o he posi ions. In Figu es 3, 4, 5, 6, 7, 8, 9, he G undy
numbe s o each poin a e p in ed, bu hese G undy numbe s ha e no hing o do
wi h he a gumen in his sec ion.
De ini ion 12. Le
A={(0,0,0),(1,2,0),(2,1,0),(3,5,0),(4,7,0),(5,3,0),(7,4,0)},
B={(0,0,1),(1,3,1),(3,1,1),(2,5,1),(5,2,1),(4,8,1),(8,4,1),(6,7,1),(7,6,1)},
and
C={(0,1,1),(1,0,1),(2,2,1),(3,6,1),(6,3,1),(4,8,1),(8,4,1),(5,7,1),(7,5,1)}.
In Figu es 3, 4, and 5, we ha e he se s o G undy numbe s {G1(x, y, 0) : x, y ≤8},
{G1(x, y, 1) : x, y ≤8}, and {G2(x, y, 1) : x, y ≤8}, espec i ely. He e, se s A,B,
and Ca e p in ed in ed.
7
0 1 2 3 4 5 6 7 8
0 0 1 2 3 4 5 6 7 8
1 1 2 0 4 5 3 7 8 6
2 2 0 1 5 3 4 8 6 7
3 3 4 5 6 2 0 1 9 10
4 4 5 3 2 7 6 9 0 1
5 5 3 4 0 6 8 10 1 2
6 6 7 8 1 9 10 3 4 5
7 7 8 6 9 0 1 4 5 3
8 8 6 7 10 1 2 5 3 4
Figu e 3: Se A
0 1 2 3 4 5 6 7 8
0 0 2 1 4 3 6 5 8 7
1 2 1 3 0 6 4 8 7 5
2 1 3 2 6 4 0 7 5 8
3 4 0 6 3 1 2 9 10 11
4 3 6 4 1 5 7 10 2 0
5 6 4 0 2 7 9 11 3 1
6 5 8 7 9 10 11 4 0 6
7 8 7 5 10 2 3 0 6 4
8 7 5 8 11 0 1 6 4 10
Figu e 4: Se B
0 1 2 3 4 5 6 7 8
0 1 0 3 2 5 4 7 6 9
1 0 3 1 5 4 2 6 9 7
2 3 1 0 4 2 5 9 7 6
3 2 5 4 7 3 1 0 8 11
4 5 4 2 3 6 7 8 1 0
5 4 2 5 1 7 9 11 0 3
6 7 6 9 0 8 11 2 5 4
7 6 9 7 8 1 0 5 4 2
8 9 7 6 11 0 3 4 2 5
Figu e 5: Se C
Figu e 6: F om P no P
0 1 2 3 4 5 6 7 8
0 0 2 1 4 3 6 5 8 7
1 2 1 3 0 6 4 8 7 5
2 1 3 2 6 4 0 7 5 8
3 4 0 6 3 1 2 9 10 11
4 3 6 4 1 5 7 10 2 0
5 6 4 0 2 7 9 11 3 1
6 5 8 7 9 10 11 4 0 6
7 8 7 5 10 2 3 0 6 4
8 7 5 8 11 0 1 6 4 10
Figu e 7: Ho izon al
0 1 2 3 4 5 6 7 8
0 0 2 1 4 3 6 5 8 7
1 2 1 3 0 6 4 8 7 5
2 1 3 2 6 4 0 7 5 8
3 4 0 6 3 1 2 9 10 11
4 3 6 4 1 5 7 10 2 0
5 6 4 0 2 7 9 11 3 1
6 5 8 7 9 10 11 4 0 6
7 8 7 5 10 2 3 0 6 4
8 7 5 8 11 0 1 6 4 10
Figu e 8: Ve ical
0 1 2 3 4 5 6 7 8
0 0 2 1 4 3 6 5 8 7
1 2 1 3 0 6 4 8 7 5
2 1 3 2 6 4 0 7 5 8
3 4 0 6 3 1 2 9 10 11
4 3 6 4 1 5 7 10 2 0
5 6 4 0 2 7 9 11 3 1
6 5 8 7 9 10 11 4 0 6
7 8 7 5 10 2 3 0 6 4
8 7 5 8 11 0 1 6 4 10
Figu e 9: Daiagonal
Lemma 1. (i)The se Ain De ini ion 12 is he se o P-posi ions (x, y, 0) o he
game in De ini ion 8 such ha x, y ≤8and he pass is no a ailable.
(ii)The se Bin De ini ion 12 is he se o P-posi ions (x, y, 1) o he game in
De ini ion 8 such ha x, y ≤8and he pass is a ailable.
(iii)The se Cin De ini ion 12 is he se o P-posi ions (x, y, 1) o he game in
De ini ion 9 such ha x, y ≤8and he hi d coo dina e is 1.
P oo . (i) Since he pass is no a ailable, by using Theo em 2 o x, y ≤8 we ob ain
Se A.
8
(ii) Le U={(x, y, 1) : x, y ≤8}. Since we need o p o e ha he se P-posi ions
o he game in De ini ions 8 in Uis Bwhen a pass is a ailable, we need o p o e
ha
mo e1(x, y, 1) ∩(A∪B) = ∅(1)
o any (x, y, 1) ∈Band
mo e1(x, y, 1) ∩(A∪B)=∅(2)
o any (x, y, 1) ∈U−B.
Fi s , we p o e Rela ion (1). Suppose ha we s a wi h he posi ion (7,6,1).
Then, he ho izon al, e ical, and diagonal mo es om his posi ion a e desc ibed
in Figu e 6, and i is easy o see ha M1(7,6,1) ∩B=∅,M2(7,6,1) ∩B=∅,
and M3(7,6,1) ∩B=∅. Since M4(7,6,1) = {(7,6,0)}and (7,6,0) /∈A, we ob ain
M4(7,6,1) ∩A=∅. The e o e, mo e1(7,6,1) ∩(A∪B) = ∅. Simila ly, o any
(x, y, 1) ∈B, i is easy o show ha M1(x, y, 1) ∩B=∅,M2(x, y, 1) ∩B=∅, and
M3(x, y, 1)∩B=∅. By compa ing Figu e 3 and Figu e 4, we ob ain M4(x, y, 1)∩A=
∅. The e o e, we ob ain Rela ion (1).
Nex , we p o e Rela ion (2). Le (x, y, 1) ∈U−B. Fo (8, y, 1) wi h y= 0,1,2,3
and y= 5,6,7,8, i is clea ha M1(x, y, 1) ∩B=∅. In his way, o all blue
posi ions (x, y, 1) in Figu e 7, we ob ain M1(x, y, 1) ∩B=∅. Simila ly, o all blue
posi ions (x, y, 1) in Figu e 8, we ob ain M2(x, y, 1)∩B=∅and o all blue posi ions
(x, y, 1) in Figu e 9, we ob ain M3(x, y, 1) ∩B=∅. The posi ions in U−B ha do
no belong o he se o blue posi ions in Figu es 7, 8, and 9 a e (1,2,1) and (2,1,1).
Since (1,2,0) and (2,1,0) belong o he se Ain Figu e 3, M4(1,2,1) ∩A=∅and
M4(2,1,1) ∩A=∅. The e o e, we ob ain Rela ion (2).
(iii) By a me hod ha is e y simila o he one used in (ii), we can p o e (iii).
The e o e, he de ails a e omi ed.
5. The Se o P-posi ions o Wy ho ’s Game wi h a Pass
In his sec ion, we de e mine he se o P-posi ions o Wy ho ’s game wi h a pass.
We use he simila i y be ween he se o P-posi ions o Wy ho ’s game wi h a pass
and he se o P-posi ions o he game in De ini ion 9.
Le P0={(x, y, 0) : G1(x, y, 0) = 0},P1={(x, y, 1) : G1(x, y, 1) = 0}, and
P2={(x, y, 1) : G2(x, y, 1) = 0}.
Lemma 2. Le x, y ∈Z≥0such ha x≥9o y≥9. Then, we ob ain he ollowing:
(i)i y≤8, hen M1(x, y, 1) ∩B=∅,M1(x, y, 1) ∩C=∅, and M2(x, y, 1) ∩C=
M2(x, y, 1) ∩B=∅;
(ii)i x≤8, hen M2(x, y, 1) ∩B=∅,M2(x, y, 1) ∩C=∅, and M1(x, y, 1) ∩C=
M1(x, y, 1) ∩B=∅;
9
(iii)i x≤y+ 4 and y≤x+ 4, hen M3(x, y, 1) ∩B=∅and M3(x, y, 1) ∩C=∅;
(i )i x≥y+ 5 o y≥x+ 5, hen M3(x, y, 1) ∩B=M3(x, y, 1) ∩C=∅.
P oo . (i) Suppose ha x≥9 and y≤8. Then, by De ini ion 12, he e exis
u, u′∈Z≥0such ha 1 ≤u, u′≤8, (u, y, 1) ∈B, and (u′, y, 1) ∈C. Then, we
ob ain (u, y, 1) ∈M1(x, y, 1) ∩Band (u′, y, 1) ∈M1(x, y, 1) ∩C. Since x≥9,
M2(x, y, 1) ⊂ {(x, , 1) : ∈Z≥0} ⊂ (B∪C)c, whe e (B∪C)cis he complemen
o he se B∪C. Hence, M2(x, y, 1) ∩C=M2(x, y, 1) ∩B=∅.
(ii) Suppose ha y≥9 and x≤8. Then, (ii) ollows di ec ly om (i), because his
game is symme ical wi h espec o he i s and second coo dina es.
(iii) Suppose ha x≤y+ 4 and y≤x+ 4. By De ini ion 12, o any a∈Z≥0such
ha −4≤a≤4, he e exis u, u′, , ′∈Z≥0such ha u= +a,u′= ′+a,
(u, , 1) ∈B, and (u′, ′,1) ∈C. Then, (u, , 1) ∈B∩M3(x, y, 1) and (u′, ′,1) ∈
C∩M3(x, y, 1). The e o e, M3(x, y, 1) ∩B=∅and M3(x, y, 1) ∩C=∅.
(i ) We ha e wo cases.
Case 1: Suppose ha x≥y+ 5. The e is no u, ∈Z≥0such ha u≥ + 5 and
(u, , 1) ∈B∪C. Hence, M3(x, y, 1) ∩B=M3(x, y, 1) ∩C=∅.
Case 2: Suppose ha y≥x+ 5. Since his game is symme ical wi h espec o
he i s and he second coo dina es, M3(x, y, 1) ∩B=M3(x, y, 1) ∩C=∅.
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
0 0 2 1 4 3 6 5 8 7
1 2 1 3 0 6 4 8 7 5
2 1 3 2 6 4 0 7 5 8
3 4 0 6 3 1 2 9 10 11
4 3 6 4 1 5 7 10 2 0
5 6 4 0 2 7 9 11 3 1
6 5 8 7 9 10 11 4 0 6
7 8 7 5 10 2 3 0 6 4
8 7 5 8 11 0 1 6 4 10
9
10
11
12
13
14
Figu e 10: Se B and o he posi ions
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
0 1 0 3 2 5 4 7 6 9
1 0 3 1 5 4 2 6 9 7
2 3 1 0 4 2 5 9 7 6
3 2 5 4 7 3 1 0 8 11
4 5 4 2 3 6 7 8 1 0
5 4 2 5 1 7 9 11 0 3
6 7 6 9 0 8 11 2 5 4
7 6 9 7 8 1 0 5 4 2
8 9 7 6 11 0 3 4 2 5
9
10
11
12
13
14
Figu e 11: Se C and o he posi ions
Lemma 3. Fo x, y ∈Z≥0such ha x≥9o y≥9, we ob ain he ollowing:
(i)M1(x, y, 1) ∩B=∅i and only i M1(x, y, 1) ∩C=∅;
(ii)M2(x, y, 1) ∩B=∅i and only i M2(x, y, 1) ∩C=∅;
(iii)M3(x, y, 1) ∩B=∅i and only i M3(x, y, 1) ∩C=∅.
P oo . By Lemma 2, we ob ain (i), (i), and (iii).
