The formal description of the problem consists of proving the following conjecture:
\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:
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.
Subject: Re: cutting sticks problem (puzzle) Organization: Space SystemsLoral Date: Fri, 15 Sep 95 15:30:48 MET DSTPlaying 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.
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 RiscySuppose 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, BoulderI 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 problemI 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
(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:
From: Rod Hynes To: faase Subject: proving special cases of sticks - insights into general case? Date: Thu, 21 Sep 1995 12:49:14 -0400We 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.
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 RiscyIt 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 ZealandUnfortunately 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 + 5So 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, MathStill 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.098I 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: NoneA 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, VirginiaI 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....
Begin with the longest stick, a_1.
j=n ____ \ a_1 = > c(1,j)*j /___ j = 1Of all possible combinations of c(1,j) choose the set that minimizes the function:
j=n ____ \ F1 = > c(1,j)*2^(-j) /___ j = 1Repeat 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 EDTI'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.
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 1These integer sequences are stored in the The On-Line Encyclopedia of Integer Sequences as A022541 and A022542.
The application of this technique has reduced the number of difficult cases. (We only have to look at cases where all a_i are between n and 2n-1.).
But as induction fails, we might decide to extend the set of problems we try (by allowing cases for which some a_i <= n).
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 ZealandOne 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
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
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.
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.
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.
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, GermanyI 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.
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 -- GermanyRolan Christofferson wrote:
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 -- GermanyOops! 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 METIs 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?
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.
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 :
If 2k-1 < n < 4k-1 then n < n(n+1)/(2*k) = S < 2n.
Now form the pairs (n,S-n),(n-1,S-n+1),(n-2,S-n+2),.....
If S is odd the last pair formed will be ((S-1)/2,(S+1)/2). These pairs will form some k1 parts summing to S, and the remaining k-k1 parts can be obtained inductively by partitioning {1,2,...,S-n-1} into k-k1 parts with sum S each.
If S is even, the last pair formed would be ( S/2-1,S/2+1) with the number S/2 left. If k1 parts are obtained this way, the remaining k-k1 parts can be obtained by inductively partitioning S-n-1 into 2*(k-k1)-1 parts with sum S/2 each, which together with the number S/2 give 2*(k-k1) parts summing to S/2. Pairing these up arbitrarily gives k-k1 parts with sum S each.
It can be verified that the inductive step can be carried out correctly at each step, since the sum required of each part is >= the largest remaining number.
From: A A Diwan Subject: Solution for cutting nearly equal sticks. Date: Tue, 17 Oct 1995 14:45:09 +0530 (IST)Theorem:
Lemma:
Hence, we can assume r < n. If S >= 2n, we form k pairs (n,n-2k+1),(n-1,n-2k+2),..., (n-k+1,n-k) and put one in each of the k parts with sum S. Inductively partition {1,2,...,n-2k} into k parts with sum S-(2n-2k+1) and one part with sum r. It can be verified that S-(2n-2k+1) >= n-2k so that this step can be carried out correctly.
Suppose S < 2n. Now form the pairs (n,S-n), (n-1,S-n+1),...
If S is odd, the last pair formed is ((S+1)/2,(S-1)/2)). This will form some k1 <= k parts summing to S ( since r < n <= S ). The remaining k-k1 parts can be obtained by partitioning {1,2,...,S-n-1} into k-k1 parts with sum S and one part with sum r.
If S is even, the last pair formed is (S/2+1,S/2-1) and the number S/2 is left. If k1 <= k parts are obtained this way, partition {1,2,...,S-n-1} into 2*(k-k1)-1 parts with sum S/2 ( if k1 < k ) and one part with sum r. Pair up the parts summing to S/2 ( and the number S/2) to form k-k1 parts summing to S and one part summing to r.
This step is essentially the same as for equal sums except for the case r >= n.
Start forming the pairs (n,S-n), ( n-1,S-n+1)... Now two possibilities can arise. Either the last pair formed is ((S+1)/2,(S-1)/2)) and k1 <= k-r parts summing to S have been obtained this way. Now the problem can be solved inductively by partitioning {1,2,...,S-n-1} into k-r-k1 parts summing to S and r parts summing to S+1.
The other possibility is that k-r pairs get formed giving all the required number of parts summing to S. Let the last pair formed be (n1, S-n1). Now form the pairs (n1-1,S-n1+2) which sum to S+1, leaving out the number S-n1+1. Since S+1 is even the last pair formed will be ((S+1)/2+1,(S+1)/2-1). If k1 pairs are formed this way we find the remaining r-k1 parts summing to S+1 by partitioning {1,2,....,S-n-1} into 2*(r-k1-1)-1 parts summing to (S+1)/2 and one part summing to n1(Lemma). Pair up the parts summing to (S+1)/2 together with the number (S+1)/2 to find r-k1-1 parts summing to S+1, and pair up the part summing to n1 with the number S-n1+1 which was left out to get one part summing to S+1.
This finally completes the proof.