Using Induction To Prove that...

Question

I am trying to find a solution for the following problem:

Suppose that $n$ points labeled $A$ and $n$ points labeled $B$, are distributed on the perimeter of a circle. Use mathematical induction to prove that for all integers $n \ge 1$, given any arrangement of the points, 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.

What I have tried so far:

Basis step:

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).

Inductive Hypothesis: Suppose that for k a's and k b's this is true.

Given $k+1$ A's and $k+1$ B's on a circle, there has to be at least one location where an A is followed by a B as one travels in clockwise direction. If you remove such an A and the B that follows it, you have k A's and k B's, which is by inductive hypothesis true.

Thus, the proposition is true for all n A's and n B's where n >=1

What do you think of my solution?

Please provide any feedback on my solution, thanks in advance!

Answer 1

Interesting problem.

Your inductive step is not quite right. What you need to prove is that given the proposition is true for $k$, it implies that the proposition is true for $k+1$.

$$P(k) \implies P(k+1)$$

What you have done instead is that you take $k+1$ A points and $k+1$ B points on a circle, and by removing two points you arrive at $P(k)$ which you claim is true by hypothesis and stop there. Can you see how this is not the induction step?

Have you proven that $P(k+1)$ is true? No, you haven't and this is what the induction step requires.

Now, your method to choose the removed points is indeed a key argument, and can help you when you try to prove that $P(k+1)$ is true. I am not sure how you were thinking about it. How did you come up with this argument?

Just to give you another take on the flaw of your reasoning, think about it this way. Based on your reasoning, you do not have to choose the removed $A$ and $B$ points in a "smart" way. You can choose any point removed from the $k+1$ $A$ points and any point removed from and $k+1$ $B$ points and arrive at the same result: $P(k)$ is true. You can see I hope that this does not prove anything.

See if you can prove the induction step. We will be here to help. I see that a proof has been provided already in another answer. See if you can do it your own way, or express it in your own words.

Answer 2

You have the right idea, but your explanation for the induction step is incomplete. What you have so far, expressed a little more carefully, is this:

Assume the result for $k$, and suppose that we have $k+1$ $A$s and $k+1$ Bs arranged in a circle. There must be at least one location where an $A$ is immediately followed by a $B$ in clockwise order. Remove that $A$ and $B$; what remains is a circle containing $k$ $A$s and $k$ $B$s. By the induction hypothesis there is a starting point on that circle such that if one travels clockwise around the circle, the number of $A$s passed is never less than the number of $B$s passed.

Now you have to explain why you can use the same starting point for the original circle with the missing $AB$ restored. Here’s one possible fairly detailed explanation:

Using that starting point we can assign a number to each of the $2k$ letters in the reduced circle in the following way. If $a$ is the number of $A$s passed just after we pass that letter, and $b$ is the number of $B$s passed just after we pass that letter, we’ll label the letter with the difference $a-b$. By hypothesis this difference is never negative, because $a$ is never less than $b$. These labels show how much the count of $A$s up through this letter exceeds the count of $B$s. Notice that as we travel around the circle, the label increases by $1$ on every $A$ and decreases by $1$ on every $B$.

Now reinsert the $AB$ pair that we removed at the beginning. As we travel around the enlarged circle from the same starting point, the $a-b$ labels assigned to the letters are the same as before until we get to the reinserted $A$. If the $a-b$ label of the letter immediately preceding it is $d$, the reinserted $A$ will get the label $d+1$, and the reinserted $B$ will get the label $d$, so the excess of $A$s immediately after the reinserted $B$ is exactly the same as it was immediately before the reinserted $A$. For the remainder of the circle it will change exactly as it did without the reinserted letters, so it will never be negative. Thus, the starting point that worked for the reduced circle also works for the original circle, and the induction step is complete.

Depending on the level of your course and the level of rigor required by your instructor, you may well be able to get away with a significantly less detailed explanation, but you do definitely have to say something along these general lines.