Previous Up Next

The cutting sticks problem

The name of the problem comes from a popular description by which the problem can be stated: Obvious assumptions are that you are not allowed to use glue, and that you have an accurate measuring device.

The formal description of the problem consists of proving the following conjecture:

Or in (pseudo) TeX:
   \forall n \in \Nat, (a_1, \dots, a_k) \in \Nat^k
      (       \Sum_{i = 1}^{k} a_i = n(n+1)/2
       \wedge \forall i (a_i \geq n)
      ) \Rightarrow
      \exists P_1, \dots, P_2 \in 2^\Nat
         (        \forall 1 \leq i \leq k (\Sum_{p \in P_i} p = a_i)
          \wedge \Cup_{i = 1}^k P_i = {1, \dots, n}
          \wedge \forall 1 \leq j < k \leq n (P_j \cap P_k = \emptyset
         )

How others formulate the problem are:

The problem is special case of the knapsack problem, which is stated as: given a number of bags with given size, can a number of objects be fitted into the bags. It can also be considered as Discrete Piece Fitting puzzle. I thought that is was shown that the decidability of the knapsack problem is NP-Complete. But although knapsack problems are generally speaking hard to solve the class that we propose here, seems relatively easy to do.

Links

After this page was created in 1995, the problem has been discussed on other forums. Interesting discussions are found at:

Remark from Dan Hoey

From: Hoey
Date: Thu, 21 Sep 95 19:05:30 EDT
Newsgroups: sci.math,rec.puzzles

In the standard encoding, some knapsack problems are easy to solve. In particular, if the total bag size n(n+1)/2 is at most polynomial in the problem size S, then the problem is easy (PTime). This occurs here, since S is at least the number of bags, k. A similar approach forces me to withdraw my comment that Saeger's method requires an exponential search.

I should notice that this problem admits a much more compact encoding, with only the parameter "n" being specified in log(n) bits, since we are implicitly quantifying over all the appropriate partitions of n(n+1)/2. Of course, if the conjecture is true, there is a constant-time recognizer. And if not, there is a O(log(n)) time recognizer, though we may not be able to prove what it is.

What others said

Subject: Re: cutting sticks problem (puzzle)
Organization: Space SystemsLoral
Date: Fri, 15 Sep 95 15:30:48 MET DST
Playing with examples I have convinced myself this cutting can always be done. There is just too much freedom generated by all the short sticks to have any trouble. Unfortunately, I haven't found any way to get started on a proof.

Collected postings and mails

In the following files, the original mails and postings can be found:

Reducing the number of cases

With some thinking it turns out that the problem space can be reduded:
From: (Mike Williams)
Newsgroups: rec.puzzles,sci.math
Subject: Re: cutting sticks problem (puzzle)
Date: Fri, 15 Sep 95 23:35:29 MET DST
Organization: Sounds Riscy
Suppose that the hypothesis is false. Choose the smallest counterexample.

We know that this set of sticks has no stick of length less than n, but we can see that it can't contain a stick which is actually length n either.

If there was a stick with length n, we could remove it and have a set of sticks of total length (n-1)n/2 containing no stick shorter than n-1. Since we chose n to be the smallest counterexample this smaller set must be cuttable into a series 1, 2.. n-1. By adding back the stick of length n this gives us a cutting for the original set of sticks.

Similarly a minimal counterexample can't contain a stick >= 2n-1, otherwise we could cut that stick into one of length n (which we remove as before) and one >= n-1, leaving only sticks >= n-1.

From: (Chris Hall)
Newsgroups: rec.puzzles,sci.math
Subject: Re: cutting sticks problem (puzzle)
Date: Sat, 16 Sep 95 22:06:41 MET DST
Organization: University of Colorado, Boulder
I had managed to deduce that much myself by trying to come up with an inductive proof. i.e., assuming that you can cut the sticks of total length n(n+1)/2, can you cut sticks of length (n+1)(n+2)/2. If you add the new length of n+1 as a new stick (and thus all the sticks in the n stick case must be length >= n+1), then it's easy to split for n+1 sticks (when I say n+1 sticks I mean n+1 resulting sticks, not necessarily n+1 starting sticks). If you add the n+1 length to any of the sticks in the n sticks case then that stick will be >= n+(n+1) long and it's easy to see that you could just cut off the length of n+1 and have the length n case. Thus, you must consider the case where the n+1 units of length are distributed across the sticks from an n stick case and that each stick is less than 2n-1 units of length (as you stated).

Date: Tue, 19 Sep 95 03:01 BST-1
From: (Hugo Van der Sanden)
Subject: Cutting sticks problem
I find this problem intriguing, and while I haven't found a proof I've managed to restrict it slightly: if the initial sticks are the set A, consisting of a_1, a_2 .. a_k, then If any of these conditions are not satisfied, either there is an easy proof that a solution exists, or the problem can be reduced to another with smaller n.

(Note, that I haven't resolved all the possibilities for k=3 yet, but from what I have established so far I feel that they should all be reasonably easy.)

From: hoey
Date: Thu, 21 Sep 95 19:05:30 EDT
To: (Frans F.J. Faase)
Newsgroups: sci.math,rec.puzzles

The first inequality can be made sharper by using the second and third inequalities:

This is actually a little looser for n=9,10, but computer search has already shown n >= 26.
From: Rod Hynes
To: faase
Subject: proving special cases of sticks - insights into general case?
Date: 	Thu, 21 Sep 1995 12:49:14 -0400
We have seen proofs for (trivial) cases k = 1 and k = max. Perhaps proofs for other special cases will give some insight into the general problem. Here is a proof for (easy) case k = 2:

(some credit to Hai Wang, who is also thinking about this problem)

say sticks are length l1, l2 let S = {1..n} and S1 u S2 = S and S1 n S2 = 0 choose S1 s.t. sum(S1) = l1 (*) sum(S1) + sum(S2) = sum(S) = n(n+1)/2 = l1 + l2 sum(S1) + sum(S2) = l1 + l2 sum(S2) = l2

(*) prove that you can choose some subset of {1..n} to add up to l, where l <= (n-1)n/2:

n,(n-1,1),(n-2,2),.. gives (n+1)/2 subsets of {1..n} which add to n we know l = cn + d where 0 <= c <= (n-1)/2 and 0 <= d < n so take (n-d,d) from the subsets which add to n and you still have (n-1)/2 subsets which add to n, enough for any c.

so for k = 2, if you fix one stick, the other follows. Unfortunately, it does not seem that for k = 3 that fixing 2 sticks means the 3rd stick follows as easily as it does here.

Algorithms

For my own experiments with programs see gen.c.

From: (Mike Williams)
Newsgroups: rec.puzzles,sci.math
Subject: Re: cutting sticks problem (puzzle)
Date: Fri, 15 Sep 95 23:35:29 MET DST
Organization: Sounds Riscy
It looks like the following algorithm might always produce a cutting that works.

Cut the longest stick you require from the shortest remaining piece which is long enough to contain it.

E.g. in the case of sticks of length 11, 9, and 8.

Cut length 7 from the 8, leaving  11 9 1
Cut length 6 from the 9, leaving  11 3 1
Cut length 5 from the 11 leaving   6 3 1
Cut length 4 from the 6, leaving   2 3 1
Get length 3 from the 3, leaving   2   1
Get length 2 from the 2, leaving       1
Get length 1 from the 1
From: (Ian Hawthorn)
Newsgroups: sci.math
Subject: Re: cutting sticks problem (puzzle)
Date: 18 Sep 95 14:15:40 +1200
Organization: University of Waikato, Hamilton, New Zealand
Unfortunately this does not always work. Consider the case of three sticks of lengths 12,19, and 24. These add to 55 = 1+2+3+4+5+6+7+8+9+10. Apply the algorithm as follows:
Working sticks		Finished sticks
12  19  24
2   19  24		10
2   10  24		10 9
2   2   24		10 9 8
2   2   17		10 9 8 7
2   2   11		10 9 8 7 6
2   2   6		10 9 8 7 6 5
2   2   2		10 9 8 7 6 5 4
>>> Failure - No stick of length 3

However note the following:

24 = 10     + 8                 + 3 + 2 + 1
19 =      9         + 6     + 4
12 =              7     + 5
So we don't have a counterexample to the original conjecture.
From: (Dave Rusin)
Newsgroups: rec.puzzles,sci.math
Subject: Re: cutting sticks problem (puzzle)
Date: Sat, 16 Sep 95 10:20:43 MET DST
Organization: Northern Illinois University, Math
Still no answer but some comments.

This is a sort of knapsack problem. Another related problem appeared on the Mathematical Competition in Modelling about 5 years ago (loading railroad cars). But there's just enough extra structure in this one that conceivably a solution can be proved to exist.

I got to the same point. I decided to have my computer consider the other cases. We might as well assume the a_i are listed in non-decreasing order, so the conditions are that each a_i <= a_(i+1); a_1 >=n+1; a_k <=2n-2; and Sum(a_i) = n(n+1)/2. Just for the record, if my program is OK, here's the count of the number of such sequences:

n       2  3  4  5  6  7  8      9      10     11     12     13
#seq    0  0  1  1  1  4  7      9      21     41     73     147
log_2   -  -  0  0  0  2  2.807  3.170  4.392  5.358  6.190  7.200

n      14     15     16      17      18      19      20      21
#seq   288    557    1111    2193    4343    8728    17483   35063
log_2  8.170  9.121  10.118  11.099  12.084  13.091  14.094  15.098
I leave it to the reader to state and prove the appropriate conjectures.

Incidentally, the bounds on the a_i show that k must be between n/4 and n/2. I like to think of the "generic" case as having k=n/3 sticks each of length roughly (3/2)n .

I tried to encode a couple of algorithms which would take such a sequence and compute a partition. For example, the previous poster suggested

Cutting the longest stick from the shortest remaining piece which is long enough to contain it, fails when presented with stick lengths 11 12 16 16 (n=10). Hoping to reduce the number of short pieces left over from cutting, I considered the opposite approach: cut the longest piece you require, taking it without cutting if there is a piece of that length already, but otherwise cutting from the _longest_ possible piece. This fails too (e.g. for 10 10 12 13 -- n=9).

In the end I had the best luck simply randomizing: cut the longest required pieces first, but cut each from a stick selected at random from among the pieces which are long enough. (Again, I instruct the computer to avoid cutting when a piece already has the right size.) Unless I coded it wrong, this succeeded in finding a solution for _all_ sequences of with n less than 22. The worst offenders are those with many boards nearly as short as possible; for example, with n=21 and k=10, the program needed 138 attempts to find a solution in the case (22, 22, 22, 22, 23, 23, 23, 23, 23, 28) using this randomizing method. Incidentally, odd n appeared to require slightly more attempts in general than even n.

The fact that the randomizing method worked so thoroughly -- and almost always quite quickly -- suggests that really _plenty_ of solutions exist, so it likely takes little ingenuity to find a solution for most partitions.

Upon examining the failures or hard cases for any particular algorithm, one can devise additional methods to handle certain configurations (e.g. in the last sample mentioned above it pays _not_ to cut the 10 longest pieces each from a different stick), but I cannot prove that I have a sufficient collection of tricks yet to guarantee success in all cases. A fun but frustrating problem.

From: (Dave Ring)
Newsgroups: rec.puzzles,sci.math
Subject: Re: cutting sticks problem (puzzle)
Date: Sun, 17 Sep 95 17:19:19 MET DST
Organization: None
A nice analysis. Here is an algorithm which works pretty well:

Break the smallest stick almost in half thus making two of the midlength bars (final sticks). From there, always use the smallest possible stick to make the midmost possible bars.

This algorithm is slightly trickier for odd n, because then the exact middle bar has to wait till the end.

All the counterexamples I could find were doable by starting with the biggest sticks instead of the smallest.

From: "K.J.Saeger"
Newsgroups: rec.puzzles
Subject: cutting sticks - an algorithm?
Date: Mon, 18 Sep 95 23:22:41 MET DST
Organization: IDA, Alexandria, Virginia
I believe that I have an algorithm that will successfully solve the stick cutting problem, but I have yet to find out why.

Let's take the sticks in non-increasing order....

Define: c(i,j) = 1 if stick a_i is used to produce a cut length of j, and 0 otherwise.

Begin with the longest stick, a_1.

     j=n
     ____
     \
a_1 = >    c(1,j)*j
     /___
    j = 1
Of all possible combinations of c(1,j) choose the set that minimizes the function:
    j=n
    ____
    \
F1 = >    c(1,j)*2^(-j)
    /___
    j = 1
Repeat for all sticks Li, remembering that the Sum on i of c(i,j) = 1 for each j (this means that exactly 1 stick of length 1 is produced). Which is to say, we minimize Fi over all partitions of Li that do not conflict with the already chosen partitions of L1,L2,...,L(i-1).

Case n = 8 and m = 4

L1, L2, L3, L4
12,  8,  8,  8   Groups:  (5,7),   (8), (2,6), (1,7)
11,  9,  8,  8            (5,6), (2,7),   (8), (1,3,4)
10, 10,  8,  8            (4,6), (3,7),   (8), (1,2,5)
10,  9,  9,  8            (4,6), (2,7), (1,8), (3,5)
 9,  9,  9,  9            (4,5), (3,6), (2,7), (1,8)
Note that this algorithm does not work if you take the sticks from smallest to largest. (There is a Fortran program that implements the algorithm.)

Perhaps the proof can be based on a binary representation of the system (as suggested by function F)?

From: (Dan Hoey)
Date: Thu, 21 Sep 95 13:48:42 EDT
I'm sorry, but function F does not suggest "binary representation" to me. All it means is that we maximize the minimum part of Li, breaking ties by maximizing the next smallest part, and so on. To see that this is so, just verify that 2^-i > 2^-(i+1) + 2^-(i+2) + ... + 2^-n, so that no way of choosing larger parts can make up for a suboptimal choice of the smallest part. I would say that this is one way of interpreting Dave Ring's suggestion to break successive sticks into the "midmost possible" parts.

This method also fails to be a closed form, because it still involves an exponential search to minimize Fi.

It also fails to be a solution: For n=15, it fails to divide sticks 22, 18, 16, 16, 16, 16, and 16. The first two steps divide 22=12+10 and 18=11+7, which is already insoluble: The numbers 15, 14, 13, 9, and 8 must then be distributed at most one each among the 16s, and then the numbers 6, 5, and 4 cannot all be placed. The problem can be solved as 22=13+9, 18=10+8, 16=15+1=14+2=12+4=11+5=7+6+3. A similar problem occurs when the largest two sticks are 21 and 19. The midmost solution starts by creating the same unsolvable configuration, but a solution exists: 21=12+9, 19=11+8, 16=15+1=14+2=13+3=10+6=7+5+4.

I'm still far from convinced that this problem is solvable in general. I have verified it up to n=24, but I don't have a lot of insight into what can happen with large n.

My own program

I also wrote a program to check all the ways in which all possible set of sticks for a given n can be cut into 1 upto n. It turns out that the possiblities increase with higher values for n. This can be taken as a very strong indication that the sticks can be cut for any n.

Following is a table where the minimun number of cuttings that was found for any set of sticks. I only looked at the hard problems (all sticks between n and 2n-1). The table also lists the minimum number of iso-morphic cutting (iso-min).

   n     problems   min    iso-min
----------------------------------
   6        1         6       1
   7        4         8       4
   8        7        18       1
   9        9        26       6
  10       21        78       1
  11       41        94       7
  12       73       342       1
  13      147       388       9
  14      288      1660       1
  15      557      1728      10
  16     1111      8592       1
  17     2193      8616      12
  18     4343     45068       1
  19     8728     46848      13
  20    17483    267536       1
  21    35063                15
  22    70828                 1
  23   143267
  24   290193                 1
  25   589705
  26  1200646                 1
  27  2448904
  28  5005001                 1
These integer sequences are stored in the The On-Line Encyclopedia of Integer Sequences as A022541 and A022542.

Possible proofs

There are several ways in which proofs could be constructed. These are: Below there are some attempts made by others.

An attempt by Ian Hawthorn

From: hawthorn
Newsgroups: sci.math
Subject: Re: cutting sticks problem (puzzle)
Date: 20 Sep 95 12:07:33 +1200
Organization: University of Waikato, Hamilton, New Zealand
One approach is to strengthen the original problem. I would like to suggest that it might be better to try to prove the analogous problem where the sticks are to be chopped into lengths With the obvious special case when k=0

An inductive proof would then note that no stick of length n can be present. If a unit is chopped from the longest given stick, then by induction the problem can be solved in that case, where k is replaced by k-1. (with obvious modification in the case that k=0). Putting back the unit, we can divide the original sticks into lengths

Imagine the original sticks composed of rods of these lengths. The problem then becomes one of shuffling the rods around so that a rod of length 1 and a rod of length k-1 appear on the same stick. When that happens, they can be `glued' together to solve the problem.

The problem thus is a rearrangement problem. The basic operation of rearrangement consists of finding a number of rods on one stick which add to the same number as a number of rods on another stick. The two subsets of rods can then be swapped. (If sequences of these basic swap operations are inadequate, then more complicated operations could be considered).

The condition that all sticks have length >= n , appears to allow the problem to be solved, because it means that the sticks are long enough to ensure that each stick is made up of enough rods that a sufficient variety of sublengths can be formed from each rod, and thus a large number of swap operations are possible. This makes it highly likely that we will be able to move a rod of length 1 onto the same stick as a rod of length k-1.

Unfortunately, after each swap operation, the swaps which are possible from the new position are different from those which were possible before. This makes it hard to look at an initial position and plan in advance a sequence of swaps which will move a rod of length 1 onto a rod of length k-1.

Perhaps what we need is some integral measure of how far apart the rods of length k-1 and the rods of length 1 are. If we could then show the existence of a swap which decreased this `distance' in any arrangement of rods, then we would be done.

I have not made any progress this way, but I thought I'd toss out the slightly extended version of the problem for comment. If you look at the problem this way, you can see why it is a difficult.

The other possibility is that someone who studies partitions knows some neat neccessary and sufficient condition for one partition to be a subdivision of another that will do the trick.

A remark by Timothy Chow

From: (Timothy Chow)
Newsgroups: sci.math
Subject: Re: cutting sticks problem (puzzle)
Date: Wed, 20 Sep 95 04:08:03 MET DST
Organization: UMich, but the views expressed below are mine not theirs.

(In reply to the last paragraph of the previous section.)

Unfortunately, there is no such general machinery available here. I asked George Andrews and he didn't know the answer to this problem. It is hard to answer specific questions like this about the lattice of partitions ordered by refinement.

My gut feeling here is that if the problem is at all tractable, probabilistic methods are going to be more promising than constructive ones, since there seem to be many different decompositions in any given case.

A remark by Dan Hoey

From: hoey
Date: Thu, 21 Sep 95 19:05:30 EDT
To: (Frans F.J. Faase)
Newsgroups: sci.math,rec.puzzles

For the probabilistic method to have plausibility, we need to also consider the average number of partitions that correspond to the same set of sticks. I have not seen this analysis carried out, nor do I know how to do it. Statements about the apparent amount of "freedom" may not extend to large problems.

A suggestion by Hauke Reddmann

From: (Hauke Reddmann)
Newsgroups: sci.math
Subject: Re: cutting sticks problem (puzzle)
Date: Thu, 21 Sep 95 12:19:23 MET DST
Organization: University of Hamburg, Germany
I suggest that the conjecture is expanded: ALL partitions of n(n+1)/2 which are not trivially impossible to cut down (contain 1+1 or 2+2 or 3+3+1 or 3+3+3+3 or ...) can be cut down to 1+...+n. Maybe now induction is easier. (Or has somebody a counterexample?)
From: (Frans F.J. Faase)
Newsgroups: sci.math,rec.puzzles
Subject: Re: cutting sticks problem (puzzle)
Date: Thu, 21 Sep 95 13:35:09 MET DST
Organization: University of Twente, Dept. of Computer Science

I tried this approach. But it seems difficult to define `trivial impossible'. Or do you have a constructive method of generating this set. Actual what you propose is a characterisation of the set all a_1, .., a_k such that there exists a P_1, .., P_k partition of {1, .., n} and the sum of the numbers in P_i equals a_i for all 1<=i<=k.

A counter example

From: (Hauke Reddmann)
Newsgroups: sci.math
Subject: Re: cutting sticks problem (puzzle)
Date: Fri, 22 Sep 95 12:50:44 MET DST
Organization: University of Hamburg -- Germany
Rolan Christofferson wrote: Point made. I just wanted to emphasize that sticklenghts>=n is not the most global condition for the problem to be solvable. (That's another idea: give a partition which can't be cut to 1+...+n where the longest stick comes as close to n as possible. Anyone programming?)
From: (Hauke Reddmann)
Newsgroups: sci.math
Subject: Re: cutting sticks problem (puzzle)
Date: Mon, 25 Sep 95 14:04:57 MET
Organization: University of Hamburg -- Germany
Oops! Shortest stick, of course. E.g, it looks like 4+(anything not shorter) can always be cut to 1+2+3+4+5.
From: (David M Einstein)
Subject: Re: cutting sticks problem (puzzle)
Organization: The World Public Access UNIX, Brookline, MA
Date: Tue, 26 Sep 95 02:44:34 MET
Is it even possible to count the number of partitions that can be cut into 1+...+n. (Of course its possible....) Does anyone have any ideas on how to count out the duplicates?

Solutions by Ajit Diwan

From: A A Diwan
Subject: Cutting Sticks problem
Date: Mon, 25 Sep 1995 10:17:27 +0530 (IST)
In particular, I have a nice constructive proof of your conjecture when the given sticks are of 'nearly equal' length, that is, any two sticks differ in length by at most 1.

I have also considered the problem of partitioning the numbers {1,2,...,n} into k parts with equal sum and 'nearly equal' cardinalities, ( differing by at most 1) and have recently found a solution to this.

The more general problem of partitioning the numbers {m+1,m+2,..,m+n} into k parts with equal sum is proving to be more difficult. I have a solution to this when gcd(n,k) = 1.

From: A A Diwan
Subject: Re: Cutting Sticks problem
Date: Tue, 26 Sep 1995 17:17:20 +0530 (IST)
The reason I was interested in these problems was that they are very special cases of general NP-Complete problems and solving these may give some understanding of the general problems. By putting restrictions of this kind on NPC problems, many interesting conjectures can be formulated. In the cutting sticks problem, if we replace the numbers {1,2,...,n} by some other set of numbers with some structure, such as {1,4,9,16,...,n^2} or the set of first n primes, the problem becomes even more difficult.

A proof for equal length cases

From: A A Diwan
Subject: Solution for Equal Length Sticks.
To: (Frans F.J. Faase)
Date: Tue, 26 Sep 1995 18:08:11 +0530 (IST)
This is a proof for the cutting sticks problem when all sticks are of equal length. Stated formally,

Theorem :

Proof :

Note that in this solution the cardinalities of the parts are widely different. It is more difficult to find solutions with nearly equally sized parts.

A proof for the near equal case

From: A A Diwan
Subject: Solution for cutting nearly equal sticks.
Date: Tue, 17 Oct 1995 14:45:09 +0530 (IST)
Theorem: Before proving this, we will prove a lemma. This lemma is also a special case of the cutting stick problem.

Lemma:

Proof: Proof of theorem: I tried to generalize this to partitions of the form n(n+1)/2 = k1S1 + k2S2 with S1,S2 >= n but have not been able to do so, so far.


Home | Seemingly Trivial Problems