Timeline for Partitioning a set of consecutive nonnegative integers into distinct pairs
Current License: CC BY-SA 4.0
11 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 16, 2021 at 13:17 | comment | added | domotorp | I'm not sure, because the results in my question are mod k, so picking 2 and k+2 can count either as k-1, or 1, but in yours it is always k-1, right? Also, watch out that you've asked your question only for even k, which are rarely prime numbers. | |
| Apr 16, 2021 at 8:31 | comment | added | vidyarthi | @domotorp so if $k$ be prime, it is definitely possible and again, if $k=2p$ also it is possible, right? | |
| Apr 16, 2021 at 5:11 | comment | added | domotorp | This problem is closely related: mathoverflow.net/questions/24108/… | |
| Apr 15, 2021 at 19:53 | comment | added | Will Sawin | 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. | |
| Apr 15, 2021 at 19:48 | comment | added | vidyarthi | @WillSawin yes, the differences are taken modulo $k+1$ so the differences become consecutive, and moreover I am interested in the absolute value of the differences | |
| Apr 15, 2021 at 19:46 | comment | added | Will Sawin | The example given for difference $1,2,\dots, \frac{k}{2}$ is confusing - it seems to me that the differences are $1, k-1, 3, k-3, \dots$ which is a different list. | |
| Apr 15, 2021 at 19:41 | comment | added | Will Sawin | @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$. | |
| Apr 15, 2021 at 18:40 | comment | added | Yaakov Baruch | 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. | |
| Apr 15, 2021 at 18:25 | comment | added | vidyarthi | @YaakovBaruch you mean this is a case for pigeonhole principle? | |
| Apr 15, 2021 at 18:20 | comment | added | Yaakov Baruch | 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. | |
| Apr 15, 2021 at 17:53 | history | asked | vidyarthi | CC BY-SA 4.0 |