Unsolved problem
simont

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

 Wed 2014-02-19 10:52
Unsolved problem
 Thu 2014-02-20 11:16

Hm. My guess would have been that the best dissection is rational, but isn't always equal sized. But I've not tried it at all, just read what you wrote here.

 Fri 2014-02-21 15:23

Aha, now I think I've got a proof of rationality. Suppose we have some dissection containing an irrational fragment. We will show it isn't optimal (under my extended criterion that if two dissections' shortest fragment lengths are equal then you tie-break by looking at the second shortest distinct length and so on).

Choose a basis B for R as a vector space over Q, and choose it so that it includes an actual rational q. Write every fragment length in the dissection as its unique weighted sum of elements of B. Rational lengths will therefore be represented as straightforward multiples of q.

The shortest irrational fragment length, being irrational, must have a nonzero coefficient for at least one element of B that isn't q; let b be such an element. Look at the coefficients of b across all fragments of the dissection. They must sum to zero in every input and output stick (because those sticks' lengths are all rational, hence have zero coefficient of everything other than q). So if we pick any real ε and adjust every fragment length by ε times its coefficient of b, we must get a system of adjustments that preserves every input and output stick length, and which always adjusts equally long sticks by the same amount. So in particular we can choose ε so that it has the correct sign to slightly increase the shortest irrational length (and has absolute value small enough not to make any two lengths cross over each other), and then applying those adjustments yields a strictly better solution.

Hence, no dissection with any irrational fragment can be optimal (under the extended criterion including tie-breaking), and in particular no dissection with an irrational shortest fragment can be optimal even under the original criterion. []

(Slightly icky because it uses the Axiom of Choice, almost certainly unnecessarily. But AC is obviously true, right? So no problem really. :-)

 Mon 2014-03-10 13:14

I now actually read this proof, and it sounds right to me, though I don't guarantee I haven't missed some exception.

What confused me in the pub is, you use the axiom of choice to get a basis for R over Q. But don't you just need a basis over Q for the vector space generated by the fragment lengths you actually have, not over any possible irrationals? Isn't that just some subset of the fragment lengths, throwing away any non-linearly-independent ones?

 Mon 2014-03-10 13:33

Ah! Yes, good thought. And that vector space is finite-dimensional, because we have at most finitely many frag lengths, and hence we don't need AC to conclude that it has a basis. Well done.

 Sat 2014-03-08 00:32

Ian has written a fairly shiny search program which confirms your guess that the best dissection is not always equal-sized. 7 into 4 has minimum fragment 5/3, which is not an integer fraction of either stick length. So much for my conjecture.

(I leave the exact dissection of 7 into 4 as an exercise, but it shouldn't be hard given the minimum length :-)

 Mon 2014-03-10 13:18

Ah! Very cool. I'm glad someone wrote a search program :)

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.

 Mon 2014-03-10 13:32

Stupid question, if the search program finds a best answer, how does it show that's the best?

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.

 Mon 2014-03-10 14:20

Ah! Thank you. I couldn't see how the program would find it, I assumed it was obvious in some other way, but that approach makes sense even if it's brute force. It's considerable progress to be able to find optimal solutions at all.

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.)

 Mon 2014-03-10 14:26

We're still working on getting the searcher to be both fast and accurate :-/ (I know it's missing at least one optimal solution in its current state.) When I have a large amount of data I more or less trust, I'll post it somewhere.

 Mon 2014-03-10 14:32

I know it's missing at least one optimal solution in its current state.

Oops! I hope it comes into shape.

 Mon 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.

 Tue 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.