Suppose that $S$ is a finite set of real numbers with the property that any two distinct elements of $S$ form an arithmetic progression with another element in $S$. Give an example of such a set with 5 elements and show that no such set exists with more than $5$ elements.
Problem
Source: 14-th Iranian Mathematical Olympiad 1996/1997
Tags: arithmetic sequence, combinatorics proposed, combinatorics
marko avila
19.10.2005 21:55
I tried this for a half an hour and got nothing. of course this is normal (im really weak at combi) but im trying to get better so could someone please post a solution??? thanks
grobber
03.11.2005 11:33
Cool problem . Assume we can have such a set with a finite but larger than $5$ number of elements. Also assume the smallest and largest elements are $0$ and $1$, for simplicity. Then $\frac 12$ is also an element, and there must be at least one element $a_0\ne 0,1,\frac 12,\frac 13,\frac 23$. More precisely, we asume WLOG that $a_0\in\left(\frac 13,\frac 12\right)$. Then there will be an element of our set, $b_0\in\left(\frac 23,1\right)$, the midpoint of the segment $(a_0,1)$. After that, we can find an element of our set, $a_1\in\left(\frac 13,a_0\right)$, the midpoint of $(0,b_0)$. Then we find $b_1\in\left(\frac 23,b_0\right)$, the midpoint of $(a_1,1)$, and so on. This sequence of steps cannot stop (we get a sequence $a_n$ converging to $\frac 13$ whose terms are always $>\frac 13$), so we're done.
jgnr
11.01.2009 05:55
Sorry for reviving this, but no one posted a 5-element set example. Grobber's solution is very nice, anyway..
A 5-element set is $ \{0,2,3,4,6\}$. We can easily verify that this set satisfies the given conditions.
Now assume that there exists a 6-element set $ \{0,v,w,x,y,z\}$ which satisfies the conditions. WLOG, assume 0 and $ v$ makes an arithmetic progression with $ w$, so assume that $ w=2v$. Similarly, assume that $ y=2x$. So the set becomes $ \{0,v,2v,x,2x,z\}$. Now, $ 0,z$ form an arithmetic progression with (WLOG) $ v$ or $ 2v$. It is easy to check that for both cases, that set is of the form $ \{0,a,2a,4a,b,2b\}$, with $ a,b\in\mathbb{R}^+$.
$ a,4a$ make an arithmetic progression with $ 7a$. So $ b=7a$ or $ 2b=7a$. Easy to check that both cases are impossible. Contradiction, Q.E.D.
JBL
11.01.2009 17:01
Johan Gunardi wrote: Q.E.D. No: deriving a contradiction for sets of size 6 does not automatically rule out sets of larger size. (Also, grobber did construct the same 5-element example you did (though he didn't say this was what he was doing) when he mentioned 0, 1/3, 1/2, 2/3, 1.)