Шары и корзины

[Sirion]

Пять шаров с номерами от 1 до 5 лежат в пяти корзинах, по одному шару в каждой корзине. Каждые полчаса мальчик Вася выбирает две случайных корзины и меняет местами шары, лежащие в этих корзинах. Неискушённому читателю может показаться, что через некоторое время распределение шаров по корзинам станет полностью случайным, т.е. вероятность встретить i-й шар в j-й корзине окажется равна 1/5 независимо от i и j. Однако это неправда: вероятность того, что шар остался в своей корзине, всегда будет немного больше, а вероятность того, что в корзине окажется чужой шар, соответственно, немного меньше. Разница между этими вероятностями, однако, со временем устремляется к нулю.

Задача: сколько времени пройдёт, прежде чем эта разница станет менее 10^-6?

[moonlight]

У меня получилось Показать скрытый текст

20*0.5=10ч

.
Если ответ правильный, то это задача скорее для другого раздела(не "для программистов"), хотя я считал программой.

[moonlight]

Показать скрытый текст

Пусть вероятность того что некоторый шар окажется в своей корзине после k перестановок равна p_k. Вероятность p_k+1 того что он будет там же после ещё одной перестановки будет равна 0.6p_k+0.1(1-p_k).
0.6-вероятность того что ни одна из 2 выбранных корзин не будет той где шар(если шар в своей корзине), 0.1-вероятность того что будут выбраны корзины одна та где шар находится и вторая "его" корзина(если шар не в своей корзине).

(p_k-0.2)/(p_k+1-0.2)=(p_k-0.2)/(0.5p_k-0.1)=2.
(p₀-0.2)/(p_k-0.2)=2^k
p₀=1.

[Sirion]

Весьма изящно. Я, правда, подразумевал немного другое условие: два выбранных шара могут совпадать. Но это решение можно адаптировать и к такому условию, я полагаю.

Лично я просто возводил матрицу в степень =)

[moonlight]

В этом случае Показать скрытый текст

(p_k-0.2)/(p_k+1-0.2)=5/3.