вотэтазадача 18. Прыжки по клеточному полю

Когда-то на досуге придумалась такая нехитрая комбинаторика.

За один ход саранча прыгает в одну из четырех сторон: вверх, вниз, вправо или влево на метр. Сколько различных путешествий длиной в 2n ходов с началом и концом в одной точке может совершить саранча? Ответ не должен содержать сумм.

Задача не сложная, но по некоторым причинам, связанным с самодвойственностью двумерного куба, задача оказывается проще в 2d чем в 3d.

Ну и заодно вопрос: как бы так посчитать количество возможных путешествий из точки (0,0) в точку (x,y)?

1 комментарий:

  1. Ответ (C_{2n}^n)^2.

    Довольно забавный способ: перевернуть всю картинку на 45 градусов. Тогда, каждым ходом саранча выбирает одно из четырех диагональных направлений: ЛВ,ЛН,ПВ,ВН (Л=лево,В=верх,П=право,Н=низ), то есть каждый раз происходит независимый выбор направления по вертикали и по горизонтали. Если рассматривать только горизонтальное направление, то последовательность ходов кодируется строчкой вида ППЛПЛ..., где всего букв 2n, из них n П и n Л. Таких строчек бывает C_{2n}^n. Аналогично, последовательностей вертикальных ходов бывает C_{2n}^n, откуда получается ответ.

    Этот алгоритм (поворот на 45 градусов) позволяет решать задачи вроде: сколько путей из точки (0,0) в точку (a,b) может сделать саранча. По другому --- хрен решишь.

    Забавно, что трюк с поворотом не работает для 3D. Можно легко посчитать число ходов для саранчи, которая делает ходы по диагонали (ее естественно называть кубической саранчой). Однако, саранча которая делает ходы вдоль координатных осей (октаэдрическая саранча) --- это уже другой тип саранчи и для нее так просто посчитать число маршрутов не получается. Про кубоктаэдрическую саранчу (делает ходы по диагоналям в координатных плоскостях) я пока не думал. А ведь бывает еще саранча гексагональная, типа A_n, пермутоэдрическая и много еще какая!

    ОтветитьУдалить