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.
![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
no subject
Hmm, does it? I tried to boil down your method into something I could state in a general way, and then applied that, and for s(4,9) I got what I think is actually the right bound.
If every piece is at least s and at most m-s, then every stick of length n is cut into at least n/(m-s) and at most n/s pieces, hence at least ⌈n/(m-s)⌉ and at most ⌊n/s⌋, hence the total number of pieces P in the dissection must satisfy m⌈n/(m-s)⌉ ≤ P ≤ m⌊n/s⌋. By similarly considering the number of pieces that a stick of length m is cut into, we derive a second inequality n⌈m/(m-s)⌉ ≤ P ≤ n⌊m/s⌋ (identical to the first except that n,m are swapped everywhere they appear except in the divisor m-s). So when s becomes big enough that either of those inequalities is self-inconsistent (with LHS > RHS) or when the two are incompatible (because they define ranges for P that do not meet), there can be no dissection with s that large.
It is true that s=9/5 is a threshold beyond which something goes wrong, namely that the first inequality for P is self-inconsistent (with s > 9/5 we would need 20 ≤ P ≤ 16). But something else has gone wrong before that – at s=7/4 the two intervals stop overlapping (because the first inequality switches from 16 ≤ P ≤ 20 to 20 ≤ P ≤ 20, while the second was at 18 ≤ P ≤ 18 all along). And the computer search data I have says that 7/4 really is the best solution.
I agree with you, on the other hand, that the method doesn't get the exact bound for s(7,8), and hence is not reliable in all circumstances.
no subject
Your account is more complicated than need be because the bound always operates when the m-sticks are constrained to be divided into only two pieces, making the first constraint P=2n. So the n-sticks are presumably going to be divided into about 2n/m pieces, give or take some rounding somewhere. Ignoring the trivial case where m | 2n, set p = floor(2n/m) and by considering the four possible cases we get a bound of
max [ min (n/p, m-n/p), min (n/(p+1), m-n/(p+1)) ]
In the s(4,9) case, p=4 and this gives
max [ min (9/4, 7/4), min (9/5, 11/5) ] = max (7/4,9/5) = 7/4.
(I didn't do this explicit calculation earlier as my brain was full and I hoped to get some work done today, but I have overcome both weaknesses :-)
As we've said, this bound isn't always tight but it seems it very often is. I'd be interested in whether your data has any cases refuting my conjecture that, when the bound isn't tight, s is still >= m/3. Also of course to see if one can characterise the cases where the bound is not tight.
no subject
no subject
No.
I've implemented a piece of Python that computes your bound (that is, computes my statement of it, without attempting to simplify based on this followup) and compared it with all the data I have so far (which is everything up to n=10, and some but not all for n=11).
The complete list of cases I know of in which your bound is not tight (assuming I haven't made any errors in my implementation) is: s(6,7), s(7,8), s(9,10), s(3,11), s(4,11), s(5,11), s(7,11). And in all those cases, we do still have s ≥ m/3.