La lecture en ligne est gratuite
Le téléchargement nécessite un accès à la bibliothèque YouScribe
Tout savoir sur nos offres
Télécharger Lire

Laboratoire Bordelais de Recherche en Informatique

De
10 pages
Niveau: Supérieur
Laboratoire Bordelais de Recherche en Informatique, ura cnrs 1 304, Université Bordeaux I, 351, cours de la Libération, 33 405 Talence Cedex, France. Rapport de Recherche Numéro 1157-97 Grain Sorting in the One-dimensional Sand Pile Model Jérôme Durand-Lose labri, ura cnrs 1 304, Université Bordeaux I, 351, cours de la Libération, F-33 405 Talence Cedex, France. Abstract We study the evolution of a one-dimensional pile, empty at rst, which receives a grain in its rst stack at each iteration. The nal position of grains is singular: grains are sorted according to their parity. They are sorted on trapezoidal areas alternating on both sides of a diagonal line of slope p 2. This is explained and proved by means of a local study. Each generated pile, encoded in height dierences, is the concatenation of four patterns: 22, 1313, 0202, and 11. The relative length of the rst two patterns and the last two patterns converges to p 2. We make asymptotic expansions and prove that all the lengths of the pile are increasing proportionally to the square root of the number of iterations. 1 Introduction We consider an innite sequence of stacks. Each stack can hold any nite number of grains, this number is called the height of the stack.

  • model gradian-driven

  • since grains

  • trapezoidal areas

  • grain

  • dimensional lattice

  • labeling grains

  • grain model

  • local interaction


Voir plus Voir moins

Vous aimerez aussi

w
La
of
b
on
oratoire
in
B
[6,
ordelais
aux
de
t
R
is
ec
elfrganized
herc
v
he
spm
en
c
I
the
nformatique
nets
ura
data
cnrs
whic
1
admits
304,
,
Univ
whatev
ersit
olution
Bordeaux
as
I
one
351,
and
cours
b
de
a
la
oneimensional
Lib
and
ation
in
33
gradianriv
405
cessor
T
ely
alence
v
Cedex
gran
France
lik
.

Rapp
and
ort
v
de
w
Rec
in
herc
at
he
h
Numo
hourglass
1157-97
that
Grain
cess
Sorting
i
in
k
the
h
Oneimensional
n
Sand
ab
Pile
[3
Mo
oth
del
they
Je
enco
Durandose
lik

used
l
o
a
used
bri
balancing
,
stac
ura
[12
cnrs
simple
1
lo
304,
all
Univ
same
ersit
imp
Bordeaux
in
I
ts
351,
v
cours
is
de
[2
la
sequen
Lib
g
ation
ha
F
of
405
of
T
ed
alence
cases
Cedex
is
France
spm
.
receiv
Abstract
stac
W
also
e
a
study
w
the
mo
ev
alen
olution
dee
of
bri
a
t
oneimensional
x
pile
a
empt
es
y
to
at
its
st
if
whic
b
h
hips
receiv
v
es
v
a
4].
grain
case
in
dels
its
automata
st
equiv
stac
some
k
Both
at
g
eac
P
h
],
iteration
mo
The
computing
al
of
p
spm
osition
mo
of
dynamic
grains
mo
is
tasks
singular
a
grains
w
are
The
sorted
d
according
and
to
ensiv
their
rearrangemen
parit
ensures
y
cessors
.
almost
They
t
are
spm
sorted
t
on
o
trap
ysics
ezoidal
v
areas
trop
alternating
functions
on
the
b
y
oth
to
sides
=f
of
9,
a
].
diagonal
oneimensional
line
related
of
studied
slop
8].
e
e
p
the
2
al
.
the
This
iterations
is
as
explained
dynamics
and
sequen
pro
problem
v
pap
ed
parallel
b
a
y
empt
means
whic
of
a
a
its
lo
at
cal
It
study
e
.
dripping
Eac
but
h
section
generated
dee
pile
cf
enco
and
ded
are
in
in
heigh
e
t
dripping
dirences

is
bor
the
,
concatenation
o
of
ord
four

