# $2k$ number assignment

Given $k$ numbers $A_1 \leq A_2 \leq ... \leq A_k$ such that $\sum\limits_{i=1}^k A_i = k(2k + 1)$ is there an assignment of numbers $i_1, i_2, ... , i_{2k}$ which is a permutation of $1, 2, ... , 2k$ such that

$i_1 + i_2 \leq A_1\\ i_3 + i_4 \leq A_2\\ .\\.\\.\\ i_{2k-1} + i_{2k} \leq A_k$

?

I cannot find an efficient algorithm and that solves this problem. It seems to be a combinatorial problem. I was unable to find a similar NP-Complete problem. Does this problem look like a known NP-Complete problem or can it be solved with a polynomial algorithm?

• Have you made any progress on the problem? – Yuval Filmus May 29 '13 at 15:52
• I forgot to mention that $A_1 \leq A_2 \leq ... \leq A_k$ – gprime May 29 '13 at 16:15
• Related problem, also without a satisfactory answer. (It may not be clear at first glance how they're related, but if $K=2N$, the problem is equivalent to finding a permutation of $1 \ldots 2N$ so that $i_{2a-1} - i_{2a} = A_i$. – Peter Shor Jun 6 '13 at 3:58

This problem is strongly NP-complete.

Suppose all the $A_j$ are odd. Then we know that since $i_{2j-1} + i_{2j} = A_j$ is odd, one of $i_{2j-1}$ and $i_{2j}$ is even and the other is odd. We can assume that $i_{2j-1}$ is odd and $i_{2j}$ is even. By letting $\pi_j = \frac{1}{2}(i_{2j-1}+1)$ and $\sigma_j = \frac{1}{2}(i_{2j})$, we can show that this is equivalent to asking for two permutations, $\pi$ and $\sigma$, of the numbers $1 \ldots n$ such that $\pi_j + \sigma_j = \frac{1}{2}(A_j+1)$.

This problem is known to be NP-complete; see this cstheory.se problem and this paper of W. Yu, H. Hoogeveen, and J. K. Lenstra referenced in the answer.

Here is a hint to get you started: since the sum of all numbers from $1$ to $2k$ is exactly $k(2k+1)$, a solution is possible only if in fact $i_1 + i_2 = A_1$, $i_3 + i_4 = A_2$ and so on. So given $i_1$ we know $i_2$, and so on. Also, $3 \leq A_j \leq 4k-1$.

• So how should I choose $i_1$ to begin with? Im not seeing the solution. But thanks for the property $3 \leq A_j \leq 4k -1$ – gprime May 29 '13 at 16:25
• If the $A_i$ are sorted, we know $3 \leq A_1$, $10 \leq A_1 + A_2$, $21 \leq A_1 + A_2 + A_3$, and so forth. Are these criteria, together with $\sum_i A_i = k(2k+1)$, enough? If they are, there might possibly be a simple algorithm for this problem. – Peter Shor May 29 '13 at 16:33
• Yeah, they are sorted. I will try to use this... – gprime May 29 '13 at 16:46
• @PeterShor You must also consider limits from the opposite direction, i.e. $4n-1 \geq A_n, 8n-6 \geq A_{n-1}+A_{n}$, and so on and so forth. Looking at the problem anecdotally, it appears a simple greedy algorithm should discover solutions when they exist, and fail precisely when they don't - but I'm having trouble proving it. – torquestomp May 29 '13 at 16:59
• @torquestomp: You're raising a good point. In fact, the limits from one direction also imply the limits from the other, but that's not at all obvious at first sight. I looked at a similar problem, and couldn't figure out a simple algorithm (but it also looked to me like the analog of these criteria was indeed enough). – Peter Shor May 29 '13 at 17:01

It's a matching problem, and so can be solved using Edmond's algorithm. See wikipedia

• The Stackexchange idea is to have a Q&A that's as complete as reasonably possible. Would you be able to expand you answer to be more than just a link to wikipedia? – Luke Mathieson May 30 '13 at 4:00
• Can you elaborate? I am failing to see how i can use that algorithms to solve my question. – gprime May 31 '13 at 18:58
• Actually, to me it looks like a special case of 3-matching, which is NP-complete. This doesn't mean that the OPs problem is NP-complete. – Peter Shor Jun 1 '13 at 11:34
• Could it be maybe a bipartite matching? I will look into the 3-matching to see if i can figure it out. Thanks! – gprime Jun 2 '13 at 15:24