18
$\begingroup$

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).

$\endgroup$
  • 1
    $\begingroup$ 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$." $\endgroup$ – Jukka Suomela Aug 28 '10 at 18:18
  • $\begingroup$ It is an unsolved problem to determine if this is always possible. $\endgroup$ – Emil Aug 28 '10 at 19:29
  • $\begingroup$ @Emil: Do you have a reference? Anything more recent than the ancient (1995) discussion linked in the OP? $\endgroup$ – Jukka Suomela Aug 28 '10 at 22:46
  • $\begingroup$ @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. $\endgroup$ – Jagadish Aug 29 '10 at 7:37
  • $\begingroup$ 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. $\endgroup$ – Suresh Venkat Aug 29 '10 at 7:59
16
$\begingroup$

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). 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

$\endgroup$
  • 3
    $\begingroup$ 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: cstheory.stackexchange.com/questions/716/… $\endgroup$ – Tsuyoshi Ito Aug 28 '10 at 21:46
  • $\begingroup$ Serge Gaspers told me that it does (thanks!). I simplified the proof using it. $\endgroup$ – Tsuyoshi Ito Aug 30 '10 at 12:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.