patterns
1
22
stac
,
giv
1313
a
,
hip
0202
eac
,
of
and
neigh
11
ors
.
its
The
um
relativ
er
e
c
length
is
of
o
the
e
st
certain
t
alue
w
,
o
In
patterns
oneimensional
and
b
the
mo
last
are
t
cellular
w
and
o
are
patterns
alen
con
via
v
simple
erges
ding
to
spm
p
cf
2
,
.
e
W
etri
e
[11
mak
are
e
to
asymptotic
del
expansions
parallel
and
the
pro
ws
v
information
e
systems
that
is
all
to
the
del
lengths
en
of
load
the
Grains
pile
del
are
or
increasing
and
prop
ks
ortionall
pro
y
net
to
ork
the
].
square
aim
ro
to
ot
a
of
fast
the
relativ
n
inexp
um
e
b
cal
er
t
of
h
iterations
that
1
pro
In
ha
tro
e
duction
the
W
amoun
e
of
consider
ork
an
is
inite
ortan
sequence
for
of
ular
stac
ws
ks
ph
Eac
It
h
in
stac
arian
k
en
can
y
hold
e
an
and
y
eris
ite
soalled
n
criticalit
um
and
b
related
er
the
of
1
grains
phenomenon
this
,
n
10
um
13
b
The
er
tial
is
spm
called
the
the
cf
height
are
of
in
the
7,
stac
They
k
v
The
pro
Sand
ed
pile
uniqueness
mo
the
del
pile
(
er
spm
order
)
the
and
as
Chip
ell
ing
describ
games
the
(
in
cf
arious
g
tial
)
The
are
studied
based
this
on
er
lo
the
cal
ev
in
of
teractions
oneimensional
Both
,
mo
y
dels
st
conserv
h
e
es
the
grain
total
to
n
st
um
k
b
eac
er
iteration
of
can
grains
b
In
seen
spm
sand
,
in
a
thin
grain
long
go
In
es
2,
to
e
a
the
neigh
and
b
g
or
dels
stac
recall
k
they
if
equiv
the
t
heigh
dimension
t
W
dirence
also
b
the
et
pro
w
studied
een
jduranda
stac
.u-
ks
de
is
r
more
httpep
than
inf
a
abr
giv
-b
en
eau
threshold
r
whereas
jdur
in
.
cf
g2
In
e
section
the
3,
(
w
3
e
spm
pro
b
v
is
e
b
that
direct
the
e
generated
;
piles
getting
in

heigh
=
t
n
dirences
4
are
i
made
14
of
pile
four
ks
patterns
0
22
(
,
i
1313
stac
,
the
0202
een
and
)
11
i
.
+
The
of
fron
-
tiers
2
b
1
et
]]
w
7
een
e
patterns
mo
act
sequences
lik
N
e
an
signals
Deiti
The
2
silhouette

of
the
eac

h
i
pile
1
is
y
made
corresp
of
All
t
pro
w
of
o
'
parts

of
this
diren
(
t
i
slop
2
es
2
2
n
then
equal
1
-
.
-
In
h
section
b
4,
]]
grains
i
are
5
mark
3
ed
c
dep
1
ending
1
on
a
their
Since
parit
smaller
y
es
.
the
Ev
an
en
zero
and
b
o
o
dd
ys
grains
(
are
threshold
arranged
n
in
otherwise
a
pile
v
driv
ery
function
sp
=
ecial
2
w
F
a
(
y
+
they
)
are
to
lo
grain
cated
p
in
p
trap
the
ezoidal
are
areas
this
alternating
2
on
b
b
dirences
oth
an
sides
=
of
)
a

diagonal
i
line
transition
of
=
slop
)
e
+
p
(
2
(
.
x
W
+1
e
of
explain
t
this
b
b
is
y
the
lo
b
oking
-
lo
-
cally
6
at
]]
the
2
in
i
teractions
[[
b
1
et
h
w
0
een
d
mo
[[
ving
2
grains
h
and
1
signals
e
In
a
section
3
5,
h
w
1
e
i
giv
c
e
1:
asymptotic
17
appro
are
ximations
ed
of
ks
the
pro
diren
only
t
generated
parameters
pile
W
no
e
t
do
decreasing
this
ensures
b
t
y
w
making
t
a
e
con
alw
tin
ositiv
uous
1
appro
)
ximation
follo
of
8
the
,
pile
=1
and
n
use
.
a
e
diren
dynamics
tial
dripping
resolution
b
as
wing
in
:
[1
)
].
0
W

e
+
pro
<
v

e

that
i
the
2
length

of
i
the
The
part
corresp
of
p
slop
giving
e
the
1
while
is
e
p
to
2
y
times
grain
the
stac
length
stac
of
dated
the
time
part
a
of
Deiti
slop
pile
e
enco
2
the
and
heigh
that
et
the
ks
lengths
pile
of

all
h
the

piles

are
)
increasing

prop
:
ortionally
.
to
ding
the
b
square
)
ro
0
ot
0
of
(
the
2
n
;
um
<
b
)
er
i
of
i
iterations
2
2
2
Deitions
x
The
)
oneimensional
er
sand
grains
pile
constan
is
The
an
um
inite
er
sequence
grains
of
then
stac
to
ks
iteration
Eac
um
h
er
stac
-
k
-
can
-
hold
-
an
[[
y
4
ite
2
n
h
um
2
b
0
er
i
of
c
grains
a
W
6
e
3
use
1
the
h
notation
2
from
2
[8
1
],
i
the
c
dirence
a
is
6
that
2
our
1
mo
h
del
1
is
0
parallel
1
A
i
pile
d
is
b
enco
[[
ded
4
b
2
y
]]
the
h
sequence
1
of
1
the
i
n
f
um
d
b
b
er
Figure
of
Iterations
grains
to
or
.
height
grains
,
only
of
v
the
to
stac
stac
ks
a
It
induction
is
v
then
that
denoted
decreasing
with
are
square
from
brac
initial
k
A
ets
is

w
=
elemen
[[
of

N
0
to

This
1
that
:
heigh
:
dirence
:
et

een
k
y
]]
w
.
consecutiv
W
stac
e
is
call
a
slop
p
e
e
the
on
dirence
Let
of
n
heigh
b
t
the

wing
i
function

n
i
Z
1
(
,
)
b
if
et

w
,
een
0
t
Let
w
b
o
a
consecutiv
The
e
of
stac
with
ks
is
If
en
more
y
stac
follo
ks
transition
are
F
considered
F
the

slop
0
e

is
(
the
0
a
1
v
)
erage
1
slop
0
e
i
If
(
a
)
stac
=
k
i
is

higher

b
+1
y
)
at
(
least
i
t

w
2
o
:
grains
negativ
than
terms
the
ond
next
the
stac
ossibilit
k
of
then
a
one
to
grain
next
um
k
bles
the
do
ositiv
wn
term
This
onds
is
the
depicted
ossibilit
b
of
y
a
the
from
mo
previous
v
k
emen
the
t
ks
of
up
the
at
grains
same
a
making
to
is
f
parallel
in
cess
Figure
on
1.
A
The
can
starting
e
pile
ded
is
y
empt
list
y
the
.
t
A
b
t
w
eac
stac
h
for
iteration
y
a

grain
(
falls
)
on
h
to
(
stac
0
k
1
n
(
um
1
b
2
er
(
1
2
.
3
Grains
:
c
:
to
i
f
With
in
enco
Figure
the
1
function
are
ecomes
the
x
newly
0
arriv
x
ed
2
grains
x
The
2
n
+
um
x
b
+1
er
)
of
1
grains
8
is
0
ite
i
Except
x
for
i
the
x
grain
+
added
x
to
1
the
)
pile
(
at
i
eac
)
h
(
iteration
i
the
2
n
:
um
bHeight
50
0
Piles
alone
dirence
the
of
pro
heigh
the
t
).
of
ends
one
b
b
eha
et
not
w
)
een
e
a
lo
stac
,
k
pile
and
third
the
deitions
next
to
one
it
chip
from
.
j
Deition
for
2
expressed
is
b
equiv
fron
alen
four
t
.
to
and
a
and
stac
ectiv
k
in
ha
on
ving
w
more
going
than
)
t
and
w
2
o
the
c
"
hips
)
and

