Suppose the sequence of nonnegative integers $a_1, a_2, \ldots, a_{1997}$ satisfies \[ a_i + a_j \leq a_{i+j} \leq a_i + a_j + 1 \] for all $i,j \geq 1$ with $i + j \leq 1997$. Show that there exists a real number $x$ such that $a_n = \lfloor nx \rfloor$ (the greatest integer $\leq nx$) for all $1 \leq n \leq 1997$.
Problem
Source: USAMO 1997
Tags: floor function, induction, inequalities, algorithm, algebra proposed, algebra
MysticTerminator
27.11.2005 04:26
copied and pasted... Note that in order for $a_n = [nx]$, we must have $x \in [\frac{a_n}{n}, \frac{a_n+1}{n}]$. Thus, there will exist such an $x$ for all $1997$ of the $a_n$ iff none of these intervals are disjoint, i.e. $\forall m, n, \frac{a_n+1}{n} \ge \frac{a_m}{m}$. We will prove this by induction on $m+n$. The base case will be $m+n = 2$, i.e. $m=n=1$, for which the inequality is obvious. Now, we do the inductive step. First, if $m=n$, the inequality is obvious, so forget that case. Now, if $n>m$, use the division algorithm to find $n = mq+r$. Note that $r$ is STRICTLY less than $n$, so $m+r < n+m$ and we can apply the inductive hypothesis: $\frac{a_r+1}{r} \ge \frac{a_m}{m}$ $\Rightarrow a_{mq+r} + 1 \ge qa_m + a_r + 1$ $= qa_m + r \cdot \frac{a_r+1}{r} \ge$ $qa_m + r \frac{a_m}{m} = n \frac{a_m}{m} \Rightarrow \frac{a_n+1}{n}$ $\ge \frac{a_m}{m}$, as desired. If $n<m$, use the division algorithm to find $m = nq+r$, and as $r$ is strictly less than $m$, we have $r + n < m + n$, and we can again use the inductive hypothesis: $\frac{a_r}{r} \le \frac{a_n+1}{n} \Rightarrow na_m = na_{qn+r} \le n(qa_n + a_r + q)$ $\le nqa_n + nq + nr \frac{a_r}{r} \le$ $nqa_n + nq + nr \frac{a_n+1}{n}$ $= nqa_n + nq + ra_n + r = m(a_n+1)$ $\Rightarrow \frac{a_m}{m} \le \frac{a_n+1}{n}$, as desired.
calc rulz
27.08.2007 05:46
As above, we wish to show $ \frac{a_{m}}{m}<\frac{a_{n}+1}{n}\forall m,n\in\{1,2,...,1997\}$
We first prove that we can add as many terms as we like to the sequence so that it still satisfies the above property. We show that given a sequence $ a_{1},a_{2},...,a_{k}$ such that $ a_{i}+a_{j}\le a_{i+j}\le a_{i}+a_{j}+1$ for all $ i,j\ge 1$ with $ i+j\le k$, we can add a term $ a_{k+1}$ at the end so that it still satisfies the same property.
Any such $ a_{k+1}$ must satisfy $ a_{i}+a_{k+1-i}\le a_{k+1}\le a_{i}+a_{k+1-i}+1$ for all $ i$ with $ \frac{k+1}{2}\le i\le k$, so the intervals $ [a_{i}+a_{k+1-i},a_{i}+a_{k+1-i}+1]$ cannot be disjoint, which is equivalent to showing that $ a_{i}+a_{k+1-i}\le a_{j}+a_{k+1-j}+1$ and $ a_{j}+a_{k+1-j}\le a_{i}+a_{k+1-i}+1$ where $ 1\le k+1-i < k+1-j\le j < i\le k$.
For the first inequality we note that $ a_{k+1-i}+a_{i-j}\le a_{k+1-j}$ and $ a_{i}\le a_{j}+a_{i-j}+1$ and add these. For the second we note that $ a_{j}+a_{i-j}\le a_{i}$ and $ a_{k+1-j}\le a_{k+1-i}+a_{i-j}+1$ and add these.
It thus follows that we can pick $ a_{k+1}$ satisfying all the necessary inequalities. We can now add terms past the $ 1997th$ term and still have a sequence that has the desired conditions, meaning that $ a_{i}+a_{j}\le a_{i+j}\le a_{i}+a_{j}+1$ is true even when $ i+j > 1997$.
Now let us consider $ a_{m}$ and $ a_{n}$. We wish to show that $ \frac{a_{m}}{m}<\frac{a_{n}+1}{n}$ or equivalently $ n a_{m}< m a_{n}+m$.
Next we prove that for a positive integer $ r$, $ r a_{m}\le a_{rm}\le r a_{m}+r-1$ using induction. The base case is $ r = 1$ which is clearly true. Assume it's true for $ r$. Then we have that $ (r+1) a_{m}\le a_{m}+r a_{m}\le a_{m}+a_{rm}\le a_{rm+m}\le a_{m}+a_{rm}+1\le a_{m}+r a_{m}+r-1+1\le (r+1) a_{m}+r$ so it holds true in general.
Now we have that $ n a_{m}\le a_{mn}\le m a_{n}+m-1 < m a_{n}+m$ and we are done.
simo14
02.02.2011 04:41
really not sure this is right... is it?
If $a_n=\lfloor nx \rfloor$, $a_n \leq nx < a_n+1 \rightarrow \frac{a_n}{n} \leq x < \frac{a_n+1}{n}$.
If there is truly some $x$ that satisfies $a_n=\lfloor nx \rfloor$ for all $n$, then $[\frac{a_1}{1}, \frac{a_1+1}{1}) \cap [\frac{a_2}{2}, \frac{a_2+1}{2}) \cap \cdots \cap [\frac{a_1997}{1997}, \frac{a_1997+1}{1997}) \neq \{\}$.
Thus, for all $m$ and $n$, $\frac{a_m}{m} \leq \frac{a_n+1}{n}$.
We use induction to prove that for all $n$, $\frac{a_n}{n} \leq \frac {a_j+1}{j}$ for all $j \leq n$.
First the base case, $n=1$. It is obvious that $\frac{a_1}{1} \leq \frac{a_1+1}{1}$, so $\frac{a_1}{1} \leq \frac {a_j+1}{j}$ for all $j \leq 1$
Assume that for all $n \leq k$, $\frac{a_n}{n} \leq \frac {a_j+1}{j}$ for all $j \leq k$.
We must show that for all $n \leq k+1$, $\frac{a_n}{n} \leq \frac {a_j+1}{j}$ for all $j \leq k+1$.
$\frac{a_{k+1}}{k+1} \leq \frac{a_b+a_{k+1-b}+1}{k+1}$ by the given condition.
$\frac{a_b+a_{k+1-b}+1}{k+1} \leq \frac{\frac{a_j+1}{j}+\frac{a_j+1}{j}+1}{k+1}=\frac{2a_j+2+j}{j(k+1)}$ for all $j \leq k$ by the induction hypothesis.
$\frac{2a_j+2+j}{j(k+1)} \leq \frac{a_j+1}{j}$ iff $2a_j+2+j < (k+1)(a_j+1) \rightarrow (k-1)a_j > j-k+1$.
This is true if $j > k-1$. If $j=k$, then $(k-1)a_k > 1$, which is obvious.
Also, $\frac{a_{k+1}}{k+1} \leq \frac{a_{k+1}+1}{k+1}$, so the induction hypothesis implies that for all $n \leq k+1$, $\frac{a_n}{n} \leq \frac {a_j+1}{j}$ for all $j \leq k+1$.
Lastly, to complete the induction step we need to show that for all $n \leq k$, $\frac{a_n}{n} \leq \frac {a_j+1}{j}$ for all $j \leq k+1$.
By the induction step, for all $n \leq k$, $\frac{a_n}{n} \leq \frac {a_j+1}{j}$ for all $j \leq k$. Thus, $
Thus for $1 \leq n \leq 1997$, there exists a real number $x$ such that $a_n = \lfloor nx \rfloor$.
$Q.E.D.$
WolfusA
17.02.2019 15:18
calc rulz wrote:
As above, we wish to show $ \frac{a_{m}}{m}<\frac{a_{n}+1}{n}\forall m,n\in\{1,2,...,1997\}$
We first prove that we can add as many terms as we like to the sequence so that it still satisfies the above property. We show that given a sequence $ a_{1},a_{2},...,a_{k}$ such that $ a_{i}+a_{j}\le a_{i+j}\le a_{i}+a_{j}+1$ for all $ i,j\ge 1$ with $ i+j\le k$, we can add a term $ a_{k+1}$ at the end so that it still satisfies the same property.
Any such $ a_{k+1}$ must satisfy $ a_{i}+a_{k+1-i}\le a_{k+1}\le a_{i}+a_{k+1-i}+1$ for all $ i$ with $ \frac{k+1}{2}\le i\le k$, so the intervals $ [a_{i}+a_{k+1-i},a_{i}+a_{k+1-i}+1]$ cannot be disjoint, which is equivalent to showing that $ a_{i}+a_{k+1-i}\le a_{j}+a_{k+1-j}+1$ and $ a_{j}+a_{k+1-j}\le a_{i}+a_{k+1-i}+1$ where $ 1\le k+1-i < k+1-j\le j < i\le k$.
For the first inequality we note that $ a_{k+1-i}+a_{i-j}\le a_{k+1-j}$ and $ a_{i}\le a_{j}+a_{i-j}+1$ and add these. For the second we note that $ a_{j}+a_{i-j}\le a_{i}$ and $ a_{k+1-j}\le a_{k+1-i}+a_{i-j}+1$ and add these.
It thus follows that we can pick $ a_{k+1}$ satisfying all the necessary inequalities. We can now add terms past the $ 1997th$ term and still have a sequence that has the desired conditions, meaning that $ a_{i}+a_{j}\le a_{i+j}\le a_{i}+a_{j}+1$ is true even when $ i+j > 1997$.
Now let us consider $ a_{m}$ and $ a_{n}$. We wish to show that $ \frac{a_{m}}{m}<\frac{a_{n}+1}{n}$ or equivalently $ n a_{m}< m a_{n}+m$.
Next we prove that for a positive integer $ r$, $ r a_{m}\le a_{rm}\le r a_{m}+r-1$ using induction. The base case is $ r = 1$ which is clearly true. Assume it's true for $ r$. Then we have that $ (r+1) a_{m}\le a_{m}+r a_{m}\le a_{m}+a_{rm}\le a_{rm+m}\le a_{m}+a_{rm}+1\le a_{m}+r a_{m}+r-1+1\le (r+1) a_{m}+r$ so it holds true in general.
Now we have that $ n a_{m}\le a_{mn}\le m a_{n}+m-1 < m a_{n}+m$ and we are done.
The problem I see in this solution is that you proved these intervals are pairwise non disjoint, but you haven't proved that all of these intervals have a common element. Though Helly's theorem makes this insignificant.
WolfusA
20.02.2019 18:41
Actually we don't need $a_i\ge 0$. Assumption they are integers is sufficient.
v_Enhance
22.03.2021 21:09
Solution from Twitch Solves ISL: We are trying to show there exists an $x \in {\mathbb R}$ such that \[ \frac{a_n}{n} \le x < \frac{a_n+1}{n} \qquad \forall n. \]This means we need to show \[ \max_i \frac{a_i}{i} < \min_j \frac{a_j+1}{j}. \]Replace 1997 by $N$. We will prove this by induction, but we will need some extra hypotheses on the indices $i,j$ which are used above. Claim: Suppose that Integers $a_1$, $a_2$, \dots, $a_N$ satisfy the given conditions. Let $i = \operatorname{argmax}_n \frac{a_n}{n}$; if there are ties, pick the smallest $i$. Let $j = \operatorname{argmin}_n \frac{a_n+1}{n}$; if there are ties, pick the smallest $j$. Then \[ \frac{a_i}{i} < \frac{a_j+1}{j}. \]Moreover, these two fractions are in lowest terms, and are adjacent in the Farey sequence of order $\max(i,j)$. Proof. By induction on $N \ge 1$ with the base case clear. So suppose we have the induction hypothesis with numbers $a_1$, \dots, $a_{N-1}$, with $i$ and $j$ as promised. Now, consider the new number $a_N$. We have two cases: Suppose $i+j > N$. Then, no fraction with denominator $N$ can lie strictly inside the interval; so we may write for some integer $b$ \[ \frac bN \le \frac{a_i}{i} < \frac{a_j+1}{j} \le \frac{b+1}{N}. \]For purely algebraic reasons we have \[ \frac{b-a_i}{N-i} \le \frac bN \le \frac{a_i}{i} < \frac{a_j+1}{j} \le \frac{b+1}{N} \le \frac{b-a_j}{N-j}. \]Now, \begin{align*} a_N &\ge a_i + a_{N-i} \ge a_i + (N-i) \cdot \frac{a_i}{i} \\ &\ge a_i + (b-a_i) = b \\ a_N &\le a_j + a_{N-j} + 1 \le (a_j+1) + (N-j) \cdot \frac{a_j+1}{j} \\ &= (a_j+1) + (b-a_j) = b+1. \end{align*}Thus $a_N \in \{b,b+1\}$. This proves that $\frac{a_N}{N} \le \frac{a_i}{i}$ while $\frac{a_N+1}{N} \ge \frac{a_j+1}{j}$. Moreover, the pair $(i,j)$ does not change, so all inductive hypotheses carry over. On the other hand, suppose $i+j = N$. Then we have \[ \frac{a_i}{i} < \frac{a_i + a_j + 1}{N} < \frac{a_j+1}{j}. \]Now, we know $a_N$ could be either $a_i + a_j$ or $a_i + a_j + 1$. If it's the former, then $(i,j)$ becomes $(i,N)$. If it's the latter, then $(i,j)$ becomes $(N,j)$. The properties of Farey sequences ensure that the $\frac{a_i + a_j + 1}{N}$ is reduced, either way. $\blacksquare$
guptaamitu1
17.09.2021 07:10
A different Inductive solution: We will solve the more generally when $1997$ is reaplaced by any natural number $\alpha$, by using strong induction on $\alpha$. Base case $\alpha = 1$ is trivially true. Assume the assertion holds for all $\alpha < \beta$ (for some $\beta \ge 2$) and we consider the case when $\alpha = \beta$. So we have numbers $a_1,a_2,\ldots,a_{\beta}$. Claim: We may WLOG assume $a_1 = 0$. proof: Suppose $a_1 \ge 1$. Then by induction $a_i \ge i$ for all $i$. Then we can change each $a_i$ to $a_i - i$ and $x$ to $x-1$ and note that the condition originally were satisfied if and only if they are now satisfied. So whenever $a_1 \ge 1$, we do this until we get $a_1 = 0$. This proves our claim. $\square$ So now we have $a_1 = 0$. Then for any $i$, $a_i \le a_{i+1} \le a_i + 1$. So the sequence $a_1,a_2,\ldots,a_{\beta}$ will look something like $$0,0,\ldots,0 ; 1,1,\ldots,1 ; 2,2,\ldots,2 ; \ldots$$Assume the number $i$ appears $b_i$ times in $a_1,a_2,\ldots,a_{\beta}$ and let $k$ be the largest such that $b_k$ in non-zero. Note that all of $b_0,b_1,\ldots,b_k$ must be non-zero and $b_0 + b_1 + \cdots b_k = \beta$. Define $$S_m = \sum_{i=0}^{m-1} b_i ~ \forall ~ 1 \le m \le k+1 $$ Claim: for all $i,j \ge 1$ with $i+j \le k+1$ we have $$S_i + S_j \le S_{i+j} \le S_i + S_j + 1$$ proof: We have \begin{align*} & a_{S_{i+j} + 1} = i +j = a_{S_{i} + 1} + a_{S_{j} + 1} \le a_{S_i + S_j + 2} ~ \implies S_{i +j} + 1 \le S_i + S_j + 2 \\ & a_{S_{i+j}} =i+j-1 = (i-1) + (j-1) + 1 = a_{S_i} + a_{S_j} + 1 \ge a_{S_i + S_j} ~ \implies S_{i+j} \ge S_i + S_j \end{align*}This completes the proof of our claim. $\square$ Now we want to prove that the following system of inequalities has a solution: $$x \cdot S_i < i \le x \cdot(S_i+1) ~ \forall ~ i = 1,2,\ldots,k+1 \qquad (1)$$If $k+1 = \beta$, then we must have $b_0 = b_1 = \cdots = b_k = 1$ which would mean $a_i = i-1 ~ \forall ~ i$, and that case is easy. So now assume $k+1 < \beta$. Consider the numbers $$S_1,S_2,\ldots,S_{k+1}$$which satisfy $$S_i + S_j \le S_{i+j} \le S_i + S_j + 1 ~ \forall ~ i,j \ge 1 \text{ with } i+j \le k+1$$By our induction hypothesis, there exist a real number $y$ satisfying \begin{align*} S_i \le y \cdot i < S_i + 1 ~ \forall ~ i =1,2,\ldots,k+1 \\ \implies \frac{1}{y} \cdot S_i \le i < \frac{1}{y} \cdot (S_i + 1) ~ \forall ~ i=1,2,\ldots,k+1 \end{align*}So if we take $x = \frac{1}{y} + \epsilon$ for sufficiently small $\epsilon > 0$, then $(1)$ will be satisfied. This completes the proof of the problem.
GeronimoStilton
11.10.2021 03:25
Replace $1997$ with $N$ and induct on $N$. At $N=1$, the result is trivial. Now, remark that if $a_i+a_j$ with $i+j=N$ is always one of $\lfloor Nx\rfloor$ and $\lfloor Nx\rfloor - 1$, meaning we are done unless $a_i+a_j$ is fixed because then $a_{i+j}$ would have to be $\lfloor Nx\rfloor$. Now first suppose that $a_i+a_j = \lfloor ix\rfloor + \lfloor jx\rfloor = (i+j)x - [ix] - [jx]$ is always equal to $\lfloor Nx\rfloor = Nx - [Nx]$ where $[\bullet]$ is the part of $\bullet$ after the decimal point for nonnegative $\bullet$. Hence $[Nx] = [ix]+[jx]$. In particular, this means that $[ix]\le [Nx]$ for all $i$. We would like to show that $x+\frac{1-[ix]}{i}=\frac{a_i+1}{i} > x$ is larger than $\frac{\lfloor Nx\rfloor + 1}{N} = x + \frac{1-[Nx]}{N}$. Indeed, this is clear because $[ix]\le [Nx]$ and $1>[Nx]$. Now suppose that $a_i+a_j=(i+j)x-[ix]-[jx]$ were always equal to $\lfloor Nx\rfloor - 1 = Nx-[Nx]-1$ so $[ix]+[jx] = [Nx]+1$. It is clear that all $[ix]$ are greater than $[Nx]$. We analogously have $\frac{\lfloor Nx\rfloor}{x} = x - \frac{[Nx]}{N} > x-\frac{[ix]}{i} = \frac{a_i}{i}$, so it is possible to shift the choice of $x$ downward to accommodate the conditions.
MathsLover04
23.12.2022 12:46
It's not hard to prove inductively that \[ia_1\le a_i\le ia_1+i-1\]So, if we denote $b_i=a_i-ia_1$, we have $0\le b_1\le i-1$ and \[b_i+b_j\le b_{i+j}\le b_i+b_j+1, \forall i+j\le 1997\]However, \[a_n=\lfloor nx\rfloor\Leftrightarrow a_n\le nx< a_n+1\Leftrightarrow nx-1< a_n\le nx\Leftrightarrow x-a_1-\frac{1}{n}< \frac{b_n}{n}\le x-a_1\]So it is enough to prove the existence of some $y$ satisfying \[\frac{b_n}{n}< y\le \frac{b_n+1}{n}\]If we manage to prove that $\frac{b_m}{m}\le \frac{b_n+1}{n}, \forall m,n$, then the intervals $\left(\frac{b_i}{i}, \frac{b_i+1}{i}\right]$ are not disjoint and we can take $y$ from their intersection. Proceed by induction on $m+n$. The base case is trivial, since $b_1=0$. Suppose the statement true for any $(i,j)$ with $i+j<m+n$. If $m<n$, then write $n$ as $m\cdot c+r$, with $r<m$. We know, by the induction hypothesis that \[\frac{b_m}{m}\le \frac{b_r+1}{r}\]On the other hand, we also know that $b_r+cb_m\le b_n$. So we have \[b_n+1\ge b_r+cb_m+1=cb_m+r\cdot \frac{b_r+1}{r}\ge cb_m+r\cdot \frac{b_m}{m}=n\cdot \frac{b_m}{m}\Rightarrow \frac{b_n+1}{n}\ge \frac{b_m}{m}\]If $m>n$, then write $m$ as $n\cdot c+r$, with $r<n$. We know that \[\frac{b_r}{r}\le \frac{b_n+1}{n}\]and also that $b_m\le b_r+cb_m+c$. So we have \[b_m\ge r\cdot \frac{b_n+1}{n}+c(b_n+1)=\frac{b_n+1}{n}\cdot m\Rightarrow \frac{b_n+1}{n}\ge \frac{b_m}{m}\]If $m=n$, the inequality is obvious. So the induction is done and the problem is now finished.