Cutting-sticks puzzle 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).
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 &lt; ai &lt; 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).  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 &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.

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