3
$\begingroup$

The sequence $x_1, x_2, ..., x_n$ of positive integers contains at least $\frac {2n}{3}+1$ distinct numbers and each of them appears at most three times. How to prove that there is a permutation $y_1, y_2, ..., y_n$ of $x_1, x_2, ..., x_n$ such that the $n$ sums $y_i+y_{i+1}$ are all distinct, where $1\le i\le n$ and $y_{n+1}=y_1$?

This problem was proposed on a math contest and as far as I'm concerned nobody managed to solve it, moreover the official solution was flawed. Or maybe this is false? In case it's true, can it be generalized?

Any reference or help would be appreciated.

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ what is $y_{n+1}$? $\endgroup$
    – vidyarthi
    Commented Aug 3, 2019 at 15:32
  • 1
    $\begingroup$ Could you give a link to the web site of the contest? $\endgroup$
    – Seva
    Commented Aug 3, 2019 at 19:16
  • 1
    $\begingroup$ Is there a counterexample if you have only $2n/3$ distinct numbers, or if you let some number appear four times? $\endgroup$
    – Gerry Myerson
    Commented Aug 4, 2019 at 0:10
  • 2
    $\begingroup$ @GerryMyerson If $n=3$ and you only have $2n/3 = 2$ distinct numbers, $\{1,1,2\}$ is a counterexample. $\endgroup$
    – Robert Israel
    Commented Aug 4, 2019 at 4:15
  • $\begingroup$ @Seva I saw this question on Aops and it appeared on an Iranian contest. I think there is no official website, but I contact someone involved in this contest and I was told it remains as an open problem. $\endgroup$
    – jack
    Commented Aug 5, 2019 at 0:25

0

Reset to default

You must log in to answer this question.