Азиатско-Тихоокеанская математическая олимпиада, 1999 год

Найдите наименьшее $n$ такое, что не существует арифметической прогрессии из 1999 вещественных чисел, ровно $n$ членов которой целые.

Комментарий/решение

Назовем:

$l - (n-1) -$ количество промежутков между целыми числами

$k -$ промежуток между числами

$m -$ разница двух соседних чисел

Т.е. если $a$ целое то:

$a+km$ также целое

Значит должны выполнятся 2 условия, независимо от выбора чисел $i$ и $j$:

$j+l(k+1) > 1999$

$a_j -$ первое целое число из последовательности

$j \in [1, \dots, k+1]$

$i+k(l+1) \leq 1999$

$a_i -$ аналогичен $a_j$

$i \in [1, \dots , k]$

$i=k, j=1$

$l(k+1) \geq 1999$ $(1)$

$(l+2)k \leq 1999$ $(2)$

$lk+l-(lk+2k) \geq 0$

$l \geq 2k$

$l(\frac{l}{2} +1)\geq 1999$

$l(l+2) \geq 3998$

$(l+1)^2 \geq 3999$

$l \geq 63$

Допустим: $l<69$

$(1) \rightarrow k \geq 30(l=68)$

$(2) \rightarrow k \leq 29(l=65)$

$l=63,64$

Данные два случая легко опровергнуть подставлением

Значит:

$l \geq 69$

$69k \geq 1930$

$71k \leq 1999$

$k=28$

Ответ: $n=70$