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

Improve this question
$\endgroup$
6
  • 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, 2010 at 18:18
  • $\begingroup$ It is an unsolved problem to determine if this is always possible. $\endgroup$
    – Emil
    Aug 28, 2010 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, 2010 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, 2010 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, 2010 at 7:59

1 Answer 1

Reset to default
15
$\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

Improve this answer
$\endgroup$
2
  • 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, 2010 at 21:46
  • $\begingroup$ Serge Gaspers told me that it does (thanks!). I simplified the proof using it. $\endgroup$
    – Tsuyoshi Ito
    Aug 30, 2010 at 12:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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