Unsolved problem (Reply) [entries|reading|network|archive]

[ userinfo | dreamwidth userinfo ]
[ archive | journal archive ]

[personal profile] simont Wed 2014-02-19 10:52
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.

Link Read Comments
Anonymous( )Anonymous This account has disabled anonymous posting.
OpenID( )OpenID You can comment on this post while signed in with an account from many other sites, once you have confirmed your email address. Sign in using OpenID.
Account name:
If you don't have an account you can create one now.
HTML doesn't work in the subject.


Notice: This account is set to log the IP addresses of everyone who comments.
Links will be displayed as unclickable URLs to help prevent spam.