I'm an undergraduate taking a Discrete Mathematics Module. This is one of my assignment questions.
Task:
$n > 0$ red balls and $n$ blue balls are arranged to form a circle. You walk around the circle exactly once in a clockwise direction and count the number of red and blue balls you pass. If at all times during your walk, the number of red balls (that you have passed) is greater than or equal to the number of blue balls (that you have passed), then your trip is said to be successful. (Note that whether successful or not, you will pass exactly $2n$ balls after walking one round.)
Define predicate $P(n) = $( In any circle formed by n red and n blue balls, there exists a successful trip ), $\forall x \in \Bbb Z^{+}.$
Using the above predicate P(n), prove by Mathematical Induction (either Regular or Strong Induction) that you can always make a successful trip if you can choose where you start.
(Note: you must use $P(n)$ as the induction predicate in your proof. You may not modify it, nor use a different predicate.)
My stand:
I think for this question, there is a need to find a general formula(or at least a way) representing the number of possible circular orientations of the n red balls and n blue balls. I have a problem with visualising this as I’m very bad at combinatorial questions and when to decide what is treated as unique and what is treated as a repetition.
1) Is it really required of me to figure out the orientations in the question, to get the inductive case of this problem? I hope I’m heading the right direction. If it’s not the right approach, please provide some hints as to how to go on from here. I will edit my progress report incrementally.
2) Suppose the number of ways Even if it’s not required, I would like to ask what exactly is a good procedure to visualise circular paths as repetitions of each other. For me, I think of a the circle arrangement as a special linear arrangement with variable start points, so I have the following procedure, take $n=3$.
a)Pick a random start point, say R (I think somehow my starting point won’t matter for a circular arrangement)
b)Come up with a possibility tree incrementally by appending R or B to the right of the arrangement till I fulfil n R and n B elements. If I do this for 6 stages/elements, and don’t eliminate repetitions in the circular arrangement, I should get $2^{5}$ such chains if I actually model it after linear chains instead.
c)I will first complete some boundary cases like RRRBBB, and reject some of the chains before they are completed if I observe that under the constraints of n colour for either side, their remaining choices are forced.
d) If they hit 6 elements long, I will try to “rotate” the leftmost element to become the rightmost element to get a common part that matches with one of the accepted cases. If that common part is not the entire length of the chain, it must be a unique case.
A diagram of my procedure.
I arrived at the conclusion that there are 5 circular combinations for $n=3$.
Suppose this procedure is somewhat correct, I’m unable to translate this procedure in terms of a formula to find number of circular arrangements for general n, and proceed to know the enumerations required for this problem. Should I think of the number of ways of circular arrangement as such or is there a more convenient way to think of such a problem?
Feel free to correct me if any of my assumptions are wrong, or quote the name of the results in my algorithm if they are somehow correct, since they are just based on my intuition.
P.S: The title may not be a good description of my problem, didn’t know how to give a good title other than “How to solve this question?”. Notice that (2) requires answer to (1) to be “Yes”. If the answer is no, I will edit the post to bring (2) to another discussion. Thanks.
Best Answer
You start out incorrectly, I'm sorry to say. In step a) you say, "I think somehow my starting point won’t matter for a circular arrangement." This is not true. When $n=1$ the circular arrangement must be RB, and we will be successful if we start at the red ball, but not if we start at the blue ball. (This takes care of the basis of the induction, by the way.)
Suppose now that $n>1$ and that $P(n-1)$ is true. In any circular arrangement of $n$ red balls and $n$ blue balls, there must be a red ball immediately followed by a blue ball in clockwise order. (Start at a red ball, and walk clockwise. The first blue ball we come to is preceded by a red ball.) Now consider the circle with these two balls removed. By the induction hypothesis, there is some red ball we can start at to have a successful trip with the $2n-2$ balls. Now argue that if we put the two balls that we remove back, and start at the same red ball, we will have a successful trip around the circle with $2n$ balls.