IJPAM: Volume 10, No. 1 (2004)

THE STRUCTURE OF COMPLEMENTARY SETS
OF INTEGERS: A 3-SHIFT THEOREM

Aviezri S. Fraenkel$^1$, Dalia Krieger$^2$
$^{1,2}$Department of Computer Science and Applied Mathematics
Weizmann Institute of Science
Rehovot 76100, ISRAEL
$^1$e-mail: fraenkel@wisdom.weizmann.ac.il
$^2$e-mail: daliak@wisdom.weizmann.ac.il


Abstract.Let $0 < \alpha < \beta$ be two irrational numbers satisfying $1/\alpha + 1/\beta = 1$. Then the sequences $a'_n =
\fl{n\alpha}$, $b'_n = \fl{n\beta}$, $n\geq1$, are complementary over $\Zg1$, thus $a'_n$ satisfies: $a'_n = \mmex1\{a'_i,b'_i : 1
\leq i< n\}$, $n\geq1$ ($\mmex1(S)$, the smallest positive integer not in the set $S$). Suppose that $c = \beta-\alpha$ is an integer. Then $b'_n = a'_n+cn$ for all $n\geq1$.

We define the following generalization of sequences $a'_n$, $b'_n$: Let $c,\;n_0\in\Zg1$, and let $X\subset\Zg1$ be an arbitrary finite set. Let $a_n = \mmex1(X\cup\{a_i,b_i : 1 \leq i<
n\})$, $b_n = a_n+cn$, $n\geq n_0$. Let $s_n = a'_n-a_n$. We show that no matter how we pick $c,\;n_0$ and $X$, from some point on the shift sequence $s_n$ assumes either one constant value or three successive values; and if the second case holds, it assumes these values in a very distinct fractal-like pattern, which we describe.

This work was motivated by a generalization of Wythoff game to $N\ge 3$ piles.

Received: September 11, 2003

AMS Subject Classification: 05A17, 91A05

Key Words and Phrases: complementary sequences, integer part function, 3-shift theorem, Wythoff games

Source: International Journal of Pure and Applied Mathematics
ISSN: 1311-8080
Year: 2004
Volume: 10
Issue: 1