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.

What conditions show that a sequence can be permuted so that no two successive members are equal?

share|improve this question
    
An obvious necessary condition is that no collection of more than half the members of the sequence can have the same value. This might be a sufficient condition as well. –  Did Nov 2 '11 at 8:55
    
@Didier Piau: I'm wondering, what does "more than half the members of the sequence" mean exactly? –  Rasmus Nov 2 '11 at 9:03
    
@zoo: With permutation, do you mean an arbitrary self-bijection of the natural numbers or one which fixed almost all elements? –  Rasmus Nov 2 '11 at 9:04
1  
Finite sequence, or infinite? –  Gerry Myerson Nov 2 '11 at 9:14
1  
@Rasmus, Unsurprisingly, the expression half the members of the sequence refers to finite sequences. And, unless I am missing something, the infinite sequence version is trivial: you lose if there is exactly one infinite class and you win otherwise. –  Did Nov 2 '11 at 9:57
show 4 more comments

2 Answers

up vote 2 down vote accepted

Here’s a proof that Christian’s greedy algorithm works.

Suppose that there are $n$ balls and $k$ colors. Suppose further that color $i$ occurs $n_i$ times, so that $n_1+\dots+n_k=n$, and that $n_i\le\lceil n/2 \rceil$ for each $i$. Finally, assume that $n_1\ge n_2\ge\dots\ge n_k$.

Even if we’ve already placed some balls, at most one color is unavailable, so we may take the first ball to be of color $1$ or color $2$. A problem would arise only if color $1$ is unavailable and $n_2=0$, but in that case $n_1=n$, which is impossible. To show that the induction goes through, it suffices to show that after the new ball is placed, there is no color with more than $\lceil(n-1)/2\rceil$ balls left.

Suppose first that the ball just placed is of color $1$. Clearly $n_1-1\le\lceil(n-1)/2\rceil$. Suppose that $n_i>\lceil(n-1)/2\rceil$ for some $i>1$. Then $\lceil(n-1)/2\rceil<n_i\le\lceil n/2\rceil$. If $n=2m$, this is $m<n_i\le m$, which is absurd, so $n=2m+1$. But then we have $m<n_i\le m+1$, so $n_i=m+1$, and $n\ge n_1+n_i\ge 2n_i=2m+2>n$, which is also absurd. Thus, the induction goes through just fine if the ball just placed is of color $1$.

Now suppose that it’s of color $2$. If $n_1>\lceil(n-1)/2\rceil$, then $\lceil(n-1)/2\rceil<n_1\le \lceil n/2\rceil$. As in the last paragraph $n$ must be odd, say $n=2m+1$, and $n_1=m+1$, which is a problem. However, this case arises only if color $1$ is unavailable, which means that we just placed a ball of color $1$ at the previous step. At the beginning of that step, therefore, there must have been $n+1=2m+2$ balls, of which $m+2$ were of color $1$, and that’s impossible. Thus, we must have $n_1\le\lceil(n-1)/2\rceil$, as desired. The colors $i$ for $i>2$ can then be handled as in the last paragraph.

share|improve this answer
add comment

Assume everything is finite. So basically we have finitely many balls of different colors assorted into heaps according to colors. I think that Didier Piau's conjecture is true and that the following greedy algorithm works: Take as next ball a ball from an allowed heap of maximal size.

share|improve this answer
    
It does work; a proof by induction isn’t very difficult. –  Brian M. Scott Nov 2 '11 at 10:34
add comment

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.