Олимпиадная задача

[sa233091]

Найти кол-во таких строк из 1 и -2, чтобы сумма любого кол-ва первых элементов слева была неотрицательной. Длинна строки 16.

[gris]

В. И. Ленин. "Шаг вперёд — два назад". Главное, за шестнадцать минут не свалиться в пропасть. Блуждания на отрезке.

[sa233091]

gris в сообщении #1163740 писал(а):

В. И. Ленин. "Шаг вперёд — два назад". Главное, за шестнадцать минут не свалиться в пропасть. Блуждания на отрезке.

это название статьи?

[gris]

Похоже. Мне просто увиделась интерпретация задачи в виде блужданий по целочисленным точкам на прямой. В очередной момент времени мы можем уйти на шаг вправо или на два влево. Можно результат записывать в виде строки с промежуточными пунктами (то есть суммами).
$(1, 1 ,-2, 1, 1, -2, 1, 1, 1)\sim(1, 2, 0, 1, 2, 0, 1, 2, 3)$
или изображать на плоскости.

[worm2]

A126042(16)

-- Пт окт 28, 2016 16:32:12 --

Но это не решение, я просто подглядел ответ

-- Пт окт 28, 2016 16:44:36 --

Можно ещё так: на доске выписан многочлен 1.
На каждом шаге то, что написано на доске, умножается на $x+x^{-2}$ и отбрасываются иксы в отрицательных степенях (получается снова многочлен).
Стало быть, то, что получилось после 16 шагов, тоже есть многочлен, ответом является его значение в точке $x=1$.

[svv]

sa233091 в сообщении #1163746 писал(а):

это название статьи?

Ну, типа.

[gris]

V.I. Lenin писал(а):

One step forward, two steps back: The Crisis in Our Party .

OEIS in A126042 писал(а):

One step forward and two steps back: number of nonnegative walks of n steps where the steps are size 1 forwards and size 2 backwards.

Идеи Ленина живут и побеждают. В общем, задача известная и изученная. Как-то облегчить её для случая $n=16$, вероятно, не получится.

[Lia]

Тема перемещена из форума «Олимпиадные задачи (М)» в форум «Карантин»
по следующим причинам:

- неинформативный заголовок;

Исправьте все Ваши ошибки и сообщите об этом в теме Сообщение в карантине исправлено.
Настоятельно рекомендуется ознакомиться с темами Что такое карантин и что нужно делать, чтобы там оказаться и Правила научного форума.