Induction Sequence on Points on a Circle Suppose that n a’s and n b’s are distributed around the outside of a circle. Use mathematical
induction to prove that for all integers n ≥ 1, given any such arrangement, it is possible to find a starting
point so that if one travels around the circle in a clockwise direction, the number of a’s one has passed is
never less than the number of b’s one has passed.
 A: HINT: Suppose that it’s true for $n$. Consider a circle with $n+1$ $a$’s and $n+1$ $b$’s. There must be an $a$ that is immediately followed in clockwise direction by a $b$. What happens if you remove that $a$ and $b$?
A: It is true for n = 1, namely if sequence is {a, b} (here is moving from left to right denotes clockwise moving and after last you jump to the first) and we start from a.
Now if it holds for n and there is starting point a*, then for n+1, there 2 possible cases new 'a' added before new 'b' => we still can start from a* since will pass through new 'a' earlier thus condition |a|>=|b| is true {... a* ... a ... b ...}.
And second case new 'b' added before new 'a' {... a* ... b ... a ...}, then it is possible what at some point b* where |a| was equal to |b| now will be |a|<|b| {... a* ... b ... b* ...}, in such a case just pick new starting point such 'a' after b* (let's denote it a**) so the condition |a|<|b| is satisfied, that will be always possible because |a| on the right of b* will be more than |b| on the right of b*, since in all we have n+1 a's and b's and as it was mentioned |a|<|b| on the left b* {... a* ... b ... b* ... a** ...}
