The cutting sticks problem
The name of the problem comes from a popular description by which the problem can be stated:
You are given k sticks with integer length of which the total length of sums up to n(n+1)/2. None 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.
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:
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<=i<=k.
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:
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.
Given by: Dave Rusin.
Consider all of the tuples(n1,n2,...,nk) where k is a natural number and n1+n2+...+nk=n(n+1)/2. k can have several possible values for any possible value of n. Given a value for n, is it possible to represent all tuples as series of disjoint sums of the natural numbers from 1 to n. i.e., n1, n2, ..., and nk can all be represented as disjoint sums of the natural numbers from 1 to n (if n1 = 1 + 2, then n2, n3, ..., and nk don't have 1 or 2 in their defining sums)?
Given by: Chris Hall.
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.
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:
Mails
Sci.math newsgroup.
Rec.puzzles newsgroup.
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
4 <= k <= n/2 + 1
n+1 <= a_i <= 2n-2 (for i in 1 .. k)
a_i >= n+2 (for some i)
n >= 9
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:
(n+2)/4 <= k <= (n-2)/2
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....
n(n+1)/2 >= a_1 >= a_2 ...>= a_k >= n
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 Online Encyclopedia of Integer Sequences as A022541 and A022542.
Possible proofs
There are several ways in which proofs could be constructed. These are:
Proof by induction. This seems to be the most obvious one. It goes like: Can all cases for n be solved, by reducing them to a case for n-1 (or a case for n-2 ...).
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).
Proof by means of an algorithm. Because for a given sets of sticks it seems rather easy to find a solution if you allow some trying, it might be good to find an algorithm that works for all cases.
Proof by probablistic arguments. The number of partition of {1, .., n} grows much quicker then the possible sets of sticks for a given n.
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
1,2,3, ...k-1,k,k,k+1, ... ,n
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
1,1,2,3, ... k-1,k-1,k,k+1, ... n
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:
How about 1,2,3,7,8? Try to remove a stick of length 6. What is considered trivially impossible?
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 :
The set of numbers {1,2,...,n} can be partitioned into k parts with equal sum iff n(n+1)/(2*k) is an integer >= n.
Proof :
The necessity of the condition is obvious. We prove the sufficiency by induction. If n >= 4k-1 we form k pairs (n,n-2k+1), (n-1,n-2k+2), (n-2,n-2k+3),...., (n-k+1,n-k) and put one in each part. Inductively partition {1,2,...,n-2k} into k parts with equal sum to find the partition for {1,2,...,n}. Also if n = 2k-1, the problem can be solved easily.
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.
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:
Let S = floor( n(n+1)/(2*k)). Then the numbers {1,2,...,n} can be partitioned into k parts such that every part has sum = S or S+1 if S >= n.
Before proving this, we will prove a lemma. This lemma is also a special case of the cutting stick problem.
Lemma:
Let n(n+1)/2 = kS + r, n <= S. Then the numbers {1,2,...n} can be partitioned into k parts with sum S and one part with sum r.
Proof:
The proof is by induction on n. If r >= n, we can put n in that part and inductively partition {1,2,...,n-1} into k parts with sum S and one part with sum r-n.
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.
QED.
Proof of theorem:
Now for the proof of the theorem. If n(n+1)/2 = kS+r, with 0 < r < k, then there will be exactly r parts summing to S+1 and k-r parts summing to S. If S >= 2n, we do the same thing as above ( form k pairs with the largest 2k numbers and reduce the problem ). If S < 2n, then the odd number amongst S and S+1 must be < 2n. Suppose S is odd.
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.
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.
1