## Sunday, February 2, 2014

### Flea on a regular polygon

We are given a regular $N$-gon. A flea originally sits on one vertex. At each turn, the flea decides to either jump to the left or to the right to the next (closest) vertex. The flea continues this movement until it has visited all vertices.
Let $a_i$ be a sequence that records the flea's movement. If at $i$-th turn $(i \geq 1)$ the flea moves to the left then $a_i = -1$, and if it moves to the right then $a_i = 1$. We are told that this sequence is finite (i.e. the flea does visit all vertices and therefore stops).
Show that there exists $j,k$ such that:
$$| \sum_{i=j}^k a_i | = N-1$$

Labels:
Combinatorics,
extremal principle,
flea,
gambler's ruin,
sequence

Subscribe to:
Post Comments (Atom)

## No comments:

## Post a Comment