Pages

Wednesday, May 12, 2010

Combined Sequence

Let $A,B$ be two distinct positive integers greater than 1, and define the sequences:

$a_m = m + \frac{Bm}{A}, m = 1,2,3,\cdots, A-1$
$b_m = m + \frac{Am}{B}, m = 1,2,3,\cdots, B-1$

And combine those two sequence to form a new sequence $c_1,c_2,\cdots, c_{A+B-2}$ with $c_1 \leq c_2 \leq \cdots \leq c_{A+B-2}$.

Prove that the difference between any two consecutive $c_i$s are less than 2.

Solution

It suffices to prove that for each $a_k$, we can find another $a_i$ or $b_j$ that lies between $a_k$ and $a_k+2$, and vice versa, for each $b_l$, we can find another $a_i$ or $b_j$ that lies between $b_l$ and $b_l + 2$.
Without loss of generality, we may assume that $A > B$.
The distance between two consecutive $b_j$s are $b_{j+1} - b_j = 1 + B/A < 2$, so for each $b_l$, we're guaranteed that $b_l < b_{l+1} < b_l+2$.

Now we're left to consider $a_k$.
Fix $k$, and now take the smallest $l$ such that $b_l > a_k$. This is always possible because:
\[a_k \leq a_{B-1} = (B-1)(1+A/B) < (A-1)(1+B/A) = b_{A-1}\]
(the middle inequality is true because $A > B$.)

If $l$ is the smallest such $l$, that means
\[b_{l-1} \leq a_k \iff (l-1)(1+B/A) \leq k(1+A/B) \iff l/A - k/B \leq 1/A\]

So
\[b_l - a_k = l(1+B/A) - k(1+A/B) = (A+B)(l/A - k/B) \leq (A+B)/A < 2\]
which completes the proof

No comments:

Post a Comment