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.

  • 1
    $\begingroup$ what is $y_{n+1}$? $\endgroup$ – vidyarthi Aug 3 '19 at 15:32
  • 1
    $\begingroup$ Could you give a link to the web site of the contest? $\endgroup$ – Seva Aug 3 '19 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 Aug 4 '19 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 Aug 4 '19 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 Aug 5 '19 at 0:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.