0
$\begingroup$

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!

$\endgroup$

closed as unclear what you're asking by Watson, Parcly Taxel, haqnatural, mrp, Takumi Murayama Oct 26 '16 at 6:08

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ Please don't vandalize your own post. If you are unhappy with it, just delete it. $\endgroup$ – Alex M. Oct 20 '16 at 15:49
  • $\begingroup$ Just below your post there is a "delete" tag/button. In any case, why delete it? If everyone deleted one's answered questions, this site would no longer exist. $\endgroup$ – Alex M. Oct 20 '16 at 18:06
  • $\begingroup$ @Mrgoog, please do not vandalise your post. If this is a homework question and you are worried about your teacher seeing it as cheating, you can explain what you did. I think it is clear that you did not ask for a solution, but instead wanted feedback on your solution. I think that's good practice and can help you learn. I do not see it as cheating and neither should your teacher. $\endgroup$ – Thanassis Oct 26 '16 at 14:40
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Can you modify your post? Please post a feedback to the question (if you want to), not a detailed answer. Thanks! $\endgroup$ – Mrgoog Oct 21 '16 at 20:05
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ No, this is not what the OP has done. The OP has in fact set up the induction step correctly and found the key to the necessary argument; what’s lacking is an explanation of why the starting point for the smaller circle still works when the removed $AB$ pair is reinserted. With that explanation the argument would be complete and correct, though it could be expressed better. $\endgroup$ – Brian M. Scott Oct 20 '16 at 10:34
  • $\begingroup$ @BrianM.Scott I am a bit surprised that you say that my description does not reflect what the OP has done. It think it's pretty straightforward. I do realise that the OP has a key argument that can be used in the proof, and I should have pointed this out in my answer (I'll edit it now). But the induction reasoning is flawed: The OP does not try to prove P(k+1) is true, but instead the proof stops when a true statement is reached (the induction hypothesis). It's hard to say what's in the OP's mind, but pointing out the flaws in rigour, might help unlock some insights. $\endgroup$ – Thanassis Oct 21 '16 at 3:33
  • $\begingroup$ The present version is much better. I still think, however, that the the OP’s error is most likely to be failure to explain clearly; otherwise there is no reason to choose to delete an $AB$ pair. $\endgroup$ – Brian M. Scott Oct 21 '16 at 14:05
  • $\begingroup$ @BrianM.Scott It's hard to say, maybe the deletion method was given as a hint to the OP. To me the flaw in the induction reasoning seems quite significant, something that goes beyond just a poor explanation, or language barriers. Of course it's hard to know without getting more feedback from the OP. Let's hope s/he will come back :) $\endgroup$ – Thanassis Oct 21 '16 at 14:37

Not the answer you're looking for? Browse other questions tagged or ask your own question.