Лёша выписал по кругу 1000 целых чисел так, что любые два соседних числа отличаются на 1. Известно, что число 1 выписано ровно 100 раз, а число −1 выписано ровно 150 раз. Какое наименьшее количество нулей мог выписать Лёша?
Короткое обоснование. Пусть (t_k) — число смежных пар ({k,k+1}) на окружности (неориентированно). Тогда для всех целых (k) [ 2nk=t{k-1}+t_k, ] где (n_k) — число выписанных чисел, равных (k). В частности [ 2n0=t{-1}+t_0,\qquad 2n_1=t_0+t1,\qquad 2n{-1}=t{-2}+t{-1}. ] Отсюда [ n_0=n1+n{-1}-\frac{t1+t{-2}}{2}. ] Чтобы сделать (n_0) как можно меньше, надо максимально увеличить (t1+t{-2}). По неотрицательности (t_1\le 2n1=200), (t{-2}\le 2n_{-1}=300), поэтому максимум (t1+t{-2}=500) даёт формально нижнюю границу (n_0\ge 0). Но если (n_0=0), то нет значений (0) в последовательности и нельзя одновременно иметь положительные и отрицательные числа (чтобы перейти от положительного к отрицательному по шагам (\pm1) нужно проходить через (0)). Так что (n_0\ge1).
Достичь (n_0=1) можно: положим (t0=t{-1}=1), тогда по формулам (t_1=2n_1-t0=199), (t{-2}=2n{-1}-t{-1}=299). Остальные (t_k) можно подобрать так, чтобы суммарно (\sum t_k=1000) и граф с вершинами — целые числа и кратностью рёбер (t_k) был связен; степени всех вершин чётны (равны (2n_k)), значит такой связный эйлеров граф имеет эйлеров цикл, дающий требуемую окружную последовательность. Это обеспечивает существование последовательности с ровно одним нулём.
Итог: наименьшее возможное количество нулей — (\displaystyle 1).
Минимум равен 1.
Короткое обоснование. Пусть (t_k) — число смежных пар ({k,k+1}) на окружности (неориентированно). Тогда для всех целых (k)
[
2nk=t{k-1}+t_k,
]
где (n_k) — число выписанных чисел, равных (k). В частности
[
2n0=t{-1}+t_0,\qquad 2n_1=t_0+t1,\qquad 2n{-1}=t{-2}+t{-1}.
]
Отсюда
[
n_0=n1+n{-1}-\frac{t1+t{-2}}{2}.
]
Чтобы сделать (n_0) как можно меньше, надо максимально увеличить (t1+t{-2}). По неотрицательности (t_1\le 2n1=200), (t{-2}\le 2n_{-1}=300), поэтому максимум (t1+t{-2}=500) даёт формально нижнюю границу (n_0\ge 0). Но если (n_0=0), то нет значений (0) в последовательности и нельзя одновременно иметь положительные и отрицательные числа (чтобы перейти от положительного к отрицательному по шагам (\pm1) нужно проходить через (0)). Так что (n_0\ge1).
Достичь (n_0=1) можно: положим (t0=t{-1}=1), тогда по формулам (t_1=2n_1-t0=199), (t{-2}=2n{-1}-t{-1}=299). Остальные (t_k) можно подобрать так, чтобы суммарно (\sum t_k=1000) и граф с вершинами — целые числа и кратностью рёбер (t_k) был связен; степени всех вершин чётны (равны (2n_k)), значит такой связный эйлеров граф имеет эйлеров цикл, дающий требуемую окружную последовательность. Это обеспечивает существование последовательности с ровно одним нулём.
Итог: наименьшее возможное количество нулей — (\displaystyle 1).