Задача 65323

Темы:    [ Дискретное распределение ] [ Теория графов (прочее) ] [ Принцип Дирихле (прочее) ] [ Предел последовательности, сходимость ]

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

Условие

  На шкуре у Носорога складки – вертикальные и горизонтальные. Если у Носорога на левом боку a вертикальных, b горизонтальных складок, а на правом – c вертикальных и d горизонтальных, будем говорить, что это Носорог в состоянии  (abcd)  или просто Носорог  (abcd).
  Если Носорог чешется каким-то боком о баобаб вверх-вниз, и у Носорога на этом боку есть две горизонтальные складки, то эти две горизонтальные складки разглаживаются. Если двух таких складок нет, то ничего не происходит.
  Аналогично если Носорог чешется боком вперед-назад, и на этом боку есть две вертикальные складки, то они разглаживаются, если же таких двух складок не найдётся, то ничего не происходит.
  Если на каком-то боку две какие-то складки разглаживаются, то на другом боку немедленно появляется две новые складки: одна вертикальная и одна горизонтальная.
  Носороги чешутся часто, случайным боком о случайные баобабы в случайных направлениях.

  Вначале в саванне было стадо Носорогов  (0221).  Докажите, что через некоторое время в саванне появится Носорог  (2021).

Решение

  Построим граф, вершинами которого будем считать состояния Носорога, а рёбрами со стрелками укажем возможные переходы между состояниями и их вероятности.
  Оказывается, всего состояний 8. При этом никакое состояние не является конечным – из любого Носорог может перейти в любое другое. Но вот перейдёт ли? Рассмотрим бесконечную последовательность переходов. Поскольку всего состояний конечное число, в силу принципа Дирихле среди них найдётся такое состояние a, которое встретится бесконечное число раз.

  Из этого состояния есть ненулевая вероятность p_a перейти в состояние  (2021),  не заходя по дороге снова в a. Например, из состояния  a = (3101)  есть цепочка , не проходящая вторично через  (3101).  Следовательно,  p₍₃₁₀₁₎ ≥ 0,25³ > 0.
  Поэтому  q_a = 1 – p_a < 1,  то есть вероятность вернуться из a в a, не заходя в состояние  (2021),  меньше единицы.
  Значит, вероятность события "Носорог никогда не попадает в состояние  (2021)  из состояния a" равна  q_aq_aq_a... = 0.
  Поэтому Носорог обязательно когда-нибудь попадёт в состояние  (2021),  и, значит, такой Носорог будет ходить по саванне.

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

олимпиада
Название	Заочная олимпиада по теории вероятностей и статистике
год
Дата	2011
задача
Номер	15