Let $ p,q,n$ be three positive integers with $ p + q < n$. Let $ (x_{0},x_{1},\cdots ,x_{n})$ be an $ (n +1)$-tuple of integers satisfying the following conditions :
(a) $ x_{0} = x_{n} = 0$, and
(b) For each $ i$ with $ 1\leq i\leq n$, either $ x_{i} -x_{i - 1} =p$ or $ x_{i} - x_{i - 1} = -q$.
Show that there exist indices $ i < j$ with $ (i,j)\neq (0,n)$, such that $ x_{i} = x_{j}$.
===================
Proof:
We rephrase as follows. $n$ integers are placed on a circle such that when we go clockwise from one number to the next, the difference is either $p$ or $-q$. We want to show that some two integers are equal.
For every arc between two consecutive numbers $x_i$ and $x_{i+1}$, we color it red or blue if $x_{i+1}-x_i$ is $p$ or $-q$, respectively. We go through each of the $n$ windows of $p+q<n$ consecutive arcs. Let window $j$ has $r_j$ red arcs. We see that $$|r_{j+1}-r_j|\le 1,$$ so $r_j=q$ for some $j$, or else the total number of red arcs is not $nq/(p+q)$. Note that $r_j=q$ implies that the two endpoints of these $p+q$ consecutive arcs are associated with the same number.
No comments:
Post a Comment