ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 65323
Темы:    [ Дискретное распределение ]
[ Теория графов (прочее) ]
[ Принцип Дирихле (прочее) ]
[ Предел последовательности, сходимость ]
Сложность: 4-
Классы: 10,11
В корзину
Прислать комментарий

Условие

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

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


Решение

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

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

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

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

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .