$x$ is equal to at least $51$ of $a_1,\frac{a_1+a_2}{2},\ldots,\frac{a_1+a_2+\ldots+a_{100}}{100}$. Prove that $2$ of $a_1,\ldots,a_{100}$ are equal.

Question

If $x$ is equal to at least $51$ number of the array $a_1, \frac{a_1+a_2}{2},\ldots,\frac{a_1+a_2+\ldots+a_{100}}{100}$, prove that $2$ numbers of the array $a_1,a_2\ldots,a_{100}$ are equal.

That's the way the problem is originally stated. It doesn't tell me whether at least or exactly $2$ numbers of the array $a_1,a_2\ldots,a_{100}$ are equal.

I've thought of a way to define the problem in a different way:

If $n_1,n_2,\ldots,n_{100}$ is an array of distinct natural numbers that belong to the interval $[1\:;100]$ and $k\in\mathbb N$, $k\le50$ and $\begin{cases}n_1x=a_1+a_2\ldots+a_{n_1}\\n_2x=a_1+a_2\ldots+a_{n_2}\\\ldots\\n_{50+k}x=a_1+a_2\ldots+a_{n_{50+k}}\end{cases}$, prove that $2$ numbers of the array $a_1,a_2\ldots,a_{100}$ are equal.

I have no idea at the moment how we could come up with a proof that $2$ numbers of the array $a_1,a_2\ldots,a_{100}$ are equal. Some ideas would be great. Thanks.

Answer 1

This should work

Let $b_i$ denote the $i$th term of the sequence.

By pigeonhole principle, at least two consecutive terms $b_n, b_{n+1}$ are equal.

If $n$ is even, then necessarily at least one other pair of consecutive terms are equal. If $b_k, b_{k+1}$ are equal, then it can be shown that $a_{n+1} = a_{k+1}$

If $n$ is odd, then it can be that $b_n, b_{n+1}$ is the only pair. If it wasn't, then we can conclude similarly as above. So consider $b_n, b_{n+1}$ being the only pair. $b_1 = a_1$ must be one of the terms equal to $x$ (the terms equal are $a_1 = a_3 = \dots = a_n = a_{n+1} = a_{n+3} = \dots = a_{100}$). Furthermore, $\frac{a_1 + a_2 + a_3 + \dots + a_n}{n} = \frac{a_1 + a_2 + a_3 + \dots + a_{n+1}}{n+1}$, so $a_{n+1} = \frac{a_1+a_2+a_3+\dots+a_n}{n} = x$. Thus, $a_{n+1} = a_1$. $\blacksquare$

Btw, do you know where this problem is from? Seems like a 1990s USAMO problem.

Answer 2

Let $I$ be the set of all $0 \le n \le 100$ such that $x_1 + \cdots + x_n = nx$. Note that $0$ does belong to $I$, and so do the $51$ (or more) other values stated in the hypothesis, so $|I| \ge 52$.

Since $I$ is a subset of $\{0, \ldots, 100\}$ with size at least $52$, it must contain at least two pairs of consecutive elements. In other words, there are distinct $m,n$ such that $m, m+1\in I$ and $n, n+1 \in I$. (One way to see this cleanly is to consider the spacings between the first $52$ elements: there are $51$ spaces totaling at most $100$, so at least two of the spacings must be $1$ rather than $\ge 2$.)

Notice that whenever $r,r+1 \in I$ we have that $a_{r+1} = x$ (since you're confused you may want to double-check that this holds for $r=0$, but it really is the same calculation as any $r$). Thus with $m$ and $n$ chosen as above, we have $a_{m+1} = a_{n+1} = x$.

Answer 3

Let $$A=\{\,k\in\mathbb N_0\mid k\le 100,a_1+\ldots+a_k=kx\,\}.$$ Then $A$ contains not only the 51 given indices, but trivially also $0\in A$, i.e. $|A|\ge 52$. Let $B= (\mathbb N\setminus A)\cap (A+1)$. Then $A\cap B=\emptyset$ and $A\cup B\subseteq \{0,1,\ldots,101\}$ imply $$\tag1|A|+|B|\le 102.$$ For each $k\in (A+1)\cap A$ we have $1\le k\le 100$ and $$ a_k=(a_1+\ldots+a_k)-(a_1+\ldots a_{k-1})=kx-(k-1)x=x.$$ Now $$(A+1)\cap A=(A+1)\setminus(\mathbb N\setminus A)=(A+1)\setminus B $$ and $$ |(A+1)\setminus B|\ge |A+1|-|B|=|A|-|B|\ge 2|A|-102\ge 2$$ Shows that there are at least two indices $k$ with $a_k=x$.

Answer 4

One can say slightly more, not only two of those $a_i$ are equal, actually two of them equal $x$.

Clearly if two consecutive running averages are equal to $x$, then the term added in the second running average was equal to $x$. One obviously cannot select $51$ out of $100$ running averages without this happening at least once (every selected average except the last would block its successor from selection, which gives $50\times2+1$ selected or blocked averages, one too many). If it actually happens more than once, then we have got our two instances of $a_i=x$. But if one wants it to happen just once, then by a similar argument, every one of the $100$ running averages is either selected or the successor of a selected average, the two conditions being satisfied simultaneously just once. But that means the very first running average was selected, making $a_1=x$, which together with the instance $a_i=x$ for the index $i$ that was both selected and the successor of a selected index gives our two instances.

One can avoid the case distinction by adding a running average $0$ declared to be equal to $x$ (with which the argument "two consecutive averages equal to $x$ implies the second $a_i=x$" remains valid), and argue for at least two pairs of consecutive chosen averages. This is essentially the answer by Eric Wong. I just wanted to show that one arrives at the conclusion also using only rather fantasy-less reasoning.