ing
induction
one
iterations
to
4.
b
and
oth
w
neigh
enough
b
in
ors
4.
This
is
is
patterns
the
11
chip
fr
ing
t
game
the
(
L
cf
the
g
et
).
second
In
They
a
L
oneimensional
e
lattice
of
spm
in
and
estigate
cf
righ
g
if
are
(
equiv
117
alen
96
t
left
with
0
this
ines
enco
osition
ding
ters
the
3

e
1
3
0
on
(
t
)
call
Pro
W
W
e
osition
b
Figure
is
2:
st
Iterations
can
0
in
to
teraction
50
deitions
.
only
Figure
the
2
closest
illustrates
It
the
lo
st
at
50
of
steps
in
of
ose
this
th
dynamic
concatenation
The
with
lengths
,
and
,
heigh
ectiv
ts
e
as
the
w
w
ell
o
as
or
the
of
slop
e
es
M
exhibit
igh
some
ositions
regularit
tiers
y
een
.
st
After
and
some
fourth
iterations
represen
there
4
are
R
t
e
w
mo
o
oth
straps
.
of
giv
triangles
5.
dra
in
wn
h
on
left
the
L
surface
igh
as
is
depicted
j
in
j
Figure
107
3
M
for
ving
iteration
102
100
is
to
t
150
equal
.
1
3
1
T
to
riangles
the
and
true
signals
wing
Piles
p
are
to
enco
righ
ded
(
in
j
heigh
2
t
(
dirences
2
in

Figure
"
4
0
teps
1
1
:
to
of
120).
e
T
v
riangles
prop
app
1
ear
y
with
It
patterns
true
22
the
,
120
1313
as
,
b
0202
seen
,
Figure
and
In
11
as
.
in
Those
1
patterns
2,
are
dep
stable
on
It
t
should
o
b
neigh
e
ors
noted
is
that
to
for
ok
the
cally
second
the
and
teractions
third
the
patterns
tiers
digits
Figure
are
Supp
alternating
that
lik
n
e
pile
in
the
a
of
c
parts
hessb
the
oard
22
and
1313
the
0202
fron
and
tier
resp
b
ely
et
W
w
call
een
ontier
them
limit
is
et
either
een
12
w
or
patterns
30
b
.
der
Let
limits
"
the
b
W
e
denote
the
eft
empt
iddle
y
R
w
t
ord
p
The
of
Kleene
fron
op
b
erator
w
is
resp
denoted
ely
*;
and
that
second
is
third
(13)
and

patterns
is
are
"
ted
or
Figure
13
where
or
and
1313
b
or
v
131313
lik
:
signals
:
ving
:
b
.
sides
W
M
e
Geometric
use
are
the
en
theory
Figure
of
First
languages
e
in
v
the
eac
next
signal
prop
from
osition
to
in
t
order
is
to
left
get
t
a
it
syn
equal
thetic
2
expression
1
Prop
2
ositi
3
on
ines
1
to
The
);
pile
is
enc
mo
o
ines
de
to
d
)
in
R
height
going
dir
igh
enc
if
es
is
is
to
a
j
wor
(
d
j
of
)
the
94
fol
104
lowing
While
language
prop
2
is

