simont | Unsolved problem

Here's a mathematical sort of question that occurred to me last year. I've been pondering it off and on ever since, but not reached any useful conclusions; and I just came across my file of notes on it, and thought perhaps I should post it somewhere for other people to ponder as well.

Let m and n be positive integers. Suppose you have m sticks of length n, and you want to turn them into n sticks of length m, by cutting them into pieces and gluing the pieces back together. And the tricky bit is that you want to do this in a way that maximises the length of the shortest fragment involved in the dissection.

One obvious approach is to glue all your sticks end-to-end into one long stick of length mn, then cut that into n equal pieces. If you do that, the shortest fragment will have a length equal to gcd(m,n). So that's a lower bound on the solution in general, and in some cases (e.g. m=3, n=2) it really will be the best you can do.

But gcd(m,n) is not always the best you can do. For example, consider m=6 and n=5. The obvious gcd solution gives a shortest fragment of 1, but actually this case has a solution with shortest fragment 2: cut each of the six 5-sticks into pieces of length 2 and 3, then reassemble as three lots of 3+3 and two lots of 2+2+2. (In fact this was the case that first brought the problem to my attention.)

I also know that the best solution will not necessarily involve fragments of integer length. For example, consider m=5 and n=7. If you constrain yourself to only use integer-length fragments, then you can't make the shortest fragment any longer than 1. (If you try to make it 2, then you have no option but to cut up each 7-stick as 2+2+3, but then you have ten 2s and five 3s, out of which you can't make the seven 5s you need without bisecting a 2.) But with fractional fragment lengths you can improve on a shortest fragment of 1, by cutting up three 7-sticks as (8/3 + 8/3 + 5/3) and the other two as (7/3 + 7/3 + 7/3), then reassembling as six lots of (8/3 + 7/3) and one (5/3 + 5/3 + 5/3). So now your shortest fragment is one and two-thirds units long.

So, does anyone have thoughts? Other than the above examples, I haven't managed very many myself. I haven't even come up with a sensible computer search algorithm to reliably determine the best answer for a given m,n pair – so, in particular, I don't even know that 5/3 is the best answer for the example above, only that it's the best answer I know of. I have a vague idea that the best answer generally seems to involve at least one stick (on either the source or the destination side) being cut into equal-length fragments, but I wouldn't be at all surprised to find that wasn't true in all cases.

Threaded | Flat

Have you yet found an example where the (apparent) optimal solution requires dividing any stick into more than three pieces?

Is there any good reason not to consider wlog m<n? Beyond that, I'm too woozy at the moment, which is a pity as this problem is going to bug me without my getting much traction on it!

Is there an obvious limit on the size of the denominator in the best solution for a particular pair? Then at least you could brute force small cases to ensure you have the best answer.

What a nice and curious problem. It's rather startling at first that the answers needn't be integers.

I don't even know that 5/3 is the best answer for the example above,

It seems most implausible that it isn't. Hmm, yes, let's see: in a better solution, each 5 stick must be cut into at most 2 pieces, obviously. The resulting (wlog) 14 pieces must be assembled into five 7-sticks so one 7-stick must get at most two pieces. One of these must be at least 3.5 long. Whichever 5-stick that came from, you had a length of 1.5 left over, which is too short.

Edited 2014-02-21 08:50 (UTC)

[Error: Irreparable invalid markup ('<n [...] half),>') in entry. Owner must fix manually. Raw contents below.]

A friend came over yesterday afternoon and we looked at this and made some progress. I can almost solve it, I think. In practice I can find the solution for given m and n with pen and paper and a small amount of fiddling, but at present this margin is too small to contain the details of the general method :-) But let's look at some examples. Let m<n and let s be the shortest length in the dissection, and t the longest length. We'll promise to never leave an m-stick whole in the dissection (this doesn't affect s, except in the trivial case where n is a multiple of m). With this constraint, t <= m-s.

Let's find s(3,10). If s is *more than*, um, 4/3, then t<5/3 if any 3-sticks are whole in the dissection, just cut them in half), so a 10-stick must be cut into at least 7 pieces (6 isn't quite enough - a tight constraint from t <5/3) and at most 7 (8 lots of 4/3 is too much) so exactly 7, so there are 21 pieces in the dissection. But each 3-stick must be cut in 2, so there are 20 pieces in the dissection, contradiction.

Note that 4/3 is the best number that gives this contradiction, since as I pointed out, the constraint was tight. So although it looked like I plucked it out of the air, I didn't really. Now all we need to do is find a 4/3-dissection, which is simplicity itself (try it).

Ok, let's find s(5,8). If s> ... let's say, 2, then t<3, so an 8-stick must be cut into at least 3 and at most 3 pieces (this time it's the maximum that's tight, from s>2, justifying my choice of the number 2), so there are 15 pieces in all. But the 5-sticks are all in 2 pieces, 16 in all, so s=2 is best, if we can find it. Again, it's easy.

Now let's find s(5,7) (your original example). if s>7/3, t<8/3 and each 7-stick must be in exactly two pieces by the argument above, and the constraint is tight. Can we find a 7/3-dissection? It's quite obvious that we can't after a moment's thought. Oh dear! Our method's gone wrong, so we use the fall-back of cutting m in 3 equal pieces. Can we find a 5/3-dissection? Yes we can, and then we use a slightly fiddlier proof to show that it's best.

Obviously there are a number of magic wands that need to be removed from this to make it a proof, but it seems to work in practice. The basic point is that the space of dissections is quite 'floppy', so if we can find a tight constraint with s>m/2 then there's a good chance we can also satisfy it, and if we can't, then the fall-back to cutting some m sticks into 3 equal parts means there's enough floppiness to do it now.

It wouldn't surprise me greatly if you found some cases where this doesn't work, but the first problem is to find out what it is actually claiming ...

Ok, sorry about earlier brainstorm. When I saw your 7/4 and saw that that was one of the numbers in my calculation, I was hypnotised briefly by my earlier mistake into thinking 7/4 > 9/5.

As usual when one has been staring at something too long, the truth is perfectly simple - I was over-complicating things with that max(). The two min()'s give two constraints, one of which will be too strong (overconstrained), so I should take the lower of them - simply, the min of the 4 quantities. And two of them can be ruled out: n/(p+1) < n/p, and similarly m-n/p < m-n/(p+1), so the latter quantity in each inequality can be discarded.

I.e. if m and n are coprime, m>2, and

p = floor (2n/m)

s' = min [ m-n/p, n/(p+1) ]

Then s' is the bound: s(m,n) <= s' and very often s=s'.

If m=1, s=1. If m=2 and n is odd, s=1. If m = dm', n=dn' for some integer d>1 then s(m,n) = d s(m',n').

Does this agree with what you calculated?

Edited 2014-03-12 21:06 (UTC)

no subject

no subject

no subject

no subject

no subject