Let $A$ be a finite set of pairs of real numbers such that for any pairs $(a,b)$ in $A$ we have $a>0$. Let $X_0=(x_0, y_0)$ be a pair of real numbers(not necessarily from $A$). We define $X_{j+1}=(x_{j+1}, y_{j+1})$ for all $j\ge 0$ as follows: for all $(a,b)\in A$, if $ax_j+by_j>0$ we let $X_{j+1}=X_j$; otherwise we choose a pair $(a,b)$ in $A$ for which $ax_j+by_j\le 0$ and set $X_{j+1}=(x_j+a, y_j+b)$. Show that there exists an integer $N\ge 0$ such that $X_{N+1}=X_N$.
Problem
Source: Indian Team Selection Test 2015 Day 4 Problem 2
Tags: algebra
17.11.2015 16:08
Observe that $x_i$ is obviously unbounded. Thus we can assume $x_j>0$ for some $j$ If we can prove $y_i$ is bounded, we are done. Let $y_j<0$ Then for all $b <0$, $ax_j+by_j>0$ $\implies y_{j+1} = y_j+b$ for some $b>0$ Thus either $|y_{j+1}<|y_j|$ Else $y_{j+1}$ changes sign that is becomes positive and thus, $|y_{j+1}| < max|b_k|$ We can show symmetric result for $y_j>0$ Thus we easily get $-(\sum|b|+|y_0|)<y_j<\sum|b|+|y_0|$ That is $y_j$ is bounded. Hence we are done.
18.11.2015 02:23
utkarshgupta wrote: Observe that $x_i$ is obviously unbounded. Thus we can assume $x_j>0$ for some $j$ If we can prove $y_i$ is bounded, we are done. Let $y_j<0$ Then for all $b <0$, $ax_j+by_j>0$ $\implies y_{j+1} = y_j+b$ for some $b>0$ Thus either $|y_{j+1}<|y_j|$ Else $y_{j+1}$ changes sign that is becomes positive and thus, $|y_{j+1}| < max|b_k|$ We can show symmetric result for $y_j>0$ Thus we easily get $-(\sum|b|+|y_0|)<y_j<\sum|b|+|y_0|$ That is $y_j$ is bounded. Hence we are done. At the actual TST one thing I found was that it had a nice combinatorial interpretation if you consider it as moving a point in the cartesian plane with some rules.($ax+by$ motivates a "line") Now, the idea of $(y_n)_{n\in\mathbb{N}}$ being bounded follows automatically by considering the distance between the jumps and since the area of movement is an unbounded region and the jumps cross it over and over we will conclude. I know, what I just said hardly makes sense when put this way, but try it by making a figure and it's pretty natural where all this comes from. On a side note this was probably my second favorite TST Problem other than IMO SL 2014 C1.
27.05.2019 05:23
Nice problem! Suppose not. Let $|A| = k$, and let the elements of $A$ be $(a_1, b_1), (a_2, b_2), \ldots, (a_k, b_k)$ where $b_1 \leq b_2 \leq \cdots \leq b_k$. Define a function $f: \mathbb{N} \to \mathbb{N}$ as follows: for each $i \geq 0$, $f(i)$ is the positive integer such that $\left(x_{i + 1}, y_{i + 1}\right) = \left(x_i + a_{f(i)}, y_i + b_{f(i)}\right)$ (which must exist by hypothesis). Since $a_t > 0$ for all $t$, we must have $x_{i + 1} > x_i$ for all $i$. Thus, for $i$ large enough, $x_i > 0$. Pick $i$ such that $x_i > 0$. If $y_i = 0$, $x_ia_{f(i)} + y_ib_{f(i)} = x_ia_{f(i)} > 0$ (since $x_i$ and $a_{f(i)}$ are both positive), contradiction; thus, $y_i \neq 0$. Suppose $y_i > 0$. Since $x_ia_{f(i)} + y_ib_{f(i)} \leq 0$ (by the problem condition), we must have $b_{f(i)} < 0$, which also implies that we must have $b_1 < 0$. Hence, $y_{i + 1} = y_i + b_{f(i)} < y_i$. Similarly, if $y_i < 0$, we must have $y_{i + 1} > y_i$, implying that $b_k > 0$. Together, these two conditions are enough to imply that the sequence of $y_i$ is bounded both above and below. In particular, this implies that the set of products $y_ib_t$, where $i$ and $t$ are arbitrary indices, is bounded above and below. However, the set of products $x_ia_t$ grow arbitrarily large. Thus, for $i$ large enough, we will have $x_ia_t + y_ib_t > 0$ for all $t$, contradiction. $\Box$