88
$\begingroup$

This was asked on sci.math ages ago, and never got a satisfactory answer.

Given a number of sticks of integral length $ \ge n$ whose lengths add to $n(n+1)/2$. Can these always be broken (by cuts) into sticks of lengths $1,2,3, \ldots ,n$?

You are not allowed to glue sticks back together. Assume you have an accurate measuring device.

More formally, is the following conjecture true? (Taken from iwriteiam link below).

Cutting Sticks Conjecture: For all natural numbers $n$, and any given sequence $a_1, .., a_k$ of natural numbers greater or equal $n$ of which the sum equals $n(n+1)/2$, there exists a partitioning $(P_1, .., P_k)$ of $\{1, .., n\}$ such that sum of the numbers in $P_i$ equals $a_i$, for all $1 \leq i \leq k$.

Some links which discuss this problem:

  • 0
    Is it allowed to break a stick or two? :)2010-08-16
  • 11
    My interpretation: all sticks' length are ≥ n, and the number of stick is variable. For example, if n = 5, then the stick lengths may be {15}, {10,5}, {9,6}, {8,7} or {5,5,5}. Then we try to break these sticks into {1,2,3,4,5}.2010-08-16
  • 1
    @Kenny, Yes, that is correct.2010-08-16
  • 2
    @Deinst: Did you see this link : http://www.iwriteiam.nl/cutsticks.html. I think the same problem is posted there.2010-08-16
  • 0
    Looks like that page contains a lot of ideas but no proof either. If this is open, it should go on Peter Winkler's list of "Open Puzzles"! :-)2010-08-16
  • 1
    @Chandru I'm surprised that page has lasted this long. (If you read it you will see that it is a summary of the sci.math posts from ages ago that I referred to.) I figured it needed marketing.2010-08-16
  • 0
    @Deinst: No problem. I googled it and i got it.2010-08-16
  • 2
    You could check MathOverflow2010-08-16
  • 1
    This was [posted to cstheory](http://cstheory.stackexchange.com/questions/709/cutting-sticks-puzzle) two weeks later as a complexity problem (apparently due to a misunderstanding by the OP). There's no progress towards a solution there, just a proof that the problem without the restriction to lengths $\ge n$ is NP-complete.2011-09-17
  • 3
    I wonder if there is an analytic way of approaching this, similar to the use of the circle method in Waring's problem? The number of ways of partitioning the set $\{1,\ldots,n\}$ to give lengths $a=(a_1,\ldots,a_k)$ can be written as $$\int_{[0,1]^k}e^{-2\pi ia\cdot x}\prod_{r=1}^n(e^{2\pi irx_1}+\cdots+e^{2\pi irx_k})\,dx_1\ldots dx_k.$$ Maybe it is possible to approximate this integral and show that it is nonzero for $a$ satisfying the required conditions?2011-09-18
  • 0
    @KennyTM: The number of sticks, $k \le \left \lfloor \frac{n+1}{2} \right \rfloor$2011-09-19
  • 0
    Note that we don't need to consider configurations with _long_ sticks longer than $2n-1$, since a solution for a configuration with one or more long sticks can be constructed from a solution for some configuration without long sticks by combining sticks. (This is unrelated to the observation below about _hard_ configurations, which is concerned with a particular approach to a possible proof.)2011-09-20
  • 0
    @David: I don't see the difference. Isn't your argument the same inductive argument as the one I cited, just perhaps stated slightly less formally?2011-09-24
  • 0
    @Joriki: I don't think so. Suppose we have a solution for all _short_ $n$-configurations (without long sticks), then we have a solution for _all_ $n$-configurations (by cutting $n$ from sticks of length at least $2n$). This is true even if we don't have a solution for $(n-1)$-configurations. (So, for example, a proof of the conjecture for some subset of $\mathbb{N}$ only needs to consider short configurations.)2011-09-26

5 Answers 5