Use induction to provde Suppose that n as and n bs are distr

Use induction to provde:

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 greaterthanorequalto 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. For example, in the diagram shown below, one could start at the a with an asterisk.

Solution

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* along clock wise direction.

it is given that (n+1) a\'s and (n+1) b\'s arrayed around the outside of the circle, there has to be atleast one location where an \'a\' is followed by a \'b\' as one travel in the clock wise direction

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** ...}