Drunken man is expected to walk integer number of steps
Source: IMOC 2021 C5
August 11, 2021
probabilityexpected valuecombinatorics
Problem Statement
A drunken person walks randomly on a tree. Each time, he chooses uniformly at random a neighbouring node and walks there. Show that wherever his starting point and goal are, the expected number of steps the person takes to reach the goal is always an integer.houkai