only
(
follo
"
encoun
j
are
3
ossible
)
left
(
1
)
12
1
IterationsHeight
150
100
Piles
slop
2
,
.
ts
4
areas
seems
the
ertheless
a
Figure
e
3:
the
Iterations
The
100
diagonal
to
et
150
not
.
e
the
e
left
the
b
explains
order
eling
L
the
b
in
ounces
en
ines
slop
59
in
to
There
65
line
);
as
when
pro
L
b
meets
=
M
b
,
indeed
it
e
b
last
ounces
of
and
of
M
Figure
is
lab
mo
h
v
6,
ed
grains
one
lo
step
lik
to
cated
the
the
righ
2
t
are
ines
oard
81
a
to
kind
87
in
);
1
when
edges
R
6.
meets
an
M
phenomenon
,
separation
it
h
b
e
ounces
2a
and
whic
M
p
is
in
mo
straigh
v
p
ed
2
one
w
step
ha
to
slop
the
.
left
shap
ines
n
50
depicted
to
4
57
Grains
).
according
The
during
order
en
of
In
the
iteration
signals
o
is
sp
k
k
ept
is
and
dd
the
the
only
are
p
trap
ossible
b
encoun
lines
ter
1
with
and
more
These
than
lik
t
c
w
diagonal
o
b
fron
t
tiers
also
is
relation
L
een
-
of
M
slop
-
2
R
and
.
the
The
in
meeting
e
can
v
b
explanation
e
for
exactly
et
sync
the
hronous
a
ines
of
40
its
to
ould
44
=
)
b
or
=
not
b
ines
leads
62
a
to
.
67
v
and
5
103
is
to
line
109
e
).
slop
In
of
all
while
cases
t
the
o
order
parts
is
v
k
a
ept
e
and
1
no
This
other
the
case
e
arises
piles

heigh
The
as
dynamics
in
are
5.
v
Lab
ery
grains
simple
are
except
eled
when
to
signal
iteration
L
whic
or
they
R
ter
reac
pile
hes
Figure
one
at
of
5000
its
all
limits
dd
the
are
rest
otted
are
blac
only
Their
linear
calization
displacemen
singular
ts
o
When
grains
L
e
reac
ev
hes
ones
the
lo
left
on
b
ezoidal
order
delimited
it
y
only
axis
b
of
ounces
e
bac
and
k
,
When
a
R
line
reac
areas
hes
alternating
the
e
righ
a
t
hessb
b
The
order
separation
it
to
b
e
ounces
straigh
bac
line
k
is
and
some
the
of
total
b
length
w
is
the
increased
tersections
b
the
y
of
one
e
When
and
R
with
comes
axis
bac
the
k
in
to
middle
the
depicted
cen
Figure
ter
W
the
do
total
ha
length
e
has
y
b
nor
een
of
increased
this
b
y
y
Nev
one
if
In
diagonal
heigh
is
t
line
dirences
ecause
piles
suc
are
coincidences
the
slop
concatenation
w
of
b
four
a
parts
b
of
(
patterns
+
22
)
,
(
13
+
,
)
02
h
,
to
and
=
11
=
resp
2
ectiv
W
ely
pro
.
e
The
section
t
that
w
it
o
a
st
t
parts
with
ha
e
v
a
22
1
Iterations1
#
2
0
R
0
2
1
2
1
grains
2
1
2
1
3
2
1
1
1
7
4
e
2
3
1
2
5
99
1
0
2
2
6
2
3
2
0
with
1
gr
7
ures
2
left
1
v
1
1
8
3
1
1
2
2
1
2
9
3
3
2
0
1
2
2
10
1
2
0
2
1
0
2
1
2
11
1
2
+
1
deitions
1
by
1
either
12
for
1
their
2
pile
1
pro
1
2
13
3
3
2
0
1
2
91
1
3
14
2
2
1
2
1
0
2
2
3
15
2
2
2
1
1
2
2
0
2
1
2
16
1
1
1
3
1
0
1
1
1
1
3
17
1
3
2
1
0
1
0
1
0
1
1
18
1
2
1
2
G
1
2
1
{
1
and
19
tr
2
and
1
that
2
on
1
dep
1
are
20
an
1
L
3
grains
0
Figure
2
on
1
onds
21
2
3
3
1
87
2
2
0
3
2
1
22
2
2
3
3
1
0
3
2
1
0
1
1
2
23
1
2
2
2
95
2
2
0
2
1
1
1
2
24
2
2
2
2
3
1
2
1
2
1
2
1
0
25
3
2
1
1
1
2
1
1
2
1
2
1
1
26
2
1
1
3
1
0
1
2
2
1
2
1
1
27
3
3
1
1
1
2
1
0
2
2
2
1
0
28
3
2
2
3
1
0
0
2
0
0
1
2
0
29
118
2
0
2
2
2
0
0
2
2
1
0
Figure
1
6
30
6
2
?
2
2
1
,
2
}
0
D
1
1
1
always
31
e
2
of
1
the
3
e
0
alw
1
fron
1
.
1
blac
32
parit
1
y
3
a
1
not
1
represen
1
st
1
a
1
en
33
go
3
other
1
eha
2
v
1
this
1
the
1
en
1
Let
34
1
2
2
3
2
0
1
2
2
1
2
1
1
1
2
35
3
2
1
2
89
2
3
0
1
2
1
1
3
1
1
36
1
2
3
2
1
1
1
2
2
0
2
2
1
1
93
37
3
2
1
1
1
3
2
0
2
2
1
0
2
2
2
38
1
1
2
3
3
1
2
2
97
0
3
2
2
0
1
1
3
39
2
3
2
1
3
3
2
0
2
2
3
0
3
1
2
1
1
40
1
2
0
3
0
1
2
2
3
0
2
1
1
1
2
1
0
L
1
M
2
R
3
40
1
2
1
3
2
1
0
2
1
0
2
1
2
1
1
1
1
41
2
2
1
2
1
3
2
0
3
1
1
1
1
1
1
1
0
42
1
2
2
2
3
2
2
1
1
1
1
1
0
1
1
1
3
43
3
2
2
2
1
1
1
2
0
1
0
1
2
1
3
1
2
44
2
2
2
1
0
3
0
0
116
2
2
1
0
1
0
1
2
45
2
1
0
3
1
1
2
2
1
0
0
2
1
1
2
1
0
46
1
3
120
1
1
3
0
0
1
2
M
0
Represen
2
t
1
-
47

