Prove that among the numbers $d_1=x_2-x_1, d_2=x_3-x_2,...,d_{101}=x_{201}-x_{101}$ at least $26$ equals.

Question

Let $x_1<x_2<...<x_{102}\le254 -$ positive integers. Prove that among the numbers $d_1=x_2-x_1, d_2=x_3-x_2,...,d_{101}=x_{102}-x_{101}$ at least $26$ equals.

Tell me how to solve this problem. I have no idea how to solve this problem.

Answer 1

Observe that: $\sum_{i=1}^{101} d_i=x_{102}-x_1\leq 253$.

Now, note that in sequence $(d_i)_i$ you have 101 elements, all of them are positive (!) integers. Assume the opposite, i.e. there are at most $25$ equal elements in this sequence. Let us find a lower bound on the sum $\sum d_i$.

There are at most 25 elements equal 1, at most 25 elements equal 2, etc., so $$\sum_{i=1}^{101} d_i\geq 25*1+25*2+25*3+25*4+5,$$ the last element comes from the observation that we have 101 $d_i$'s.

But then $\sum_{i=1}^{101}d_i\geq 255$, which is a contradiction. Therefore, there must be at least 26 equal elements in $(d_i)^{101}_{i=1}$

Answer 2

The main idea is that a lot of the differences have to be the same. Why? Because $102$ integers are squeezed between $1$ and $254$ so there can't be too many big jumps. Now we formalize this idea.

Let $\Delta_i$ = $x_{i +1} - x_i.$ Thus, $$x_{102} = (x_{102} - x_{101}) + (x_{101} - x_{100}) + \cdots + (x_2 - x_1) + x_1 = \sum_{i = 1}^{101} \Delta_i + x_1.$$

Let $S = \sum_{i = 1}^{101} \Delta_i$. The equation above tells us

$x_{102} = S+ x_1 \le 254.$ Since $x_1 \ge 1$, we have $S \le 253.$

Now suppose that each $\Delta_i$ can be repeated at most $25$ times. Since there are $101$ $\Delta_i$ values, we have $$S \ge 1 \cdot 25 + 2 \cdot 25 + 3 \cdot 25 + 4 \cdot 25 + 1 = 255.$$

This contradicts $S \le 253$ which means that $26$ of the $\Delta_i$ values are equal.

Answer 3

In this problem each x_i is positive integer and they are ordered in strictly increasing manner.So,the least value that d_i can take is 1.If we can show that without permitting a minimum of 26 same values of d_i's we can not accommodate all of the x_i's 0

Answer 4

Suppose there is just $25$ equal $d_i$. The minimun possible is $x_{k+1}-x_k=1$ for $k=1,2,...,25$ and $x_{26}=26$.

Now in order to have the other $d_{26+k}$ distinct we must have at the minimum case $x_{27}=28,x_{28}=31,x_{29}=35$ an so on, for which we have $d_{27}=2,d_{28}=3,d_{29}=4...$ This would give $$x_{102}-x_{101}=\frac{76\cdot77}{2}=2926$$ This is impossible because $x_{101}\lt x_{102}\le 254$.

Thus, in this minimal case there are at least two of the $d_i$ equal.

Answer 5

First thing I notice is $x_{102} > \sum d_i$. This is intuitive to me because to get to from one $x_i$ to the next we have to add an $d_i$ to the $x_i$ so the last $x_i$ is greater than the sum of all $x_i$. But to prove it formally:

$\sum d_i = \sum_{i=2}^{102}(x_i - x_{i-1})$ which is a telescoping sum.

$\sum_{i=2}^{102}(x_i - x_{i-1})= \sum_{i=2}^{102}x_i - \sum_{i=2}^{102}x_{i-1}=$

$\sum_{i=2}^{102}x_i - \sum_{i=1}^{101}x_{i} = x_{102} - x_1$

which is actually stronger and more specific than I first thought.

To prove that there are two equal anything, just screams "pigeon hole" principal at me. To prove a "pigeon hole" result I usually assume everything is different and show that results in something not fitting.

So what happens if at most there are 25 equal $d_i$. Well then there must be at least 76 with different values. If there are 25 of a second value, and 25 or a third and four. There must be at least four different values. And one fifth value.

If I make these 4 values as small as possible (1,2,3,4) what happens? Well the sum of those must be at least some minimum value.

$\sum d_i \ge 25*1 + 25*2 + 25*3 + 25* 4 = 250$.

250 is very close to the maximum, I allowed $\sum d_i < x_{102} \le 254$.

Well, I've accounted for 100 of the differences so there is one more. It must be at least $5$. So $\sum d_i \ge 255$ which is contradiction.

Of, course I have to convince myself that $25*1 + 25*2 + 25*3 + 25* 4 + 5$ is the lowest possible sum. Which is obvious if I replaced any $d_i$ I'd have to replace it with something larger.