<p>Caution: As Jukka Suomela commented on the question, the page linked from the question is about a problem different from the problem stated in the question in that the problem on the page has a restriction that the lengths of given sticks are greater than or equal to n.  This answer is about the problem without this restriction.  Since Emil’s comment on the question refers to the problem <em>with</em> the restriction, there is no contradiction between his comment and the following answer.</p>

<hr>

<p>The problem is NP-complete, even if the numbers are given in unary.</p>

<p>The 3-partition problem is the following problem:<br>
<em>Instance</em>: Positive integers a<sub>1</sub>, …, a<sub>n</sub> in unary, where n=3m and the sum of the n integers is equal to mB, such that each a<sub>i</sub> satisfies B/4 &lt; a<sub>i</sub> &lt; B/2.<br>
<em>Question</em>: Can the integers a<sub>1</sub>, …, a<sub>n</sub> be partitioned into m multisets so that the sum of each multiset is equal to B?</p>

<p>The 3-partition problem is NP-complete even if a<sub>1</sub>, …, a<sub>n</sub> are all distinct [HWW08] (thank you to Serge Gaspers for <a href="https://cstheory.stackexchange.com/questions/716/computational-complexity-of-the-3-partition-problem-with-distinct-numbers/758#758">telling me about this</a>).  It is possible to reduce this restricted version of the 3-partition problem to the problem in question as follows.</p>

<p>Suppose that we are given an instance of the 3-partition problem consisting of distinct positive integers a<sub>1</sub>, …, a<sub>n</sub>.  Let m=n/3 and B=(a<sub>1</sub>+…+a<sub>n</sub>)/m, and let N be the maximum among a<sub>i</sub>.  Consider the following instance of the stick problem: the instance consists of one stick of length k for each k∈{1, …, N}∖{a<sub>1</sub>, …, a<sub>n</sub>} and m sticks of length B.  By using the fact that each a<sub>i</sub> satisfies a<sub>i</sub> &gt; B/4 ≥ N/2, it is easy to prove that this stick problem has a solution if and only if the instance of the 3-partition problem has a solution.</p>

<p>References</p>

<p>[HWW08] Heather Hulett, Todd G. Will, Gerhard J. Woeginger.  Multigraph realizations of degree sequences: Maximization is easy, minimization is hard.  <em>Operations Research Letters</em>, 36(5):594–596, Sept. 2008.  <a href="http://dx.doi.org/10.1016/j.orl.2008.05.004" rel="nofollow noreferrer">http://dx.doi.org/10.1016/j.orl.2008.05.004</a></p>

CC BY-SA 2.5
2010-08-28T21:46:28.427Z
I do not know if the 3-partition problem remains NP-complete or not if the numbers are distinct, and I am asking about it: http://cstheory.stackexchange.com/questions/716/computational-complexity-of-the-3-partition-problem-with-distinct-numbers
Tsuyoshi Ito
CC BY-SA 2.5
2010-08-30T12:53:29.977Z
Serge Gaspers told me that it does (thanks!).  I simplified the proof using it.
Tsuyoshi Ito
CC BY-SA 2.5
2010-08-28T19:43:27.120Z
2010-08-30T12:52:12.930Z
2017-04-13T12:32:28.053Z
Tsuyoshi Ito
<p>Problem: We are given a set of sticks all having integer lengths. The total sum of their lengths is n(n+1)/2. </p>

<p>Can we break them up to get sticks of size ${1,2,\ldots,n}$ in polynomial time?  </p>

<p>Surprisingly, the only reference I find for this problem is this ancient discussion:</p>

<p><a href="http://www.iwriteiam.nl/cutsticks.html">http://www.iwriteiam.nl/cutsticks.html</a></p>

