Problem

Source: IMOC 2021 C5

Tags: probability, expected value, combinatorics



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