Laboratoire Bordelais de Recherche en Informatique

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