MathDB

A ladder style tournament is held with

2016

participants. The players begin seeded

1,2,\cdots 2016

. Each round, the lowest remaining seeded player plays the second lowest remaining seeded player, and the loser of the game gets eliminated from the tournament. After

2015

rounds, one player remains who wins the tournament. If each player has probability of

\tfrac{1}{2}

to win any game, then the probability that the winner of the tournament began with an even seed can be expressed has

\tfrac{p}{q}

for coprime positive integers

p

and

q

. Find the remainder when

p

is divided by

1000

.
Proposed by Nathan Ramesh

Problem Statement