Given an integer $n\ge\ 3$, find the least positive integer $k$, such that there exists a set $A$ with $k$ elements, and $n$ distinct reals $x_{1},x_{2},\ldots,x_{n}$ such that $x_{1}+x_{2}, x_{2}+x_{3},\ldots, x_{n-1}+x_{n}, x_{n}+x_{1}$ all belong to $A$.
Problem
Source: 2009 China Western Mathematic Olmpiad
Tags: combinatorics proposed, combinatorics
28.02.2012 18:44
$A=\{x_{1}+x_{2}, x_{2}+x_{3},\ldots, x_{n-1}+x_{n}, x_{n}+x_{1}\}$ and so $k\le n$ seems to be a wrong thing. Which information do we have about the $n$ distinct values?
20.07.2013 14:42
The answer is $k=3$ (The nice fact is that $k$ does not depend on $n$ as long as $n\geq3$). Firstly let us show that $k=3$ is achievable: Consider the set of values: \[ x_{i}=\begin{cases}i &\textrm{ if i is odd},\\ 2n-i &\textrm{ if i is even}\end{cases} \] (for $ 1 \leq i \leq n $) Then it is obvious that $ x_{i} + x_{i+1} = i + (2n - (i+1)) = 2n-1 $ for $i$ odd and $ x_{i} + x_{i+1} = (2n - i) +(i+1) = 2n+1 $ for $i$ even, and also $ x_{n} + x_{1} = n + 1 $ will be the third value. (It is easy to notice that $ x_{n}=n$ in both cases: n is odd and n is even). So the $x_{1}, x_{2}, ..., x_{n}$ values and the set $A=\{n+1, 2n-1, 2n+1\}$ satisfy the condition. Secondly let us show that $k=2$ is not achievable: Assume the contrary that such values exist and let $A=\{p,q\}$ Then if $ x_{1} + x_{2}=p$ then $ x_{2} + x_{3}=q$ (it cannot be $p$ because we would have $x_{1}=x_{3}$ ). Similarly this will yield $ x_{3} + x_{4}=p$, $ x_{4} + x_{5}=q$ and so on the sums $x_{i}+x_{i+1}$ will continue in an alternated way: $\{p,q,p,q,p,q,...\}$ If $n$ is odd the sum $ x_{n-1} + x_{n} $ will be $q$. The sum $x_{n}+x_{1}$ cannot be $p$ because that would yield $x_{2}=x_{n}$ and also it cannot be $q$ because we would have $x_{1}=x_{n-1}$, so contradiction. If $n$ is even the sum $ x_{n-1} + x_{n} $ will be $p$ and the sum $x_{n}+x_{1}$ have to be $q$. But that would yield that \[ x_{1}+x_{2}+...+x_{n} = (x_{1}+x_{2})+(x_{3}+x_{4})+...+(x_{n-1}+x_{n}) = \frac{1}{2}np\] and also \[ x_{1}+x_{2}+...+x_{n} = (x_{2}+x_{3})+(x_{4}+x_{5})+...+(x_{n}+x_{1}) = \frac{1}{2}nq\], so we would have $p=q$ , so contradiction.