2
$\begingroup$

Let us have a set of $k$ consecutive natural numbers $2,3,\ldots, k+1$, $k$ even. In addition, we are given a set of $m=\frac{k}{2}$ 'differences' from one among the $k$ numbers $1,2,\ldots, k$.

My questions is, is it always possible to partition the $k$ prior numbers into distinct pairs such that the difference between the numbers in the distinct pairs correspond to the $m$ 'differences' given. Note that the differences are taken modulo $k+1$.

I think the answer is yes if the 'difference' numbers $m$ are all distinct. If the set of differences was like $1, 2,\ldots,\frac{k}{2}$, then it is easily possible to partition the aforementioned numbers as $(\frac{k}{2}+2,\ \frac{k}{2}+1),(2,\ k+1),(\frac{k}{2}+3,\ \frac{k}{2}),(3,\ k),\ldots$, but what if the set of $m$ numbers was random? Is there any easy algorithm to do the partitions.

If the $m$ 'differences' are not distinct, we can arrive at easy counterexamples, like say, our $k=6$ and the set of $m$ 'differences' are $4,4,4$, then we cannot get the distinct partitions. However, this is not always the case, for if the 'differences' are $6,6,6$ we have the partitions $(2,\ 3),(4,\ 5),(6,\ 7)$. I think this partitioning is somewhat related to concepts such as Sidon sequence and Golomb rulers. Any hints? Thanks beforehand.

Improve this question
$\endgroup$
10
  • 1
    $\begingroup$ Some remarks: 1] the differences should form a multiset; 2] they should range from $1$ to $k-1$ (not $k$); 3] clearly the sum of the differences needs to be $\equiv k/2$ (mod $2$), 4] clearly for any $n$ there can be at most $k-n$ differences $\ge n$. I wonder if 3] and 4] are sufficient to guarantee the existence of a partition. $\endgroup$
    – Yaakov Baruch
    Commented Apr 15, 2021 at 18:20
  • 1
    $\begingroup$ No, I didn't say that. It may be the case that some simple application of the principle nails the proof, but I don't have an opinion on that. I'm more thinking that 3] and 4] being sufficient may be provable by induction on $k$, but it's just speculation on my part. $\endgroup$
    – Yaakov Baruch
    Commented Apr 15, 2021 at 18:40
  • 2
    $\begingroup$ @YaakovBaruch A sharper version of 4] is that the sum of any $n$ difference must be at most $k n - n^2$ (proof: take the maximum sum of $n$ distinct values minus the minimum sum of $n$ distinct values). When this inequality is sharp, the top $n$ and bottom $n$ are separate from the rest, and so we can split into two distinct problems - a smaller version of the original one and a problem depending only on $n$. $\endgroup$
    – Will Sawin
    Commented Apr 15, 2021 at 19:41
  • 2
    $\begingroup$ Then by reversing the order of pairs we can switch the differences $d$ and $k+1-d$ and thus assume the differences are at most $\frac{k}{2}$ (because $k$ is even). There is still a parity condition as Yaakov said but the inequalities we wrote down are not needed. $\endgroup$
    – Will Sawin
    Commented Apr 15, 2021 at 19:53
  • 2
    $\begingroup$ This problem is closely related: mathoverflow.net/questions/24108/… $\endgroup$
    – domotorp
    Commented Apr 16, 2021 at 5:11

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .