Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Given $n$ $0$'s and $n$ $1$'s distributed in any manner whatsoever around a circle, show, using induction on $n$, that it is possible to start at some number and proceed clockwise around the circle to the original starting position so that, at any point during the cycle, we have seen at least as many $0$'s as $1$'s:

enter image description here

share|improve this question
    
what does see mean? –  Jorge Fernández Jul 8 '13 at 18:57
2  
@Omnitic: Think of actually walking around the circle, looking at each number as you pass it. You ‘see’ it at the moment you go past it. When you return to your starting point, you will have ‘seen’ all $2n$ numbers. –  Brian M. Scott Jul 8 '13 at 19:02
    
I'm missing a zero... Opps... Use your imagination to envision the missing one. –  Trancot Jul 8 '13 at 19:06
1  
Couldn't you start at a 1 and this falls apart though? You haven't seen any zeros yet you have seen a 1. There may be more to this question then. –  JB King Jul 8 '13 at 22:15
    
@JB King: Then don't start at a 1. The problem is to prove that there exists a starting point that fulfills the criterion, not to prove that every starting point fulfills the criterion (which as you note is trivially false). –  dfan Jul 9 '13 at 12:25

3 Answers 3

There is at least one instance of a $0$ followed by a $1$. Remove these two numbers, find (by induction hypothesis) a good starting point for the reduced circle, put the $0$ and $1$ back in and use the same starting position. It is easily verified that this is a valid starting position.

It is also not difficult to show the result without induction: A person walking around the circle and dropping a dollar at each $0$ seen and collecting a dollar (out of nowhere) at each $1$ seen will end up with the same amount he started with. And he will manage to complete the tour provided he starts with enough money in the briefcase. For an arbitrary starting point, chose the minimal valid starting amount of dollars. Then at some point of the tour the briefcase is empty. Starting the round trip at that place instead gives the desired result.

share|improve this answer
    
had you seen something like this before? –  Jorge Fernández Jul 8 '13 at 19:01
    
@Omnitic Could be, I don't know. –  Hagen von Eitzen Jul 8 '13 at 19:06
    
This smells like an application of Stokes' theorem. –  Neal Jul 8 '13 at 19:06
2  
@Neal: It’s a consequence of Raney’s lemma. Insert an extra $1$ anywhere. Raney’s lemma, which is proved by an argument much like the one in Hagen’s second paragraph, says that there is exactly one starting point from which you will always have seen more $1$’s than $0$’s. Start there after removing the extra $1$, and at each point you will have seen at least as many $1$’s as $0$’s. –  Brian M. Scott Jul 8 '13 at 19:13
    
It is a pretty well-known problem (in the more general Raney's Lemma form), and I would be surprised if it hadn't appeared here before. –  MJD Jul 8 '13 at 20:17

Alternatively: Count the total number of ways to arrange $0$s and $1$s around a circle ($2n$ binary digits in total), consider the number of Dyck words of length $2n$, i.e., the $n$th Catalan number, and then use the Pigeonhole Principle. "QED"

share|improve this answer
1  
[Anyone should feel free to edit and flesh out this argument; apologies for my presently absent focus!] –  Benjamin Dickman Jul 8 '13 at 19:13
    
"presently absent"-- nice phrase! –  coffeemath Jul 9 '13 at 1:11

Although a simple proof or your problem was already given in other answers, I wanted to complement them with some more (I hope interesting) information. Indeed, this is a special case of very old problem:

Let $(a_i)_{i=0}^{n-1}$ be a sequence of $n$ real numbers of non-negative sum, that is, $\sum_{i=0}^{n-1} a_i \geq 0$. Then, there exists index $k$ such that all partials sums (of $n$ terms starting from $k$) $\sum_{i=k}^{m+k} a_{i\ \bmod n}$ for $m = 0,1,\ldots,n$ are non-negative.

In your setting change $0$s to $(-1)$s and use the above theorem. As for its proof, you might want to use induction, but it is easier to do it directly. The key point is that, when you start from the lowest possible level, then all the rest of the path will actually be above (i.e. greater or equal) zero.

lot na marsa

In the picture above we can see two runs of partial sums (for convenience), thin horizontal black line is the absolute zero. If we were to start from the lowest possible level (dark red line), then all the rest (dark green strips) would be above the starting level (blue line).

The proof of the aforementioned theorem does exactly put the observation into formulas and concludes after rather simple calculation. I will not reproduce it here, because it would only obfuscate the basic idea behind the picture.

I hope this helps ;-)

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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