finite set of integers can be arranged without intersection

orl

Prove that each finite set of integers can be arranged without intersection.

**Posted:** Tue Dec 28, 2004 4:49 pm

_________________
Math is like love. A simple idea but it can get complicated.

grobber

orl, maybe you could restate some of the problems you've recently posted? For instance, I have no idea what this one means Confused

. First of all, what does "arranging a finite set of integers" mean? Second of all, what does "intersection" mean in this case?

Sorry if this is common language, it's not common to me.. Smile

Thanks!

**Posted:** Tue Dec 28, 2004 5:32 pm

orl

**Posted:** Wed Dec 29, 2004 5:43 am

_________________
Math is like love. A simple idea but it can get complicated.

pbornsztein

Ah, ok. Thus, I still do not see where there must be an invariant (unless you are talking about induction) but here it goes :
Let $n$ be a positive integer. And $U_n = a_1,..., a_n$ be a sequence of positive integers.
We will say that $U_n$ is good if no term $a$ is the arithmetical mean of two other terms of the sequence one on each side from $a$ .
Thus both $U_3 = -1,1,0$ and $U_6 = -2,2,0,-3,1,-1$ are good.

Now assume that $U_n$ is good.
Let $U_{2n} = 2a_1,2a_2, \cdots , 2a_n, 2a_1-1,2a_2-1, \cdots, 2a_n - 1 = b_1, \cdots, b_{2n}.$

We will verify that $U_{2n}$ is good too :
Let $1 \leq i<j<k \leq 2n$ .
If $i \leq n$ and $k>2n$ then $b_i$ and $b_k$ have opposite parities so that their sum is not equal to $2b_j$ .
If $k \leq 2n$ , then $b_i = 2a_i,b_j = 2a_j,b_k = 2a_k$ , and the induction hypothesis ensures us that $b_i+b_k \neq 2b_j.$
If $i > 2n$ then $b_i = 2a_{i-2n} - 1,b_j = 2a_{j-2n}-1,b_k = 2a_{k-2n}-1$ , and again $b_i+b_k \neq 2b_j.$

This proves that $U_{2n}$ is good, as claimed.

Now, it is easy from $U_3$ and $U_6$ given above to verify that $U_{3 \cdot 2^n$ is a permutation of $E_n = \{-2^{n+1} , -2^{n+1} + 1, \cdots, 0, 1 ,2, \cdots, 2^n \}$ .
Then, since any finite set of integers is contained in such set $E_n$ for sufficientely large $n$ and since to obtain a good permutation of our given set it suffices to delete the members of $E_n$ which do not belong to our given set (so that the sequence remains good), we are done.

Pierre.

**Posted:** Wed Dec 29, 2004 6:17 am

Pentakratie

More or less the same problem was used by the Bundeswettbewerb Mathematik 2005 as the problem 4 in the 1st round:

For which positive integers n is it possible to arrange the n numbers 1, 2, 3, ..., n in a sequence such, that for any two numbers the arithmetic mean of these two numbers doesn't stand somewhere between them?

Of course, the answer is: This is possible for all positive integers n.

Another thread with a discussion of the same topic: http://www.artofproblemsolving.com/Forum/viewtopic.php?t=14758 .

**Posted:** Tue Mar 01, 2005 3:01 pm

_________________
CRDHNKDGCHJEVGAF