Boys and Girls around the table

$(n+1)$ boys and $n$ girls are seated around a circular table playing a game. One boy started to put a stone on the table, and they subsequently went around the table clockwise. At each child's turn, if that child is a boy, he puts a stone on the table, but if that child is a girl, she takes away one stone from the table. They're finished when everyone has had one turn. If the table ever becomes empty (except before the first boy put his stone), they all lose the game.

Prove that there is a boy such that if he starts, they can complete the round without losing.

Furthermore, prove that there is only one such boy. That is, if any other boy starts, they would lose the game.

Harder version: suppose you now have $m+n$ boys and $n$ girls, with $m$ positive. Prove that there are exactly $m$ boys who could start a non-losing game.

Solution for normal version

We prove by induction on $n$. The proof is trivial for $n=1$. Now, suppose that there is one and only one boy who could start a non-losing game in the case of $n=k-1$. We consider the case of $n=k$.

Take any boy who sits with a girl to his left, so that the girl's turn is immediately following him. Call the boy Andy and the girl Betty. Remove Andy and Betty from the table. We are now left with $k-1$ girl and $k$ boys, for which we would have exactly one boy who could start a non-losing game.

Suppose we start with that boy, then when we get to Andy, his stone would immediately be removed by Betty, and then the game proceeds exactly like it would in $n=k-1$ case. So the table would never become empty.

To prove that there is only one boy who could start a non-losing game, we only need to prove that Andy could not start a non-losing game. But it is trivial. If we start with Andy, the table would become empty right after Betty's turn. For any other boy besides Andy, the game proceeds exactly like it would in $n=k-1$ case, so there can only be one starter boy.

Solution for harder version

We fix $m$, and prove by induction on $n$. For $n=1$, it is easy to see that all the $m+1$ boys are sitting together, so the first $m$ boys could start a non-losing game.

The induction step works exactly like the normal version. We take any boy who sits immediately before a girl and remove them from the game.

Any boy who had started a non-losing game would still start a non-losing game after those two are returned to the table. The boy who was temporarily removed couldn't have been a starter boy. So there are exactly $m$ starter boys.