Just want to ask an mathematical induction question which I've tried to solve.. but still cannot get the LHS and RHS.

709 Views Asked by At

I have tried to solve this question, but it's kinda tricky here when I form a LHS equation by myself it doesn't equals to the RHS. Can anyone here provide me a step by step guide to proof it?

problem

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 \geq 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.

1

There are 1 best solutions below

10
On

The proposition is obviously true when $n=1$ because you can start at $a$.

Now assume it's true for all circles with $2n$ labels equally apportioned among $a$ and $b$. Consider a circle with $2n+2$ equally apportioned labels.

There will necessarily be a place on the circle where an $a$ and a $b$ are immediately adjacent with $b$ clockwise from $a$. Remove those two adjacent vertices and you have remaining a circle with $2n$ equally apportioned labels. By your inductive hypothesis, you can find a starting place where you have passed at least as many $a$s as $b$s. When you reinsert the two vertices you have removed, you will pass the removed $a$ before you pass the removed $b$, so the property you need still holds and you are done.

Edit:

There's a second way to look at most proofs by induction that you may find helpful. You can think of them as considering the least $n$ where your proposition fails, and then proving that the proposition does not in fact fail there. Let's look at how this methodology plays out for your problem.

Suppose the proposition is false for some $n$. Since any non-empty set of natural numbers has a least element, let's choose the smallest possible $n$ for which the proposition fails, and consider a circle with $n$ $a$ labels and $n~b$ labels. As above, we know there must be a place on the circle where an $a$ and a $b$ are immediately adjacent with $a$ clockwise from $b$ so let's erase those two vertices. There are two possibilities.

Case 1: There are no vertices left after you erase those two vertices. In that case, the two vertices you erased were the only two vertices around the circle, you can start your path at the $a$ vertex, and in fact the proposition did not fail, contrary to your assumption. That contradiction proves the result for Case $1$.

Case 2: There are vertices remaining after you erase two vertices as above. Then the circle with two vertices erased has fewer than $2n$ vertices so it's smaller than the smallest case for which the proposition fails. Therefore, there must be a path around this smaller number of vertices that works. Start there, and we will always have reached at least as many $a$ vertices as $b$ vertices until we reach the two vertices that we erased. We will add an $a$ vertex before we add a $b$ vertex, so the path continues to work when we traverse the two erased vertices, and in fact the net difference when we have passed them both will be the same as it was in the path on the smaller set of vertices. Thus, when we complete the circle, the path will continue to work (because it worked in the smaller circle) and again, contrary to our assumption, the proposition does not in fact fail here, contradicting the assumption we used to reach Case $2$. This completes the proof.