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
(I leave the exact dissection of 7 into 4 as an exercise, but it shouldn't be hard given the minimum length :-)
no subject
I'm flattered you call my comment a conjecture, when it was only really saying I wasn't convinced by your conjecture. But I'm glad we found an answer deciding it :)
Stupid question, if the search program finds a best answer, how does it show that's the best? Is there an obvious limit on something? Previously we seemed to have no way of clearly showing an answer _is_ the best, except by special-case proofs like writing-hawk's.
no subject
Not a stupid question at all, since nobody else had thought of an answer to that problem!
Ian's basic idea is to start by (WLOG) assuming each input stick contributes at most one piece to each output stick (clearly if that's not true then you can merge fragments until it is without making your score worse). So now you have an n × m matrix of fragment lengths. Next, we want to treat the problem as a linear-programming optimisation exercise, trying to maximise one variable ("smallest nonzero matrix entry") under a collection of linear constraints (matrix entries all positive, rows and columns sum to the right thing). The trouble with that is that it's not actually a linear problem, since the objective criterion is nonlinear (taking min of all the matrix entries isn't a linear function). But if you knew the adjacency matrix (that is, you knew which input sticks contribute at all to which output sticks) it would be, because you could introduce the minimum frag length itself as an extra variable, so that some matrix elements were constrained to zero and others were of the form (min_frag + some positive extra value). So Ian simply iterates over all possible adjacency matrices and appeals to a linear-programming library to solve that optimisation problem for each one, and once he's gone through all possible matrices then he knows he's considered every answer!
Of course, then you optimise as hard as you can (by e.g. iterating over adjacency matrices in a sensible order that means you see the best ones first, stopping as soon as your matrix gets too dense because then some stick has to be cut into enough pieces that the smallest won't beat your existing best answer, parallelising over all the CPUs you can find, etc). But that's the basic idea.
no subject
Has any pattern emerged in the results found?
I wonder if it's possible to make any theoretical progress following the same approach? (But I'm just speculating I haven't even had time to start thinking about it yet.)
no subject
no subject
Oops! I hope it comes into shape.
no subject
Or rather, what happens if you try to increase all the shortest lengths by epsilon? That obviously fails if several of them compose a single stick. That's what you were trying to explain to me before. But if you follow through adjusting all other stick lengths epsilon as you described, it has to fail *somewhere* or you didn't start with a local optimum. Another way it could fail is if the *complements* of the shortest fragments are equal divisions of a stick. But there may be other ways as well, if you end up with a stick made of fragments that all have to get longer or all have to get shorter, but came from a different number of steps from the original perturbation.
But if the optimal solution for some division is 5/3, I can't help but wonder if that means *something* has to be divided into three equal pieces.
I wonder if this might be easier to imagine looking at perturbing a matrix as you described, instead of sticks.
no subject
I don't think that's worded quite right, but I think something like that. If so, maybe a perturbations argument could show that if at some step you divide into the same number of fragments of slightly different lengths, you can follow through the remainder of the steps in the same way. And if so, the non-equal division would be sub-optimal (because one stick of that length gets shorter).
But I'm not sure if that's actually right, or just another plausible guess that will turn out to have exceptions.
no subject