Ukrainian Mathematical Olympiad

Нехай блоха послідовно побувала в точках: $$a_1=1,a_2,\dots ,a_{2n}.$$ Сума довжин усіх стрибків становить: $$S=|a_1-a_2|+|a_2-a_3|+\cdots +|a_{2n-1}-a_{2n}|+|a_{2n}-a_1|.$$

Зрозуміло, що $$S\le 2(2n+2n-1+\cdots +n+2+n+1)-2(n+n-1+\cdots +2+1)=2n^2,$$ а оскільки за умовою $|a_1-a_2|+|a_2-a_3|+\cdots +|a_{2n-1}-a_{2n}|=n(2n-1)$, то довжина останнього стрибка $|a_{2n}-a_1|$ не перевищує $n$. Оскільки $a_1=1$, то $a_{2n}\le n+1$. Доведемо, що $a_{2n}=n+1$, тобто довжина останнього стрибка дорівнює $n$. Припустимо, що $a_{2n}\le n$. Тоді в послідовності (1) знайдуться два сусідні члени $a_i$ та $a_{i+1}$, кожний з яких більший за $n$. Справді, якщо це не так, то в послідовності (2.1) між $n$ елементами, більшими за $n$, містяться принаймні $n-1$ менших за $n$ елементів, а разом з $a_1=1$ та $a_{2n}\le n$ у (2.1) знайдуться $n+1$ елементів, менших за $n$, що неможливо. Отже, у послідовності (2.1) знайдуться два сусідні члени $a_i$ та $a_{i+1}$, кожний із яких більший за $n$. Перебудуємо послідовність стрибків блохи: $a_1,a_2,\dots ,a_i,a_{2n},a_{2n-1},\dots ,a_{i+1}.$ Для нової послідовності сума стрибків дорівнює $$\begin{array}{rl}{S}^{\prime }& =|a_1-a_2|+\cdots +|a_i-a_{2n}|+|a_{2n}-a_{2n-1}|+\cdots +|a_{i+1}-a_1|=\\ & =n(2n-1)-|a_i-a_{i+1}|+|a_i-a_{2n}|+|a_{i+1}-1|\le 2n^2.\end{array}$$ Проте $1\le a_{2n}\le n<a_i<a_{i+1}$ або $1\le a_{2n}\le n<a_{i+1}<a_i$, і тому неважко перевірити, що $|a_i-a_{2n}|+|a_{i+1}-1|-|a_i-a_{i+1}|>n$, звідки $S^{\prime }>2n^2$. Маємо суперечність. Відповідь: Довжина останнього стрибка дорівнює $n$.