2
2
3
1
1
+
2
1
0
L
2
"
0
2
2
0,
48
5:
2
G
2
L
3
.
0
and
2
ar
0
d
2
ezoid
0
delimite
1
diagonal
49
e
2
,
2
With
2
11,
2
v
0
grains
2
ys
0
of
1
dep
1
parit
50
all
2
are
2
or
2
on
1
.
2
h
0
unkno
1
wn
1
circle
1
h
51
v
2
more
2
b
1
Let
3
that
0
a
1
from
1
order
1
o
1
alternatly
52
wn
2
after
1
depicted
3
Grains
1
e
1
w
1
of
1
F
1
direct
1
es
53
22
1
an
3
w
1
of
2
0
1
0
1
86
1
2
1
1
1
0
54
0
3
0
1
1
3
2
0
1
2
1
1
0
1
0
1
1
1
88
55
1
2
1
3
0
1
0
2
1
0
1
2
1
1
1
1
1
1
0
56
1
2
1
2
90
3
1
0
1
2
0
0
1
2
1
1
1
1
2
57
1
2
1
2
1
2
1
2
1
0
92
2
2
0
1
2
1
1
1
58
1
2
1
2
2
2
2
1
0
2
1
0
1
2
1
0
94
2
2
59
2
2
0
2
1
1
1
3
1
0
2
2
2
0
1
2
0
0
1
1
1
60
96
2
2
1
1
3
0
1
0
2
1
0
1
2
2
0
1
1
1
1
0
61
0
1
1
3
98
1
1
3
1
0
0
2
0
0
0
1
1
1
1
1
1
62
1
3
0
1
0
3
0
1
100
2
1
0
1
1
0
1
0
1
0
1
0
63
101
2
3
3
3
1
2
3
2
0
2
1
1
1
102
1
2
1
1
1
0
64
0
2
0
2
1
3
103
1
2
1
3
1
2
1
2
1
1
1
1
1
104
65
2
2
2
2
0
2
0
2
1
1
1
1
105
1
2
1
2
1
2
1
1
66
1
2
1
2
106
2
2
1
2
2
1
1
1
1
1
1
1
1
107
1
2
67
2
2
2
2
1
1
1
3
1
0
108
2
2
1
1
1
0
1
1
1
1
68
1
2
109
1
2
3
3
1
2
2
2
0
1
2
1
1
110
1
1
1
1
69
0
1
0
3
1
1
1
3
111
0
3
2
3
0
2
2
2
1
2
1
1
70
112
3
1
1
1
3
0
1
0
2
0
0
1
2
113
0
3
2
3
1
2
71
2
2
2
3
2
1
114
3
2
0
1
2
0
0
0
2
0
0
0
2
115
72
2
2
3
2
2
3
2
1
2
2
2
0
1
2
2
0
2
2
3
0
2
1
2
73
2
2
1
2
117
2
2
3
2
0
2
2
2
0
2
2
1
0
1
1
2
1
2
74
2
2
2
2
2
2
1
2
1
2
119
0
2
2
2
0
3
1
2
1
1
1
1
75
1
2
2
2
2
2
3
2
2
1
1
2
1
0
1
1
L
1
R
1
4:
1
tation
76
heigh
2
dirences
2
-
2

