Красивая задачка

[spamsink]

На одной из центральных клеток шахматной доски стоит "ладьекороль" (фигура, которая ходит на одну клетку, но только по вертикали или горизонтали), оставляющий следы на клетках, на которых он побывал. Он делает случайные равновероятные ходы до тех пор, пока на доске не окажется 4 клетки со следами, включая первоначальную. В результате следы образуют одну из пяти (зеркальные считаются идентичными) фигур тетрамино: S, T, O, L, I. Какова вероятность получить каждую из фигур?

Комменты скринятся.

Upd: +kcmamu, +raindog_2, +oldjackaroo +anonymous, +6zow

Comments

[oldjackaroo.livejournal.com]

S: 1/6
T: 1/7
O: 1/6
L: 17/42
I: 5/42

[spamsink]

Нет.

[oldjackaroo.livejournal.com]

OK. Вторая попытка:
S: 4/21
T: 3/21 (=1/7)
O: 4/21
L: 8/21
I: 2/21

[kcmamu.livejournal.com]

(4,3,4,8,2)/21

[raindog-2.livejournal.com]

Из одной клетки всегда получается домино.
Из домино с вероятностью 1/3 получается I - тримино, 2/3 - L-тримино.

Дальше мы начинаем блуждать по тримино, начиная с крайней клетки. Рано или поздно мы с нее выйдем. Если выйдем по центру (с любой) то получится T.
Обозначим вероятность выхода из центра как t.
t = 1/4 * 1/2 + 1/4 * 1/2 * t
откуда t = 1/7.
Итак, P(T) = 1/7
Вероятность выхода с крайней клетки тримино = 6/7.

Чтобы получить I, нужно начать с I-тримино (P=1/3) и выйти "прямо" (P=1/3).
P(I) = 6/7 * 1/3 * 1/3 = 2/21

Чтобы получить О, нужно выйти из L-тримино (P=2/3) и выйти вбок (в определенный бок) (P=1/3).
P(O) = 6/7 * 2/3 * 1/3 = 4/21

Чтобы получить S, нужно, как и для O, выйти из L-тримино, но в другой бок, поэтому
P(S) = P(O) = 4/21

Оставшаяся P(L) = 1 - P(S) - P(T) - P(O) - P(I) = 8/21

Итак, S, T, O, L, I соответствуют
4, 3, 4, 8, 2 / 21.

Я тупой.

[(Anonymous)]

Угу.
Строим стохастический процесс.
Есть переменная/состояние, положение "ладьекороля" в образовавшейся фигуре.
1 промежуточное состояние из двух клеток. (Двоечка, король в крайней)
4 промежуточных состояния из 3-х клеток. (Троечка-прямая <король в крайней, король в центре>, Троечка-уголок <король в крайней, король в центре>).
5 конечных состояний (I,O,S,L,T).

Строим матрицу переходов, строим её замыкание.
Матрица очень разрежённая, но строить замыкание руками - лениво.

Я всё равно тупой...

[(Anonymous)]

Вычислил замыкание.
Как-то так:

I: 2/21
S: 4/21
L: 8/21
T: 3/21
O: 4/21

[6zow.livejournal.com]

I=2/21
L=8/21
S=O=4/21
T=1/7

[mtsyr.livejournal.com]

I 2/21
T 3/21
O 4/21
S 4/21
L 8/21