Kindly refer to Q4 of this handout.
"$2n$ dots are placed around the outside of the circle. $n$ of them are colored red and the remaining $n$ are colored blue. Going around the circle clockwise, you keep a count of how many red and blue dots you have passed. If at all times the number of red dots you have passed is at least the number of blue dots, you consider it a successful trip around the circle. Prove that no matter how the dots are colored red and blue, it is possible to have a successful trip around the circle if you start at the correct point."
I have been able to come up with a proof as follows:
Let $f(x)$ be the function counting the number of red dots less blue dots from an arbitrary point to a point $x$ radians clockwise. Then, if this arbitrary point does not contain a dot, $f(0) = f(2\pi) = 0$. If we find the minimum of $f$, we can take the value of $x$ at that point as our start and guarantee that red minus blue is always non-negative, satisfying the condition.
However, I am unable to come up with a proof by induction. Clearly, the base case is starting at the red dot. How does one proceed with the inductive step?
Thanks for any guidance!
Best Answer
Suppose that the result is true for $2n$ dots, and consider a circle with $2(n+1)$ dots. There must be a point where a red dot is immediately followed clockwise by a blue dot; remove those two dots. By the induction hypothesis there is a usable starting point for the reduced circle. Will that starting point still work when you restore the two adjacent dots that you removed?