A problem about pigeon hole principle.

Question

Let $1 < a_1 < a_2 < a_3 < ... < a_{51} < 142.$ Prove that, among the 50 consecutive differences $(a_i − a_{i - 1})$ where $i = 1, 2, 3, ..., 51$, some value, must occur at least twelve times.

My attempt; let $d_i = a_{i+1}-a_i$, so like $d_1=a_2-a_1 , d_2 = a_3 - a_2 ......... d_{50} = a_{51} - a_{50}$ , adding all these, we get $d_1 + d_2 + ..... d_{50} = a_{51} - a_1 \le 139$, now I am not sure what to do, can someone please help?

Thanks!

Answer 1

Hint:

• Suppose you tried to make $d_1 + d_2 + ..... + d_{50}$ as small as possible without having any value appear more than eleven times

• $11 \times 1 + 11 \times 2 + 11 \times 3 + 11 \times 4 + 6 \times 5=140$

Answer 2

Suppose each difference can only appear $11$ times. Then:

$$\sum_{i=1}^{50}d_i \ge (1+2+3+4)\times 11+5\times 6 = 140$$