Архив задач олимпиады по математике и криптографии
Робот и 4 направления
В одной из клеток бесконечной клетчатой бумаги находится робот, которому могут быть отданы следующие команды:
вверх (робот перемещается на соседнюю клетку сверху); вниз (робот перемещается на соседнюю клетку снизу); влево (робот перемещается на соседнюю клетку слева); вправо (робот перемещается на соседнюю клетку справа). Если, например, робот выполнит последовательность из четырех команд (вверх, вправо, вниз, влево), то он, очевидно, вернется в исходное положение, т.е. окажется в той же клетке, из которой начал движение. Сколько существует всего различных последовательностей из 4 команд, возвращающих робота в исходное положение?
Для краткости команду влево будем обозначать Л, вправо – П, вверх – В, вниз – Н. Чтобы робот вернулся в исходное положение необходимо и достаточно, чтобы ему было отдано команд Л столько же, сколько и команд П, а команд В – столько же, сколько и Н. Пусть k – количество команд Л в последовательности. Подсчитаем количество Nk искомых последовательностей для k от 0 до 2. k=0. Последовательность состоит только из команд В и Н. Так как их поровну, то на 2 местах из 4 должна быть команда В, а на оставшихся двух – Н. Выбрать 2 места из 4 можно C42 способами. Следовательно, N0=C42=6;
k=1. Каждая из команд Л,П,В,Н встречается в последовательности ровно 1 раз. Число перестановок из 4 элементов равно 4!. Поэтому N1=4!=24;
k=2. Здесь две Л, две П и нет команд В и Н. Две команды Л можно разместить C42 способами. Значит N2=C42=6.
Таким образом, искомое число последовательностей равно N0+N1+N2=36.