Unsolved problem [entries|reading|network|archive]
simont

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

Wed 2014-02-19 10:52
Unsolved problem
LinkReply
[personal profile] jackMon 2014-03-10 22:21

Hold on a second. Did you mean that the best dissection involved the shortest fragment being coming from an equal size division of some stick? Or that the best dissection involved SOME stick being equally divided? Because I wasn't sure there was an obvious reason for the first, but the second could still be true (if I've got the right solution for 4<->7)?

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.

Link Reply to this | Parent | Thread
[personal profile] jackTue 2014-03-11 15:12

A more specific conjecture would be that any optimal dissection (in your extended criterion of tie-breaking) of a set of n m-sized sticks and a set of m n-sized sticks into two identical piles of fragments can be performed by a sequence of "Divide (the remainder of) some stick from one set into N (N>=1) equal sized fragments, and removing the corresponding fragments from sticks in the other set. Then repeat, dividing one of the new remainders, until nothing is left."

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.

Link Reply to this | Parent | Thread
[personal profile] simontTue 2014-03-11 16:13

This seems like just the sort of conjecture that we could actually check against the piles of data from the search program! (Which may now be working [crosses fingers], so some data might actually be forthcoming once I've sorted out a way to present it legibly.)

Link Reply to this | Parent
navigation
[ go | Previous Entry | Next Entry ]
[ add | to Memories ]