Информация о задаче

Задача 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