A stronger model for peg solitaire II

-

Documents
27 pages
Obtenez un accès à la bibliothèque pour le consulter en ligne
En savoir plus

Description

Niveau: Supérieur, Doctorat, Bac+8
A stronger model for peg solitaire, II ?† O. Ramaré, CNRS, Laboratoire Painlevé, Université Lille 1 59 655 Villeneuve d'As q, Fran e January 4, 2008 Abstra t The main problem addressed here is to de ide whether it is or not possible to go from a given position on a peg-solitaire board to another one. No non-trivial su ient onditions are known, but tests have been devised to show it is not possible. We expose the way these tests work in a unied formalism and provide a new one whi h is stri tly stronger than all previous ones. 1 Introdu tion Peg solitaire (also alled Hi-Q) is a very simple board game that appeared in Europe most probably at the end of the 17th entury. Its prior origin is unknown. The rst eviden e is a painting by Claude-Auguste Berey of Anne Chabot de Rohan (1663-1709) playing it. It seems to have then be ome popular in some royal ourts. The mathemati al study of the game starts in 1710 when Leibniz writes a memoir on the subje t [1?. We refer the reader to the ex ellent histori al a ount presented in Beasley's book [2?. Let us introdu e rapidly how this game is being played.

  • single peg via legal moves

  • negative integer

  • conway's group theory

  • lassi al

  • ex ellent histori

  • peg solitaire

  • full linear


Sujets

Informations

Publié par
Nombre de lectures 37
Langue English
Signaler un problème

∗†
2S
I
J


I
I
p
The
h
and
for
ted
O.
w
Ramar?,
),
CNRS,
sub
Lab
game
oratoire
Z
P
(see
ainlev
en
?,
solitaire,
Univ
1710
ersit?
to
Lille
us
1
rst
59
e
655
h
Villeneuv
tro
e
oard

it
F
mo
rance
that
Jan

uary
the
4,
a
2008
e

historical
The
o
main
rapidly
problem
pla
addressed
b
here
ximation
is
as
to
oard

b
whether
a
it
J.C.
is
square
or
most
not
as
p
go
ossible
p
to
one
go
of
from
w
a
da
giv
91A46,
en
study
p
starts
osition
Leibniz
on
on
a

p
the
eg-solitaire

b
t
oard
Beasley's
to

another
tro
one.
w
No
b
non-trivial
ed.
sucien
is
t
stronger

rst
are
y
kno
t
wn,
subset
but
english
tests
the
ha
dra
v
w,
e
presen
b
one
een
b
devised
in
to

sho
this
w
hold
it
p
is
pr
not
e
p
is
ossible.
a
W
of
e
(sa
exp
to
ose
y
the
a
w
gal
solitaire,
e
eyw
a
y
P
these
P
eg
tests
w
05A99,
ork
90C08.
in
mathematical
a
of
unied
game
formalism
in
and
when
pro
writes
vide
memoir
a
the
new

one
W
whic
refer
h
reader
is
the

t
stronger

than
presen
all
in
previous
b
ones.
ok
1
Let
In
in
tro


ho
P
this
eg
is
solitaire
eing
(also
y

The
Hi-Q)
data
is
a
a
oard
v
whic
ery
in
simple
appro
b
ma
oard
b
game
though
del
of
.
a

of
are
that
app
The
eared
ones
in
the
Europ
b
e
and
most

probably
one
at
wn
the
elo
end
and
of
e
the
t
17th
third

in
tury

.
y
Its
Wiegleb
prior
1779
origin

is
h
unkno
of
wn.
b
The

rst
at

one
is
eg,
a
a
pain
oblem
ting
w
b
dene
y
here
Claude-Auguste
to
Berey
from
of
giv
Anne
distribution
Chab
these
ot
egs
de
y
Rohan
)
(1663-1709)
another
pla
(sa
A
ying
it.
via
It

seems
le
to
moves
ha
w
v
no
e
dene.
then
k
b
ords:
ecome
eg
p
Hi-Q,
opular
ago
in
function.
some
AMS
ro
primary
y

al
52B12,

1P Q R
P Q
R
P Q R
P Q R
Q
|I|−|J|
|I|−|J|
577 116 156 815 309 849 672
40 861 647 040 079 968
n×n k×n
k
7× 7
remo
ving
tral
Wiegleb
h
the
an
t
binatorial
w
.
o
are
p
this
egs
e
in
eg
3:
b
and
a
Figure
problem
and
y
putting
it
one
b
on
reac
the
gets
empt

y
oard
square
the
oard
v
.
on
W
nal
e
umerous

to
sa
y
y
to
that
in
the
es

the
p
not,
eg
mo
in
fur-
b
This
jumps
ecause
o

v
one
er

the

middle
english
one

in
h
h
tral
and
whic
lands
a
in
en
renc
eing
,

while
sho
destro
or
ying
a
the
ose
p
b
eg
is
in
that.
F
b
.
e
As
mo
a
rep
trivial
un

n
the
(
n
do
um
)
b
es
er
or
of
mo
p
p
egs

on
k
the
the
b
F
oard
Harang

there
when
the
the
a
game
b
pro
(sa

w
further.
on
F
oard
or
p
most
the
authors,
on
a
e
problem
the

empt
in
whic

diagonal),
the
(but
initial
w
distribution
Giv
of
to
p
eg
egs,
the
what
See
w

e
tend

that
thereafter
NP-complete.
the
sen
initial
v
p
w
osition

,
w
to
extending
a
to
single
and
p

eg
hiev
via

legal
three
mo
is
v
while
es.
us
They
not
qualify
v
the
and
p
eat
osition
action
as
til
solvable
required
if
um
this
er
is
a
p
es
ossible.
)
W
(
e
of
shall
v
sa
is
y
hed
that
no
the
ther
problem
v
in
is
our
ossible.
sense
pro
is
usually
fe
stuc
asible
b
if
of
one


explosion.
go
or
from
E.
the

initial
that
p
are
osition
third
to
while
the
p
nal
tain
one
)
b
and
y
y
using
e
legal
o
mo
t
v
paths
es.
the
Note
b
that
from
the
initial
n
osition
um
of
b
full
er
oard
of
whic

w
h
lea
mo
e
v

es
square
is
y
kno
Of
wn
h
and
of
equals
a
the
not
dierence

b
or
et
ro
w
in
een
and
the
lead
n
the
um
p
b
b
er
on
of

p
square.
egs
also
in
In
the
n
initial
setting
p
to
osition
w
and
the
the
is
n
F
um
this

tence
move
ha
oard
e
gal
sense,
is
e
wn
to
b
ho
linear
a

a

of
ma
the
w
oard
whether
innit
english
,
oard
there
a
no
of
fashion
le
ac
in
e
oard
The
tractable
of
not
,
the
squares
er
oard
still
studied
at

not
the
will
b
er
b
of
with
p
xed
egs
sho
in
to
the
e
nal
in
one
Of
(that
one
is:
y
2:
onder
Figure
the
oard
b
b
as
English
subset
1:
a

h

b
n
is
b
or
of
and
b
answ
enormous,
is
e
no,
ok
least
tests
without
Figure
uge
).
The
Giv
um
en
er
a
paths
problem,
eing
w
w
e
lo

for
try
that
all
ensure
p
that
ossible
is
legal
2S F(S, )
F(S, ) F(S, )2
I ⊂S
ˇP ∈S PI
ˇ ˇ ˇP f =P+Q−R −fI
attributed
to
Reiss
has
in
use
in
in
1857
whic
in
Beasley

oard.
though
game.
Beasley
of
traces
ev
it
due

or
k
of
to
een
A.
are
Suremain
w
de
none
Missery
b
,
an
a
a
former
GTK

in
of

the
t
F
for
renc
en
h
In
artillery
del
,
w
around
though
1842.
oard
W
The
e
this
again
tee
refer
p
the
set
reader
its
to
function

th
for
an
more
e
historical
a
details.
Let
It
y
is

also
in
describ
it
ed
our
in
w

(to
b
wledge
o
on
ok
not

time,
whic
orking
h
via


tains
tally
also
It
more

material
of
and
b
in
Z
the
et

functions

dene
hapter
y
of
.

of
A
game
seemingly
w
more
taining

mo

1
h
w
is
in
prop
mo
osed
W
in
ossible
[10],
tensiv
but
the
it
[12],
turns
terface
out
b
to
the
b
end
e

only
tioning
a
in
dieren
v
t
ol
setting
out
for
),
the
es
same
ell
test.
ork
This
b
test
ed
is
arbitrary
v
b
ery
y
often
least),

one
b
english
y
e
mo
it
dern

authors
has
to
at
the
a
rule-of-three
this
test
rewriting
(see

b
remains
elo
er
w).
dimensional
W
rewriting
e
had
shall
describing
rst
of
presen
Main
t
linear
these
en
tests
of
in

a
dule
formalism
kno
that
all
will
v
help
v
us
oard,

y
the
F
situation;
feasibilit
this
Q
formalism
is
will
main
also
formalization:
b
in
e
giv
adequate
a
to
test
presen
squares
t
p
the
w
adv
b


realised
.
on
w
the
w
sub
is

and
in
else.
1961/1962
e
at
the
Cam
en
bridge
solv
univ
via
ersit
in
y
e
b
of
y
lp_solv
a
library
group
a
of
in
studen
and
ts
C-program
(among
oth
whic
to
h
author.
w
us
ere
this
Beasley)
tro
led
b
b
men
y
that
J.H.
also
Con
tro
w
a
a
ery
y
to
.
(the
W
and
e
The
shall
ems
nally
but
presen
do
t
not
a
w
dieren
in
t
framew
test,
and
whic
not
h
een
w
ork
e
out
term
an

problem
and
the
whic
est
h
m
is
kno
stronger
at
than
ev
all
if
previous
remains
ones.
an
It
b
ho
W
w
shall
ev
discuss
er
here.
relies
more
on
t
solving
there
a
b
larger
attempts
in
w
teger
out
linear
mo
program
of
and
game

string
sometime
as
b
[6
e
This

h
demanding.
ho
W
ev
e
fundamen
pro
one
vide
as
ho
string
w
rules.
ev
has
er
applications
n
in
umerous
the
examples
y
that
the
w
2
e
formalism
ha
the
v
b
e
Giv
disco
a
v
oard
ered
,
b
e
y
the
exploring
-mo
thousands
rst
of
wn.
problems,
Z
and
of
this
rational
in
teger
itself
alued
sho
o
ws
er
the
b

and
y
similarly
of
are
the
but

,
h.
and
The
the
theory
guaran
of
ould
this
This
test
one
in
the
its
step
purest
the
form
a
is
osition

the
but
is
w
en
e
y
pro
subset
vide
that
in
(the
the
of
t

w
a
o
eg),
last
h

e
sev
del
eral
y
impro

v
function
emen
y
this
If
and

is
,
note
e
test
ould
whic
the
h
that
w
1
e
e
are
0
still
erywhere
w
A
orking.
v
All
is
examples
us
ha
function
v
problem.
e
giv
b
e
een
to

ts
of
1
p
it,
on
3P Q R
S D(S)
D(S) S
I J
f ,f ,...,f1 2 k
X
− = f.I J i
1≤i≤k
• − D(S)I J
• −I J
D(S)
• −I J
D(S)
X
V(S, ) = ·f
f∈D(S)
X X
+ + + +V (S, ) = ·f , V (S, ) = ·f.
f∈D(S) f∈D(S)
I
F2
˜ F(S, )I 2
I J
f ,f ,...,f1 2 k X
˜˜ ˜− = fI J i
1≤i≤k
that
y
1
set
.

sa
ha


1
b
e
Let
is
as
a
function
rational

in
another
teger
y
linear
(3)

mo
bination
is
of
with
mem
e
b
in
ers
to
of
e
W
v
writing.

this

exploit
v
.
e
This
and
leads
ose
to

the
0

ok
Reiss's
alues
theory
elemen
,
v
or
w
to
t
the
this
lattice
initial

ts
of
v
[11
and

still
to
w
1
76,
ys
oard,
a
the
1
In
w
b
is
these
a
denote
linear
.

Reiss
bination
rule-of-three
with
rst
non-negativ
and
e
notations
rational
Characteristic

v

1,
ts
to
of
1
mem
its
b
the
ers
w
of
a
three
o
are

There
or
(1)

.
an
This
ro
leads
F
to
If
the
from
main
osition
part
nal
of
y
Con
legal
w
oin
a
three
y's
that
group
,
theory
e
.
e
1

1
b
1
y
e
has
1
Q
v
english
is
of
a
the
linear
.
ha
Z
e
es
w
mo
non-negativ
of
e
the
in
Z
teger
W

of

3
ts
theory
of
the
mem
test
b
us
ers
exp
of
rapidly
Then
in
.
dern
es
the
v
material.
.
functions
This
ving
leads
alues
to
or
what
it
w
tempting
e
lo

at
the

ful
taking
l
v
line
in
ar
eld
test
t
,
o
or
ts
also
in
the
T
non-negativ
a
e
oid
in
w
teger
note
test.
1
W
this
e

in
as
tro
elemen

of
some
a
notations
either
mo
order
legal
.
of
one

go
Z
the
the
p
y
in
b
the
to
one
from
b
go
the

of
e
mo
w
es
Z
p
Assume

remark.
where
(2)
,
and
assumed
main
of
the
one

has
Here
1
33.
ha
Q
1
y
function;


has
ecome
while

should
bination
with
4˜ ˇ ˇ ˇf f = P +Q−Ri 2
˜f S 1 ∈ 2
P Q R 2
˜ ˜V(S, ) −2 I J
V(S, )2
F(S, )2
⊥V(S, )2
χ∈F(S, )2
ˇ ˇ ˇ∀f =P +Q−R∈D(S), χ(P)+χ(Q) =χ(R)
χ
X
∀g∈V(S, ), χ(A)g(A) = 0.2
A∈S
⊥V(S, )2
χ0
1 0
1 1
1 0 1
1 1 0
0 1 a
a
the
es
extend
a
function
F
w
tak
.
that
p
is
w
to
name

and
equations
the
of
four
it.
alues
By
further.
using
o
the
W

elemen
scalar
at
pro
ose

to
this
Let

W
to
a

Figure
er
w
v
y
o
y
function
on
F
square
the
,
is
need
then

whic
of
h
F
means
all
the
e
elemen
name
ts
us
,
so
If
b
.
determine
F
three
in
rst
alues
alues
F
for
v

with
Starting

using
h

that
v
seen
w
es
this
v
the
mo
v
the


e
of
the
taining
ts
1
(5)
are
e
,
a
whether
for

h
space!
ts
ector

v
as
a
F
simply
F
is
,
and
w
v
prop
F
the
anishes
witness
otherwise.
Let
Ho
start
w
do
and
on
eld
english
a
oard.
w
us
no
a
(4)
the
since
.
an
e
y
x

v
h
on
is
square,
v

eries

ev
to
alue
4:
of
v
5:
By
As
(4),
turns
e
there
readily
t
these
o
alues:
a
a
to
One
v
problem
either
line
v
Figure
in
Extension
us
it
Let
out,
algebra.
are
F
w
linear
w
only
ys
requiring

F
:
matter
b
on
adding
estigate
t
simple
o
a
alues
is
the
it
ab
to
v
elongs
its
b
or
oin
t
1
o
and
the
er,

where
5a = 1
χ0
V(S, )2
1 0 0 1 0 0 0 0
0 0 0 0 1 0 0 1
2
1 1 0 1 1 0 1 1 0 1 1 0 1
1 1 0 1 1 0 1 1 0 1 1 0 1
0 0 0 0 0 0 0 0 0 0 0 0 0
1 1 0 1 1 0 1 1 0 1 1 0 1
1 1 0 1 1 0 1 1 0 1 1 0 1
0 0 0 0 0 0 0 0 0 0 0 0 0
1 1 0 1 1 0 1 1 0 1 1 0 1
1 1 0 1 1 0 1 1 0 1 1 0 1
0 0 0 0 0 0 0 0 0 0 0 0 0
2
2
1 1 0 1 1 0 1 1 0 1 1 0 1
1 1 0 1 1 0 1 1 0 1 1 0 1
0 0 0 0 0 0 0 0 0 0 0 0 0
1 1 0 1 1 0 1 1 0 1 1 0 1
1 1 0 1 1 0 1 1 0 1 1 0 1
0 0 0 0 0 0 0 0 0 0 0 0 0
1 1 0 1 1 0 1 1 0 1 1 0 1
1 1 0 1 1 0 1 1 0 1 1 0 1
0 0 0 0 0 0 0 0 0 0 0 0 0
of
this
tiling,
w
b
this
s.he
witnesses.
will
v
b
square
e
remark

indep
vinced
en
that
of
they
alues
regularit
alues
b
e
e
is
extended
alues
to
there
Z
W
the

.
.
y
The
w
The
a
the
y
the
one
erywhere
drops
ha
the
no
english
and
b
us
oard
these
on
not
it
t
yields
linearly
for
the


this
this
witness:
extend
ses
to
reader
yields
the
F
that
in
w

No
v
Z
on
er
initial
Ov
determine
6:
v
Figure
ev
The
as
result
e
is
v
here
just
the
w
same
ed,
.
there
W
th
e
16

But
use
v
this
are
pro
linearly

endan
to
and

are
the
generated
v
y
alues
four
of
e
on
ev
the
use
full
pro
b
to
oard.
the
What
alues
is
Z
the
This
dimension

it.
6V(S, )2
V(S, )2
2 S
V(S, )2
V(S, )2
⊥V(S, )2
V(S, )
− V(S, )I J
F(S, ) F(S, )/2·F(S, )2
˜: F(S, ) → F(S, )
g →g˜ : S → 2
P →g(P) mod 2
V(S, ) V(S, )2
essen
tially
is
4.
is
what
of
is
ab

us
Reiss's
problem
theory
not

linear
though
using
it
the
is

expressed
b
with
of
other
oard
w
F
ords,
giv
and

is
[11]
presen
ossible
t
Or,
in
try

iden
b
with
o
Z
ok
F


W

e
required
sa

y
this
"essen
has
tially"
lik
b
4
ecause
lattice
they
of
do
the
not
y
use
b
an
b
y
with
linear
e
algebra
2;
and
mo
that
w
their
sho
w
p
a
y
y
tral
to
with
reac
with
h
whether
this
(6)
result
with
is
on
b
a
y
This
using
the

w
mo
ev
v

e
v
together
w
with
larger
rev
eral
ersed
that
ones
in
(to
in
undo
and
a
rion
mo
in
v
v
e).
theory
They

obtain
to
what
1
they
y

to

e

Ho
p
test
ositions,
previous
whic
ely:
h
to
is
mo
equiv
y
alen
do
t
3?
to
note
the
ma
equations
to
dening
F
taking
This
y
Z
b
to
obtained
left
F
that
are
the
F
egs,
.
oard
This

is
to
ho
is
w
to
ev
A
er
this
what
basis)
is

presen
sen
ted
scalar
[10


basis
There
witnesses.
are
is
still
when
a
b

is
to
eakly
b
(or
e
en
made:

1.
and
One
e

lea
start
e
from
but
witnesses
dimension
of
than
Z
Sev
dening
examples
,
e

are
them
en
to
[11].
equations
The
and
teger
get
test
witnesses
the
for

this
Thinking
b
h
oard.
terms
This
e,
is
o

Z
the
,
rule-of-three.
lattice
Of
of

is
w
sa
e
that
get
the
only
1
a
should
four
elong
indep
b
endan
imp
t
Z
equations
.
that
w
ma
this
y

not
the
dene
one?
determined,
alternativ
are
w
witnesses

the

F
problem

dulo
us
Wh
formally
not
w
to
questions
so
e
dulo
an
Let
witnesses
rst
of
that
is
e
.
y
enough,
tify
for
wn

e
when
b
there
with
exists
eg.
a
one
dening
only
square
end
from
and
whic
empt
h
Z
all
via
the
square
other

v
for
alues

of
p
the
lled
witnesses
Z

h
b
the
e
start

ossible
this
p
is
it
enough.
determine
2.
is
One


them.
start
During
from
pro
theory
of
This
(a
reader.
Z
the
is
F

to
t
pleasure
pro
and
to
er:
F
the
thic
k
Let
And
state
fully
t
.
o
If
w
the
w
b
t
oard
answ
is
7V(S, ) F(S, )
F(S, )/V(S, )
S
P R S D(S)
P R P ◦ R
A B A≡ B
S
P S Q≡P

S 2F(S, )⊂V(S, )
ˇ ˇ ˇf = P +Q−R ∈D(S)
′ ˇ ˇ ˇf =−P +Q+R
ˇP ∈ S 2P ∈ V(S, ) P
′ˇf 2P = f + f V(S, )
P = P ◦ P ◦ ... ◦ P P0 1 n n
f ∈D(S)i
′ˇ ˇ2P − 2P = f −f i = 0,...,n−1i i+1 i i
′ˇ2P =f +f f ∈D(S)n n nn
′ ′ ′ ′ˇ2P =f −f +f −f +···+f −f +f +f ∈V(S, ),0 0 1 n−1 n0 1 n−1 n
P =P ⋄⋄⋄0
f V(S, )
V(S, ) F(S, )
will
v
erify
this
up
e
h
h
In
yp
relation,
othesis.
w
It
answ
means
w
that
ts

t.
h
er
Most
osed
-equiv
ery

a

on

full
tains
t
a

middle
where
p
transitiv
oin
and
t.
extremities
Ho
also
w
the
ev
the
er
out
the
the
n
whic
um
Theorem
b
ector
er
Q
of
of

w
h
to

Otherwise,
ma
w
y
is
v
a
ary
y
.
The
F
and
or
e
a
for
sucien
ts
tly
,
thic

k
of
b
teger
oard,
w
there
b
will
also
b
questions.
e
will
exactly
on
4
e

required
but
Z
there

ma
oards,
y
the
b
Ho
e
the
more,
a
if
mo
the
,
b
to
oard
b
is
are
not
oin

exists
for
p

if
or
equiv

this
tains
e
thic
p
k
urthermore,

there
ham
e
b
note
ers
e
v
neighb
ery
y
w
,
eakly
mem

ery
b
of
y
p
only
.
one
e
square.
the
The
the
reader
as
will
some
easily
test

.
examples
these
of
reac
b
w
oards
t
with
the
no
this
isolated
will
p
fully
oin
us
t
oard
but
geometry
w
yp
ere
tro
the
w
n
is
um
since
b
Z
er
to
of
sev

of
is
h
larger
Q
than
b
4.
's
The
b
follo
?
wing
)
Theorem
space:
is
lattice

a
tral
Is
move.
v
oards
.
note
then
b
e
full
it,
Let

note
alen
follo
elongs
Lemma
equiv
will
and
e
Z
later:
.
d
there
p
a
oint,
hain
then
o
a
t
of
and
oint

p
an
le
relation
Z
of
midd

the
is
is
middle
which
oin
and
F
oint
b
Z
denition,
p
exists
.
and
A
reexiv
nal
.
notation

b
that
efore
w
sk
ors

are
hing
that
the
sa
pro
w
of:
of
if
b
a
a
exists
ev
e
of
ther
are
,
and
of
oin
oint
o
p
t
every
Finally
for
w
if

t
write
oin
If
p
previous
isolated
in
,
exp
w
witnesses,
e
for
note
theory
no
and
with
linear
e
in
b
Summing
to
all
said
equations,
is
e
d
h
ar
een
o
et
b
link
A
tigh
the
v
rev
exhibit
ersed
will
mo
that
v
turn
e
It
(with
these
equal
er
middle
to
p
enables
oin
that
t).
b
Pro
of
of:
the
W
othesis
e
h
sho

w
in
that
Z
for
sequel,
ev
h
ery
the
4.1

Denition
the
denition:
?
,
.
w

e
This
ha
has
v
eral
e
First
t
all,
ortan

imp
b
an
the
state
-v
w
spanned
no
y

w
Z
(that
e
ould
.
e
If
2.
W
Z
is
in
a
is
middle
whole
p
rank
oin
of
t,
Z
sa
is
y

of
Z
the
in
our
Z
discussion:
of
Theorem
rank.
4.1
us
If
the
1.
wing
is
that
with
b
no
required
isolate
8S |S|≤|D(S)|≤ 4|S|−8
D(S) F(S, )
⋄⋄⋄
S g∈F(S, )
g∈V(S, ) ⇐⇒ g˜∈V(S, ).2

g∈V(S, )+2·F(S, )
V(S, ) ⋄⋄⋄
A B
C D
A B C D
S V(S, )
F(S, )
V(S, /m ) =F(S, /m ) ( m ).
follo
wing
um
maximal
no
Theorem.
and
Theorem
not
4.2
Here
Assume
remains
e
no
to
isolated
b
that
e
2
with
7:
no
squares
isolate
see
d
A
p
if
oint
Z
and
dulo
let
indeed
v
Z
ha
when
e
solv
w
ound,

oard
main
p
Z
,
a
is
.
is
Then
v
As
d
.
oint
readily

ws
from
follo
b
lemma

Z
dd
The
e
t.
(after
oin
of:
p
p
er)
4.1
w
mo
lo
es
(resp.
the
side
one:
left-hand
er
F
pathological
their
total
to
er

on
(Se
,
e
and
(6)
t.
for
dicult
the
this
denition

of
e
es
Theorem
v
o
).
is
Pro
d
of:
and
Indeed,
generates
the
the

ank
implication
ound
is
.
ob
with
vious,
oin
while
situation
the
y
rev
teger
ersed
to
one
y
follo
4.2
ws
w
from
lo
Theorem
Pro
4.1:
we
w
isolate
e
Z
kno
er
w

that
dulo
mo
do
the
not
t
e

problem.
ones,
is


Z
b
v
Figure
(resp.
A
tal
b
horizon
The
the
n
or
b
F
of
.
egs
Z
the
separately
upp
but
the
this
or
last
F
es

is
It
dd
not
the
to
v
that
mo
example

in
v
general
Z
w
and
ha
.
e:
tal
4.3
horizon
b
t
ar
This
.
Theorem
with
tells
isolate
us
p
that
if
the
only
lattice
Q

that
is
Z
not
has
stronger
r
than
in
Reiss's

theory
b
,
er
when
On
prop
oards
erly
no
understo
p
o
ts,
d,
the
and
mo
pro
an
vided
o
w
in
e
is

going
our
giv
atten
an
tion
information;
to
Theorem
non-pathological
implies
b
some
oards.
ork)
In
w

The
[11]
Z
do
.
not
have
ev
oints,
en
d
giv
Z
e
has
a
If
single
whenev
example
space
is
o
Lemma
nothing
but
9F(S, )/V(S, ) /2
F(S, )/V(S, ) /2
I J
+− ∈V (S, ).I J
+V (S, )
D(S)
π
S
ˇ ˇ ˇ∀f =P +Q−R∈D(S), π(P)+π(Q)≥π(R).
+g V (S, )
X
hπ,gi= π(A)g(A)≥ 0.
A∈S
J I hπ, iI
hπ, iJ
ts,
pago
da
b
v
the
functions
r
and
h
the
less
linear
es
test
are
in

non-negativ
one
e
from
rationals
its
The
its
next
as
main
ago
step
dev
tak
with
es
(8)
place
Z
in
get
1961/1962
In
at
oin
Cam
b
bridge
and
univ
to
ersit
er
y
these
when
in
J.H.

Con
in
w
elop
a
on
y
.
led
Z
a
a
group
for
of
Z
studen
It
ts
dicult
(among
wn
whic
the
h

w
mo
ere
with
Beasley)
wn
that
generator
stud-
half-
ied
w
this
in
game.
equations
They
The


out
erties
with
In
another
ell
and
so
dieren

t
or
test,
functions
also


hereafter,
explained
h
in
w

no
and
results
that
of
w

e

no
a
w
is
describ
a
e.
y
This
and
test
elongs
exploits
this
the
is

Z
that

(1)
7,
has
oard
non-negativ
used
e
y

if

e
ts,
with
i.e.
es,
the
isolated
test
is

the
in
to
writing
e
that,
of
if
extreme
w
lines),
e
it

ould
go
e
from
teresting
of
determine
to
for


with
pap
legal
[14
mo
giv
v
prop
es,
of
then

1


w
pro
as
1

5

a
esour
simply
e
is
ounts
Z
p
Z
da
that
are
Q
tro
nally
These
are
functions
examples
on
As

it
that
turns
e
out,
what
of.

pro
e
formal
ha
y
These
an
Z
Q

vide
Z
is
of
pro
of
not
of

pro
.
ys
v
alw
ector
Z
space,
As
and

determining
an
whether

a
function
p
if
oin
b
t
to
b
in
elongs

to
Q
it
,
or
has
not
not
is
to
fast.
that
W
and
e
gure
kno
dra
w
b
generators
for
of
reasoning
this
generalising

(9)
(the
particular,
elemen
one
ts
deriv
of
b
do
ts
e
legal
w
v
so
then
;
p
they
1


b
not
e
than
sho
a

1
kle
in
a
Here

some
(7)
10