From: faase@cs.utwente.nl (Frans F.J. Faase) Newsgroups: rec.puzzles,sci.math Subject: cutting sticks problem (puzzle) Date: 12 Sep 1995 07:40:34 GMT You are given some sticks with a total length of n(n+1)/2. Non of the sticks are shorter than n. Can you always cut them into sticks with length 1, 2, upto n, no matter the number of the sticks and their lenghts. I am looking for a proof of this problem. -- Frans J. Faase Vakgroep Informatiesystemen Tel : +31-53-894232 Faculteit der Informatica secr. : +31-53-893690 Universiteit Twente Fax : +31-53-339605 Postbus 217, 7500 AE Enschede, The Netherlands Email : faase@cs.utwente.nl --------------- http://www.cs.utwente.nl/~faase/ --------------------- ============================================================================== From: rusin@washington.math.niu.edu (Dave Rusin) Newsgroups: rec.puzzles,sci.math Subject: Re: cutting sticks problem (puzzle) Date: 16 Sep 1995 08:20:43 GMT Still no answer but some comments. Recently faase@cs.utwente.nl (Frans F.J. Faase) wrote: >You are given some sticks with a total length of n(n+1)/2. >Non of the sticks are shorter than n. >Can you always cut them into sticks with length 1, 2, upto n, >no matter the number of the sticks and their lenghts. Formally: we have a sequence a_1, ..., a_k of integers such that each a_i >= n and Sum(a_i) = n(n+1)/2. We wish to find a partition of {1, 2, ..., n} into disjoint subsets S_i such that for each i, Sum(j , j in S_i) = a_i. 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. In article <19950915.213529.38@econym.demon.co.uk>, Mike Williams wrote: > >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)/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. > >But then I get stuck. 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 >Cut the longest stick you require from the shortest remaining piece which is >long enough to contain it. but this 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. dave ============================================================================== From: dwr2560@tam2000.tamu.edu (Dave Ring) Newsgroups: rec.puzzles,sci.math Subject: Re: cutting sticks problem (puzzle) Date: 17 Sep 1995 15:19:19 GMT Dave Rusin wrote: >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 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. -- Dave Ring dwr2560@tam2000.tamu.edu ============================================================================== Date: Tue, 19 Sep 1995 14:49:14 +0200 From: faase@cs.utwente.nl (Frans F.J. Faase) To: rusin@washington.math.niu.edu Subject: Your program for the cutting sticks problem Hello Dave, Could you send me your program for the cutting sticks problem. I am making a WWW page about the problem. Please have a look at: http://www.cs.utwente.nl/~faase/cutsticks.html Kind regards, Frans [sig deleted -- djr] ============================================================================== The following was (as far as I can tell) never sent or posted. -rw-r--r-- 1 rusin math 2560 Oct 5 16:44 stix.idea (I have also appended the UBASIC program mentioned above:) -rw-r--r-- 1 rusin math 4956 Oct 3 13:49 stix.ub ============================================================================== One contribution - Suppose k sticks of lengths a_i with a_1 <= ... <= a_k. Suppose a_(k-1) is small, that is, a_(k-1) <= 2(n-k+1). Then we can cut the longest pieces we need from the shortest sticks, leaving pieces of now strictly increasing length: 1 <= a_1 - n <= a_2 - (n-1) <= ... <= a_(k-1) - (n-k+2) <= a_k - (n-k+1). Note that the second-to-last has length at most n-k by assumption. Thus, each of these new pieces, with the exception of the last, has the length of one of the other pieces we need to cut. Taking those pieces leaves just the last long one, which must be of length equal to the sum of the pieces still needed; we just cut it up as needed. Thus when beginning the problem we can assume a_(k-1) > 2(n-k+1), so that in particular a_(k-1) = 2(n-k+1) + 2u or 2(n-k+1) + 2u-1 for some u >=1, making a_(k-1) = (n-k+u) + (n-k+2+u) or ...+(n-k+1+u), making this stick, at least, be of a length which allows it to be cut into two parts each of which is needed on the first "round". That is, except for the situation outlined (and solved) in the first couple paragraphs, we may always assume that it's not necessary to cut the k longest desired pieces each from a different stick (and in fact at least one can be cut with no leftover). Remark - let u = n-2k+1, u>=2 except in trivial case. Let R = k - (u choose 2). Then k = (u,2) + R, and n = u+2k-1 = u^2 + 2R-1. Total stick length is (u^2+2R-1)(u^2+2R)/2. If each a_i is 2n-2k+2 -bi = (u^2+u)+2R-bi, then their total is (u^2-u + 2R)(u^2+u+2R)/2 - Sum bi = [(u^2+2R)^2-u^2]/2 - Sum bi. Comparing the two, see Sum bi = R. So sets of stick lengths is specified by giving: u>=2; R in Z; set of b_i in Z, Sum(bi)=R, each bi in [u-u^2-4R+4, u] (Any ai which we know to be at most 2n-2k+1, 2, 3, ... causes b_i to be restricted to at least 1, 0, -1, ...)(e.g. if _all_ ai <= 2n-2k+2, then we have (u,2) +R nonnegative bi which sum to R, which means at least (u,2) have to be zero, and if only this many are zero then all the rest have to be just =1, etc.) This kind of analysis really limits the number of cases in which all the a_i are small. Contribution two -- The average number of pieces into which each stick is cut is n/k, which is between 2 and 4 (only 2 in the extreme cases near those outlined at the beginning). Thus this is unlike a general knapsack problem, in that we don't expect in general to have to cut each stick into very many pieces. (Never 1, never 2 everywhere, never more than 4 on average, probably usually around 3.) ============================================================================== 10 'Given some sticks of integral length at least n, whose total length 20 'is n(n+1)/2, can one cut them into pieces of length 1, 2, ..., n? 30 'Easy induction shows it's enough to consider all stick sets with 40 'lengths between n+1 and 2n-2 inclusive. 50 'Program considers all such stick sets for a given n. Run time: about 60 'an hour for n=22, roughly doubles when n increases by 1. (33MHz 486) 70 'Program written in BASIC variant called UBASIC (allows integers of 80 'unlimited size. Available at oak.oakland.edu and other SimTel mirrors. 90 'Written by Dave Rusin rusin@math.niu.edu. Last revised 1995/9/19. 100 ' 110 cls 120 print "Given sticks of integral length at least n, whose total length" 130 print "is n(n+1)/2, cut them into pieces of length 1, 2, ..., n" 140 print 150 print "Enter n, where n(n+1)/2=total length. n="; 160 input N 170 dim A(N):' collection of stick sizes 180 dim B(N):' (same, for recursive use) 190 M=(N*(N+1))\2 200 M1=N+1:' min stick length 210 M2=N*2-2:' max stick length 220 Numok=1024:' how many attempts before we give up? 230 randomize 240 Configs=0:' how many sets of sticks? 250 Tsum=0:' how many random-cut attempts made? 260 ' 270 'We consider every possible collection of sticks for this n. 280 ' 290 for K=M\M2 to M\M1:' k=no. of sticks 300 if M2*K1 then 450:' ...unless of course you've cut them all 700 if Trials<2*N then 720:' what I (arbitrarily) call "tough cases" 710 for I=1 to K:print A(I);:next I:print "took";Trials;"tries" 720 Tsum=Tsum+Trials 730 ' 740 'tada! -- got this configuration diced up. Now let's make the next. 750 ' 760 I=K-1:' decide where to increase a(i) next 770 if A(I)0 then 770 else 880 800 U=I:' 1st index down by 2 or more from a(k) 810 Su=0:for I=U to K:Su=Su+A(I):next I 820 A(U)=A(U)+1:Su=Su-A(U):' Su=how much to distribute in other stix? 830 S=1+((K-U)*M2-Su)\(M2-A(U)):' (distribute with pattern like very first) 840 for I=U+1 to U+S-1:A(I)=A(U):next I 850 A(U+S)=Su-(S-1)*A(U)-(K-U-S)*M2 860 for I=U+S+1 to K:A(I)=M2:next I 870 goto 360:' go to chop up this next configuration 880 next K 890 print "Checked";Configs;" configurations" 900 print "Average number of random trials needed to chop successfully="; 910 print Tsum/Configs 920 end:' task complete! 930 ' 940 'note: n=25: solved 589705 configurations after about 7 hours on PC 950 'note: even with n=25 at least half of the configurations successfully 960 'chopped with the first random pattern. 970 'note: n=50: there are 24550320 configurations just with k=14 980 '