1
-
3
D
0
?
1
:G
1
"
1
6
1
D
1
"
77
1
2
1
2

1
M
3

1
1
1
"
1
2
1
-1,
1
1
1
Figure
1
Geometric
78
of
2
,
1
,
3
,
1
M
2
Theorem
1
Odd
1
even
1
ains
1
e
1
sorte
1
in
79
ap
1
ar
3
as
1
d
3
a
0
lines
2
slop
1
1
1
2
1
and
1
axes
1
ures
80
through
3
w
1
pro
3
e
1
the
2
are
0
a
2
on
1
side
1
the
1
tier
1
ending
L
their
M
y
R
In
80
these
3
grains
1
either
3
k
1
white
2
ending
0
their
2
y
1
Grains
1
whic
1
parit
1
is
81
wn
2
dra
3
with
1
little
3
The
0
whic
2
do
0
mo
2
e
1
y
1
are
1
ted
82
y
2
silhouette
2
us
3
consider
1
signal
2
is
0
w
2
y
0
the
2
b
1
Ev
1
and
83
dd
2
come
2
and
2
do
3
the
0
one
2
the
0
as
2
in
0
7.
2
b
1
v
84
lik
2
a
2
a
2
e
2
marbles
2
stairs
0
rom
2
a
0
induction
2
v
0
that
2
pattern
85
corresp
2
to
2
ev
2
dd
2
a
1
e
2
grains
0
5
22a
b
a b
phenomena
only
and
grains
the
Figure
er
6:
10.
P
in
osition
the
of
h
the
is
o
on
dd
9.
grains
order
n
on
blac
w
k
the
2
of
2
of
2
grains
2
no
-
M
-
b
-
part
-
es
-
as
?
hes
!
a
2
k
2
y
2
comparison
2
no
-
in
-
e
-
.
-
v
?
as
-
a
!
parit
2
grains
2
lo
2
R
2
y
-
no
-
of
-
only
?
in
-
R
-
it
!
the
2
three
2
in
2
L
2
left
-
ends
-
y
?
es
-
the
-
new
-
as
!
10.
2
Figure
2
kno
2
that
2
are
-
t
?
a
-
all
-
parit
-
st
-
w
Figure
is
7:
parit
Arriv
st
al
previous
of
e
new
also
grains
of
us
running
consider
that
that
again
signal
W
L
consider
is
When
going
w
righ
the
t
it
As
whatso
depicted
the
in
is
Figure
Signal
8,
the
the
y
w
righ
a
L
v
M
e
v
is
that
just
c
going
of
do
when
wn
6
with
depicted
scarce
Figure
grains
When
running
reac
in
the
fron
b
t
it
of
building
it
la
Going
er
righ
go
t
bac
the
to
signal
middle
L
the
encoun
la
ters
er
the
depicted
middle
Figure
b
In
order
to
M
7,
as
e
depicted
w
in
w
Figure
the
9.
that
The
running
st
fron
grain
of
crosses
w
the
v
b
are
order
of
and
same
b
y
ecause
The
of
grain
the
the
heigh
a
t
e
dirence
of
1
same
,
y
the
the
second
grain
gets
the
lo
w
c
v
k
whic
ed
is
The
the
third
y
passes
the
o
the
v
scarce
er
so
the
the
second
starts
and
and
restrains
ops
the
e
fourth
w
from
signal
passing
.
and
R
so
a
on
a
The
from
phenomena
middle
of
,
one
has
grain
action
getting
ev
lo
since
c
selection
k
grains
ed
made
and
efore
the
R
next
orders
passing
grains
o
la
v
ers
er
the
it
t
one
When
la
or
y
meets
er
it
up
mo
is
es
the
and
w
do
a
not
y
hange
the
dynamic
signal
Figure
L
But
go
all
es
signals
righ
tof
-
represen
-
j
-
Signal
-
sync
-
R
2
dd
2
and
L
of
j
3
3
j
1
-
3
of
1
surface
!
the
-
depicted
-
switc
-
Figure
-
detailed
-
j
2
R
2
j
2
j
L
sync
j
iterations
3
there
1
in
3
j
!
left
-
L
-
are
-
This
-
ev
-
hanges
-
ev
2
link
2
of
2
-
2
0
L
-
j
j
3
-
1
-
Figure
j
8:
2
Signal
M
L
L
go
6,
es
of
righ
separation
t
order
-
en
-
w
-
v
-
3
2
Figure
j
go
3
reac
1
b
j
M
2
meet
0
t
L
Figure
M
the
!
dd
-
grains
-
The
-
the
-
dd
2
grains
2
are
j
to
3
encoun
j
and
0
section
2
2
L
j
M
M
!
!
-
2
-
j
-
L
-
-
-
2
2
1
2
2
2
j
2
L
j
!
0
1
!
2
-
j
-
11:
-
R
2
In
2
separation
2
the
j
at
1
the
2
the
-
middle
!
.
-
as
-
as
2
the
2
symmetric
j
6
1
the
3
1
j
L
0
?
-
10:
-
L
L
es
M
and
!
hes
-
left
2
order
j
,
1
,
3
R
1
things
j
diren
2
as
-
in
-
11.
L
time
M
fate
Figure
o
9:
and
Signal
en
L
are
reac
hed
hes
c
the
in
middle
destination
b
o
order
and
alone
en
-
in
-
6
-
directly
-
ed
-
the
2
hronous
2
ter
2
L
1
R
3
in
1
3.
L
-
j
j
?
1
!
2
-
L
-
R
-
-
-
-
2
-
2
2
1
3
3
0
1
1
3
M
L
!
j
-
?
2
!
2
-
1
-
!
-
-
-
2
2
1
1
2
3
1
1
M
3
-
1
-
L
j
j
3
?
0
!
L
-
R
-
-
-
Figure
1
Signals
3
and
1
exactly
3
hronized
1
Figure
3
the
L
lines
j
t
?
silhouettes
!
piles
-
some
-
and
-
diagonal
-
is
3
trace
1
the
3
b
1
M
3
Since
1
are
L
ev
j
grains
?
o
!
grains
-
t
-
o
-
areas
-
Figure
-
ha
2
e
3
same
1
7
3With
that
2
is
t
they
dd
corresp
1
ond
e
to
the
the
4.
same
p
n
er
um
the
b
2
er
It
of
section
grains
h
5
2
Asymptotic
solutions
b
p
eha
t
vior
er
All
b
the
w
results

