3

Let $a_1<a_2<...<a_{43}<a_{44}$ be positive integers not exceeding $125$. Prove that among the $43$ differences $d_i = a_{i+1}-a_i$, $i=1,...,43$ some value must occur at least $10$ times.

I succeeded to obtain that $$43\leq\sum_{i=1}^{43}d_i\leq 125$$

Is it possible the use the pigeonhole principe to conclude this question? Otherwise, can anyone help me to finish it?

1 Answers1

4

Observe that, assuming that $a_1>0$ $$\sum_{i=1}^{43} d_i=a_{44}-a_1<125$$ Suppose now that each values of $d_i$ occurs at most nine times. Then the minumum value for $\sum d_i$ is obtained by taking 9 times each values $1,2,3,4$ and the remaining 7 times the value 5, for a total of $$(1+2+3+4)\cdot 9+5\cdot 7=125$$ absurd.

Capublanca
  • 1,262
  • If you want to minimize $\sum d_i$, without using 10 times the same values, you obtain for the sequence $a_n$ something like: 1-2-3-4-5-6-7-8-9-10...now i used 9 times the difference 1, so i start to use the difference 2, so i get...12-14-16-18-20-22-24-26-28-30...now i start to use difference 3 and so on. In this way you can observe that $a_{44}=126$, absurd. – Capublanca Sep 13 '15 at 17:33