Задача с собеседования на стажировку в Goldman Sachs

[Alex1976]

1. Ничего личного, но правильный ответ - 7, до тех пор, пока Вы не нашли ошибку в моем решении или не доказали, что правильный ответ - 8.

2. По ссылкам не хожу, в особенности, когда дело касается элементарной задачи.

[mclaudt]

Цитата:

Ничего личного, но правильный ответ - 7, до тех пор, пока Вы не нашли ошибку в моем решении или не доказали, что правильный ответ - 8.

Девочки не ссорьтесь. 8 это с учетом изначального шага - матожидание длины замкнутой траектории. Ответ зависит от того, с какой степенью дотошной упёрнутости относиться к условиям.

Ежу понятно что путь обратно, отсчитанный от первого шага, будет на единицу меньше, чем матожидание замкнутой траектории.

[passenger]

Спасибо всем за помощь, стартовал тогда тему, чтобы оперативно сверить ответ с другими.
На собеседовании решал через систему, аналогичную системе с неизвестными (m, x, y, z).

Есть и другое менее элегантное решение.
Пусть p(k) - вероятность того, что человек от старта доберётся до начальной вершины ровно за k дней.
Очевидно, $p(1) = \frac{1}{3}, p(3) = \frac{4}{27}, p(k) = 0$ для чётных k.

Пусть S(k) - мн-во вершин, до которых мы добрались за k шагов, k > 3.
Сделав ещё два шага, мы в 2 из 9 случаев попадём в начальную вершину, в остальных 7 оказываемся в S(k+2).
Поэтому p(k+2) = 7/9 * p(k).

Пишем формулу для матожидания и получаем ряд:

$E = 1 * \frac{1}{3} + 3 * \frac{4}{27} + 5 * p(5) + 7 * p(7) + ... $

Такой ряд можно посчитать, дважды применив формулу cуммы геометрической прогрессии, ответ E = 7.