Poker Circles Induction

Question

Mehcad plays poker against 2n players already arranged in a circle. He will lose $1$ dollar against the ones better than him (wearing red shirts) but win $1$ dollar against ones weaker than him (wearing blue shirts). There are n red shirts and n blue shirts overall Mehcad will end up even, with a net gain of $0$ dollars. Mehcad has to pick the starting player and then play against each player in a clockwise pattern. Mehcad starts with no money, so he must avoid being cash-negative (for example BBRRRB, where playing against the third R ends up with -1). Using induction, prove that there is a starting point (a blue shirt) such that Mehcad always has $0 or more.

(Hint: Given 2n players, think carefully about which two players (one red shirt, one blue shirt) to remove. Apply the induction hypothesis on the remaining players.)

I have some basic ideas but I don't know how to write this induction. First, I wrote down the base case when $n=1$, there is $1$ red shirt and $1$ blue shirt players. They can be arranged as BR. Mehcad plays against them in a clockwise direction with a net gain of $0$ dollars at the end.

Then, my inductive hypothesis is that assumes $n=k$ is true, it is true that there is a starting point (a blue shirt) such that Mehcad always has $0$ dollars or more. $k$ R and $k$ B can be arranged in many ways. Overall, remove the adjacent BR, and finally, we will always be left with $a$ numbers of R and B (like RRR...RB...BBB). Remove the innermost RB every time. We will have only 1 pair of RB which cancels each other out. Now we must prove that when $n=k+1$, there is a starting point (a blue shirt) such that Mehcad always has $0$ dollars or more. I said there are $1$ more red and 1 more blue player. They can be placed anywhere in $2k$ players but since it's true that there is a starting point such that Mehcad always has $0$ dollars or more by inductive hypothesis. $2k$ R and B cancel out and lead to $0$. The left pair of RB will be canceled too.

I don't think my answer worths 20 marks. Could anyone help me?

Answer 1

I think you have the overall right idea, but your answer might be a bit confusing.

You did base case for $n=1$. Let’s suppose the result is right for $n=k$. Notice that for any configuration with $2k$ people, adding a "BR" somewhere doesn’t affect the problem: you’ll just get an additional dollar that you will lose right after. Now take any configuration with $2(k+1)$ players. In this configuration, there must be a "BR" somewhere (otherwise we would either have no blues or no reds). Remove these two players to get a configuration with $2k$ players for which we can choose a starting point. Then add back the two players we removed, and we’re done!