Showing posts with label flea. Show all posts
Showing posts with label flea. Show all posts
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
Thursday, November 12, 2009
Path and Parallelogram
A path from $A$ to $B$ consists of several piecewise straight segments (where $b \neq A$). A flea starts from point $P$ and for each segment, it performs the following operation:
If the segment starts at $X$ and ends at $Y$, and the flea is currently at $Z$, the flea will jump to the point $Z'$ such that $XZYZ'$ is a parallelogram (in that order).
The flea starts from $P$ and performs the operation on the segments sequentially until it is done with the last segment, where the flea is now in $Q$. Prove that $APBQ$ is a parallelogram.
If the segment starts at $X$ and ends at $Y$, and the flea is currently at $Z$, the flea will jump to the point $Z'$ such that $XZYZ'$ is a parallelogram (in that order).
The flea starts from $P$ and performs the operation on the segments sequentially until it is done with the last segment, where the flea is now in $Q$. Prove that $APBQ$ is a parallelogram.
Labels:
Combinatorics,
flea,
Geometry,
jump,
parallelogram,
path,
piecewise,
segment
Subscribe to:
Posts (Atom)