Каким образом значение T (1,0) = T (0,1) = 3 в задаче «Случайная овчарка»?

Question

Я рассмотрел приведенный ниже вопрос о кодировке. Я не мог решить это самостоятельно. Итак, я прошел анализ. Я знаю, что T (0,0) = 0, потому что овце не нужно делать никаких ходов. Но я не понял, как T (1,0) = T (0,1) = 3? Чтобы решить рекуррентное отношение, мне нужно знать значение T (1,0) или T (0,1), равное 3. Может ли кто-нибудь объяснить меня ясно? Любая помощь будет оценена по достоинству.

https://codingcompetitions.withgoogle.com/codejamio/round/0000000000050fc5/0000000000054edd

Answer 1

Если овца находится в (0, 1), одна овчарка поместит себя в (0, 2), а другая - в (-1, 1) или (1, 1) (это не имеет значения) . Затем половину времени овца будет двигаться к цели, остальное время - на (1, 1) (или (-1, 1), если овчарка была на другой стороне).

From (1 , 1), как говорится в вопросе, овчарки поставят себя в (2, 1) и (1, 2), а овца переместится в (1, 0) или (0, 1).

Пусть E0 будет ожидаемым количеством шагов из (1, 0) (или эквивалентно (0, 1)), а E1 будет ожидаемым количеством шагов из (1, 1) (или эквивалентно (-1, 1)) .

Тогда E0 = 1/2 + (1 + E1) / 2 и E1 = 1 + E0.

Таким образом, E0 = 1/2 + (1 + 1 + E0) / 2 = 3/2 + E0 / 2, что дает E0 = 3. Это также дает E1 = 4, что согласуется с результатом в вопросе.