# Proving a sequence has a permutation in which no member is equal to its successor

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

-
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

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.

-

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.

-

It does work; a proof by induction isn’t very difficult. – Brian M. Scott Nov 2 '11 at 10:34
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 40, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9581454992294312, "perplexity_flag": "head"}