What conditions show that a sequence can be permuted so that no two successive members are equal?
Proving a sequence has a permutation in which no member is equal to its successor
-
0An 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. – 2011-11-02
-
0@Didier Piau: I'm wondering, what does "more than half the members of the sequence" mean exactly? – 2011-11-02
-
0@zoo: With permutation, do you mean an arbitrary self-bijection of the natural numbers or one which fixed almost all elements? – 2011-11-02
-
0@Rasmus, This means $\geqslant n+1$ if the sequence has length $2n$ or $2n-1$. But you knew it, didn't you? – 2011-11-02
-
1Finite sequence, or infinite? – 2011-11-02
-
0@Didier Piau: Well, for a finite sequence this is clear. But what if it is infinite? – 2011-11-02
-
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. – 2011-11-02
-
0@Brian: Eh, I'll figure out how to reword in when it's not 4am here anymore. – 2011-11-02
-
0@Rasmus: Correction: for infinite sequences, you lose if there is exactly one infinite class which is also co-finite, and you win otherwise (that is, if there are no infinite class, or exactly one infinite class, also co-infinite, or at least two infinite classes). The additional co-finiteness condition is not needed to ensure that you lose if there are finitely many classes. – 2011-11-02
2 Answers
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
Now suppose that it’s of color $2$. If $n_1>\lceil(n-1)/2\rceil$, then $\lceil(n-1)/2\rceil
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.
-
0It does work; a proof by induction isn’t very difficult. – 2011-11-02