$n$ athletes ($a_1,...,a_n$) are arranged in a line. At each time $t$, two adjacent athletes race each other. The loser is removed from the line and the winner stays in the same position. This continues until there is one athlete remaining. You have a matrix where the $(x,y)$ entry indicates gives the result if $a_x$ and $a_y$ are to race. Give an algorithm to output all possible final winners that runs in polynomial time.
The idea that I had was to iterate through each athlete (let's call this $a_i$) and have two separate competitions: one for the next ($a_{i+1}$) and one for the previous $(a_{i-1}$). I don't know if this is correct, and have not been able to prove its correctness either way. Is this correct and if so, how might I prove it?
"Polynomial time" is actually pretty generous -- it lets you get away with nesting another loop of length $n$ in your program whenever you need one.
Problems like this kind naturally lend themselves to dynamic programming where you build up a table of answers to smaller subproblems and use those to find answers to larger subproblems, the original problem being the largest of them all.
Here, a natural shape of a subproblem would be something like:
There are $O(n^3)$ such subproblems, so if only we can build an answer to one of them in polynomial time assuming that we already know solutions to all smaller subproblems, then we're done.
Can you see how to do that combination in $O(n^2)$ time? That would add up to an $O(n^5)$ algorithm -- which is perhaps a bit much for practical use, but certainly meets the requirement of polynomial time.