HMMT 2006 C7

Let $n$ be a positive integer, and let Pushover be a game played by two players, standing squarely facing each other, pushing each other, where the first person to lose balance loses. At the HMPT, $2^{n+1}$ competitors, numbered 1 through $2^{n+1}$ clockwise, stand in a circle. They are equals in Pushover: whenever two of them face off, each has a $50 \%$ probability of victory. The tournament unfolds in $n+1$ rounds. In each round, the referee randomly chooses one of the surviving players, and the players pair off going clockwise, starting from the chosen one. Each pair faces off in Pushover, and the losers leave the circle. What is the probability that players 1 and $2^{n}$ face each other in the last round? Express your answer in terms of $n$.