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
On the other hand, 'you can calculate it somehow or other' actually makes it rather less useful, since you can also calculate the exact value of s!
To be clear, I was only trying to find the optimum value of s' such that for any greater s', the number of pieces that n-sticks are divided into would be constrained to an exact number, Q say, giving exactly Qm pieces in the dissection. Provided that this s'>m/3, the m-sticks are simultaneously constrained to be in 2 pieces, giving 2n pieces. Since by hypothesis m doesn't divide 2n, these two constraints are incompatible (Qm =/= 2n).
So actually, you were flattering me by saying my bound for s(5,7) would be 5/3. It would actually be 7/4. (Not 7/3, as I wrongly claimed above.) If s>7/4, then t<13/4 and the 7-sticks are constrained to be in exactly 3 pieces (P=15), whereas for a lower s, 4 pieces are possible (15<=P<=20). As you rightly noticed, in this particular example, in either case the fact that the 5-sticks are constrained to be in 2 pieces gives P=14 which is a contradiction, but I wasn't so optimistic as to expect to be able to get an exact expression for the bound which took account of that.
What I *can* prove is that the *max* of the two numbers I gave is a bound, i.e.
max [m-n/p, n/(p+1) ]
But this bound is almost always too strong. In fact, just considering the n-sticks alone you find there is no possible dissection, except in the special case where the two terms in the max are equal (for example for s(5,6), where they are both 2). Except in that special case therefore, this is higher than the bound I was looking for. At least it's something, though.
I still feel in my bones that there should be a reasonably accessible expression for the bound I'm after, if not for the (better) one which you have actually calculated, but it's more messy than I had hoped.
no subject
To further clarify, the bound thus obtained is only *just* too strong - you get a pair of constraints Q<=p and Q>p. So the next boundary-point down is the one you want. I wrongly hoped that this would be the other element in the min(), but as the s(5,7) case shows this isn't remotely true.
no subject
Or rather, "since this s'>m/3", as it always is. If s'<=m/3, t>=2m/3, i.e. the longest length is at least twice the shortest length and there can't be a simple counting argument that means you can't fill up an n-stick. You just fill it up with copies of t until you get stuck; then you remove your last copy of t and fill up the remaining gap with two equal sized sticks, which are obviously shorter than t and longer than s.