<p>What else is known about the problem? Can we prove the problem to be `in the limbo'?</p>

<p><em>Update: The cutting-sticks problem has the constraint that each stick is at least $n$ units long. (See the comments and Tsuyoshi's answer for the unconstrained case).</em></p>

CC BY-SA 2.5
2010-08-28T18:18:15.143Z
The problem formulation in the link that you gave has the following additional requirement, with which the problem seems to make more sense: "None of the sticks are shorter than $n$."
Jukka Suomela
CC BY-SA 2.5
2010-08-28T19:29:03.807Z
It is an unsolved problem to determine if this is always possible.
Emil
CC BY-SA 2.5
2010-08-28T22:46:18.337Z
@Emil: Do you have a reference? Anything more recent than the ancient (1995) discussion linked in the OP?
Jukka Suomela
CC BY-SA 2.5
2010-08-29T07:37:06.537Z
@Jukka My mistake. I forgot to mention that point since I was under the impression that the problem will not change significantly with that constraint.
Anyway, I'm happy since Tsuyoshi's answer has spawned an interesting question.
Jagadish
CC BY-SA 2.5
2010-08-29T07:59:37.960Z
this is quite a neat problem, but the title is misleading. It suggests that this is a complexity theory problem, when really it's a cool algorithms puzzle just like the unshuffling problem. Maybe you should reword the title.
Suresh Venkat
CC BY-SA 2.5
2010-08-29T09:47:59.547Z
@jagadish: One major difference is this: Without the constraint it's clear that for some instances the answer may be "no" (for example, all your sticks could have length = 1). With the constraint, it doesn't seem to be clear if there are any "no" instances at all.
Jukka Suomela
<reference-request><complexity-classes><puzzles>
Cutting-sticks puzzle
Jagadish
# Cutting-sticks puzzle

(Asked by: username_0 on 2010-08-28)

Problem: We are given a set of sticks all having integer lengths. The total sum of their lengths is n(n+1)/2.

Can we break them up to get sticks of size ${1,2,\ldots,n}$ in polynomial time?

Surprisingly, the only reference I find for this problem is this ancient discussion:

<http://www.iwriteiam.nl/cutsticks.html>

What else is known about the problem? Can we prove the problem to be `in the limbo'?

*Update: The cutting-sticks problem has the constraint that each stick is at least $n$ units long. (See the comments and Tsuyoshi's answer for the unconstrained case).*

**Tags:** reference-request, complexity-classes, puzzles
> **Comments:**
> **username_1**: The problem formulation in the link that you gave has the following additional requirement, with which the problem seems to make more sense: "None of the sticks are shorter than $n$."  
> **username_2**: It is an unsolved problem to determine if this is always possible.  
> **username_1**: @Emil: Do you have a reference? Anything more recent than the ancient (1995) discussion linked in the OP?  
> **username_0**: @Jukka My mistake. I forgot to mention that point since I was under the impression that the problem will not change significantly with that constraint. Anyway, I'm happy since Tsuyoshi's answer has spawned an interesting question.  
> **username_3**: this is quite a neat problem, but the title is misleading. It suggests that this is a complexity theory problem, when really it's a cool algorithms puzzle just like the unshuffling problem. Maybe you should reword the title.  
> **username_1**: @jagadish: One major difference is this: Without the constraint it's clear that for some instances the answer may be "no" (for example, all your sticks could have length = 1). With the constraint, it doesn't seem to be clear if there are any "no" instances at all.  

---

## 1 answers

### Answer by username_4 on 2010-08-28. Score: 15 | Accepted answer

Caution: As Jukka Suomela commented on the question, the page linked from the question is about a problem different from the problem stated in the question in that the problem on the page has a restriction that the lengths of given sticks are greater than or equal to n. This answer is about the problem without this restriction. Since Emil’s comment on the question refers to the problem *with* the restriction, there is no contradiction between his comment and the following answer.

---

The problem is NP-complete, even if the numbers are given in unary.

The 3-partition problem is the following problem:  
*Instance*: Positive integers a1, …, an in unary, where n=3m and the sum of the n integers is equal to mB, such that each ai satisfies B/4 < ai < B/2.  
*Question*: Can the integers a1, …, an be partitioned into m multisets so that the sum of each multiset is equal to B?

The 3-partition problem is NP-complete even if a1, …, an are all distinct [HWW08] (thank you to Serge Gaspers for [telling me about this](https://cstheory.stackexchange.com/questions/716/computational-complexity-of-the-3-partition-problem-with-distinct-numbers/758#758)). It is possible to reduce this restricted version of the 3-partition problem to the problem in question as follows.

Suppose that we are given an instance of the 3-partition problem consisting of distinct positive integers a1, …, an. Let m=n/3 and B=(a1+…+an)/m, and let N be the maximum among ai. Consider the following instance of the stick problem: the instance consists of one stick of length k for each k∈{1, …, N}∖{a1, …, an} and m sticks of length B. By using the fact that each ai satisfies ai > B/4 ≥ N/2, it is easy to prove that this stick problem has a solution if and only if the instance of the 3-partition problem has a solution.

References

[HWW08] Heather Hulett, Todd G. Will, Gerhard J. Woeginger. Multigraph realizations of degree sequences: Maximization is easy, minimization is hard. *Operations Research Letters*, 36(5):594–596, Sept. 2008. <http://dx.doi.org/10.1016/j.orl.2008.05.004>

> **Comments:**
> **username_4**: I do not know if the 3-partition problem remains NP-complete or not if the numbers are distinct, and I am asking about it: http://cstheory.stackexchange.com/questions/716/computational-complexity-of-the-3-partition-problem-with-distinct-numbers  
> **username_4**: Serge Gaspers told me that it does (thanks!).  I simplified the proof using it.  

---