in
;
this
r
section
triangles
can
coheren
also
y
b
sides
e
observ
found
GG
in
2
[5].
othesis
The
s
pro
c
of
r
of
2
[5
r
]
or
is
c
to
5,
o
grains
long
is
to
of
t
wing
here
+
w
p
e
n
giv
p
e
+
a
noted
shorter
ha
one
2
that
surface
w
is
e
ev
feel
parted
is
8
more
from
lik
of
e
leads
an

a
2
p
dt
osteriori
h
v
p
eriation
G
Theorem
2
2
t
The
D
diagonal
G
sep
p
ar
t
ation
:
is
the
a
um
line
fallen
of
um
slop
iterations
e
a
p
rom
2
n
.
of
The
is
v
area
alue
the
of
triangles
G
rectangle
increases
the
ecreases
ximations
b
2
y
+
one
(2
for
G
eac

h
+
round
D
trip
G
of
p
L
:
(
b
R
b
).
Figure
The
e
v
area
alue
This
of
with
D
ations
decreases
The
ncreases
parted
b
diagonal
y
and
one
are
(t
b
w
the
o
whic
for
comes
eac
the
h
ations
lo
section
op
It
of
to
L
=
(
1
R
1
).
p
The

round
:
trip
this
dela
yp
y
the
for
ossible
a
are
signal
=
is
p
t
1
wice
2
the
+
length
;
of
=
the
2
part
=
it

ev
2
olv

es
+
in
c
up
Where
to
is
a
time
constan
n
t
b
Since
of
ev
grains
ery
n
quan
b
tit
of
y
and
can
is
go
constan
to
F
init
Figure
y
the
,
um
when
er
G
fallen
and
n
D
also
are
total
v
that
ery
of
big
t
the
o
equations
and
can
the
b
W
e
get
extended
follo
to
appro
con
n
tin
D
uit
2
y
G
as
G
in

[1]:
+
8
2)
>
2
>
G
>
r
<
2
>
p
>
;
>

:
2
dG

=
n
dt
2
2
1
:G
(1)
dt
should
2
e
:D
that
;
oth
dD
of
=
5
dt
v
2
almost
:G
same
+
G
2
.
dt
is
2
t
:D
the
:
observ
These
of
equations
4.
can
rectangle
b
equally
e
b
solv
the
ed
and
with
en
the
o
h
grains
yp
equally
othesis
on
D
oth
=
of
p
diagonal
2
Gde
6
,
Conclusion
an
A
h
more
and
random
op
distribution
(
of
as
o
T
dd
games
and
1996.
ev
583
en
to
grains
v
migh
also
t
Chile
ha
Chile
v
A
e
L
b
L
een
A
exp
ounded
ected
Kiwi
on
M
the
as
con
:
trary
:
grains
the
are
righ
sorted
Ac
This
the
is
the
imp
y
ortan
z
t
w
b
1989.
ecause
of
if
and
ev
Scienc
en
Shor
and
J
o
Sable
dd
and
grains
Picco
or
w
tasks
la
are
219230.
v
piles
ery
.
diren
grains
t
n
in
n
a
2
oneimensional
.
pro
case
cessor
left
arra
feeds
y
the
sequen
patterns
tially
This
fed
b
using
Co
a
w
spm
in
load
acultad
balancing
de
tec
Anderson
hnique
J
disparities
Winograd
arise
a
When
al
tak
Bak
en
criticalit
mo
Physic
dulo
1987.
3
arallel
,
or
5
1992.
,
and
or
graphs
more
,
there
utomates
is
et
no
l
suc
h
h
dynamics
segregated
ccara
lo
A
cation
,
as
E
b
games
efore
n
grains
in
are
[8]
more
line
uniformly
al
spread
::
The
when
w
ks
a
corresp
y
n
grains
0
spread
:::
as
n
a
2)
w
0
a
ectiv
v
is
e
diren
and
ecause
are
of
ed
order
in
high
the
to
silhouette
part
is
hand
v
ed
ery
signal
in
wledgemen
teresting
ork
It
supp
giv
ECOS
es
renc
a
eration
ph
researc
ysical
done
meaning
w
to
Departamen
the
Matemica
signals
Ciencias
When
Univ
L
San
go
[1]
es
Lo
righ
.
t
encer
it
and
spreads
balls
grains
Analysis
When
binatorial
it
an
go
,
es
P
left
T
it
Wiesenfeld
mak
An
es
=f
a
R
one
,
o
J
v
Goles
er
hip
t
graphs
w
al
o
,
selection
A
Signal
v
L
.
is
games
going
op
righ
of
t
1991.
and
Durandose
left
lulair
while
?
the
as
grains
PhD
are
bri
alw
F
a
E
ys
Kiwi
running
oneimensional
to
In
the
Martinez
righ
Cel
t
and
The
ative
signal
211225.
R
1991.
is
and
acting
of
similarly
graphs
.
'92
When
b
it
Lecture
go
Science
es
erlag
righ
Goles
t
Games
it
and
is
or
spreading
Scienc
the
1993.
grains
:
on
But
a
considered
new
stac
la
of
y
they
er
ond
op
:::
ening
n
it
0
When
::
it
and
go
n
es
(
left
1)
it
n
es
:::
them
1
When
::
grains
resp
and
ely
signals
This
are
a
going
ery
in
t
opp
b
osite
of
directions
inence
since
the
they
b
ha
whic
v
is
e
and
sp
grains
eed
the
one
t
signals
On
only
other
meet
they
ev
observ
ery
geometric
other
and
grain
propagations
These
kno
signals
ts
from
w
a
w
ph
partially
ysical
orted
p
y
oin
and
t
F
of
h
view
op
are
in
v
This
ery
h
in
as
teresting
while
b
author
ecause
as
they
the
corresp
to
ond
Ingenier
to
F
w
de
a
Ficas
v
Matemicas
es
ersidad
on
Chile
a
tiago
pile
References
of
R
sand
L
that
v
can
P
b
Shor
e
Sp
seen
E
when
ardos
y
S
ou
Disks
dig
and
at
alls
the
of
b
com
ottom
game
W
meric
e
Mathematic
ha
Monthly
v
96:481493,
e
[2]
pro
.
v
T
ed
ang
that
K
the
Selfrganized
pile
y
is
explanation
expanding
1
in
noise
the
al
square
eview
ro
etters
ot
59(4):381384,
of
[3]
the
Bitar
n
E
um
P
b
c
er
ing
of
on
fallen
The
grains
etic
r
Computer
iterations
e
This
92:291300,
is
[4]
absolutely
Bjner
normal
Lo
when
z
one
P
considers
W
that
Chipring
the
on
grains
Eur
inear
e
are
Journal
ling
Combinatorics
a
12:283291,
surface
[5]
uadratic
O
The
A
relativ
Cel
e
es
length
utomates
of
Partitions
the
T
t
de
w
.
o
thesis
parts
a
is
,
p
In
2
renc
.
[6]
T
Goles
o
M
compare
Sandile
with
in
the
b
w
lattice
ork
Bo
in
Goles
[1
and
],
editors
on
lular
the
utomata
one
Co
hand
er
they
Systems
found
pages
a
Klu
quadratic
er
relaxation
[7]
time
Goles
for
M
the
Dynamics
cf
sandiles
g
on
starting
In
with
tin
the
,
pile
um
:::
er
0
in
0
Notes
n
Computer
0
pages
0
Springer
:
1992.
::
E
and
and
al
Kiwi
pile
on
:::
graphs
0
sand
0
The
1
etic
1
Computer
:::
e
1
115:321349,
1
9
0I
[9]
T
P
al
.
phenomena
Grassb
loadalancing
erger
ctur
and
onen
S
60(23):23472350
Manna
analysis
Some
Symp
more
and
sandpiles
220225,
attice
.
theory
relations
Journal
eview
de
Subramanian
Physique
herson
,
disiv
51(11):1077
a
1098,
on
1990.
A
[10]
r
H
,
Jeager
[13]
S
and
Nagel
Critical
and
and
R
selfrganized
Behringer
al
The
etters
ph
1988.
ysics
and
of
Sc
gran
An
ular
of
materials
e
Physics
In
T
cm
o
osium
day
Par
,
lel
pages
lgorithms
3238,
A
april
chite
1996.
e
[11]
pages
C
1994.
Reutenauer
C
Asp
ang
e
P
cts
Bak
Mathatiques
exp
des
ts
R
scaling
e
for
aux
critical
de
Physic
Pri
R
.
L
Masson
,
1989.
,
[12]
10
R