Рассмотрим лист клетчатой бумаги со стороной клетки, равной 1. Пусть P_k – число всех непересекающихся ломаных длины k, начинающихся в точке O – некотором фиксированном узле сетки. Доказать, что  P_k·3^–k < 2  для любого k.

   Решение

Темы:    [ Правило произведения ] [ Задачи с ограничениями ]

Сложность: 3- Классы: 10,11

Прислать комментарий

Условие

Рассмотрим лист клетчатой бумаги со стороной клетки, равной 1. Пусть P_k – число всех непересекающихся ломаных длины k, начинающихся в точке O – некотором фиксированном узле сетки. Доказать, что  P_k·3^–k < 2  для любого k.

Решение

Первое звено ломаной можно провести четырьмя способами (в каждом из четырёх направлений). Каждое следующее звено можно провести не более чем тремя способами (одно направление уже занято). Поэтому   P_k ≤ 4·3^k–1 < 2·3^k.

Источники и прецеденты использования