Unsolved problem
simont

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

 Wed 2014-02-19 10:52
Unsolved problem
 Wed 2014-02-19 15:10

there's probably some situation in which you can find a closed loop of those local perturbations that never touch a minimal fragment, in which case you can apply that change with irrational ε to get a partially irrational and equally good answer

In fact, yes, the 7/5 example in my original post admits just such a transformation. Where we previously dissected three 7-sticks as (8/3 + 8/3 + 5/3) and the other two as (7/3 + 7/3 + 7/3), we now do:

• two lots of (8/3+ε) + (8/3−ε) + (5/3)
• one unmodified (8/3) + (8/3) + (5/3)
• two lots of (7/3+ε) + (7/3−ε) + (7/3)
which reassembles as:
• two lots of (8/3+ε) + (7/3−ε)
• two lots of (8/3−ε) + (7/3+ε)
• two lots of (8/3 + 7/3)
• one lot of (5/3) + (5/3) + (5/3) as before.
And then you can set ε = π/1000 or some such and you have some irrational pieces – but not interestingly irrational.

At a guess, you can probably rule this out by introducing a tie-breaking rule, in which solutions with the same shortest fragment length are now compared by their second shortest, and so on. That'd probably put a stop to frivolous irrationality :-)
 Fri 2014-02-21 13:08

Because you have to match up the + and - irrationals I don't think you get a longer smallest stick doing this; although obviously you can have the same-length smallest stick.

I've written a thing that looks for integer solutions; but it's slow and crap and obviously "I searched exhaustively and found this" is much less interesting than "I thought really hard about it and realised that all solutions look like this". Also it can't handle irrationals and so far can do fractions only where all stick-fragments share a denominator....

 Fri 2014-02-21 13:46

Indeed, you certainly can't get a longer smallest stick by small perturbations of that answer, because one of the 5-sticks is entirely made up of smallest-fragments and so if you lengthen them all by any ε > 0 then that stick overflows. What I was hoping to show was that the converse is also true – that the only way in which a dissection can be locally optimal is if some stick is made up entirely of smallest-fragments, by showing that in all other cases you can find a system of ε-adjustments that lengthens every smallest-fragment. No luck yet, though!

(In fact, has proved over on LJ that my dissection for 5-into-7 is globally as well as locally optimal, which is more than I had previously known.)

I've written a thing that looks for integer solutions

Ooh, I'd like to see whatever data it's generated.

Also it can't handle irrationals and so far can do fractions only where all stick-fragments share a denominator

In any rational dissection there must be some denominator shared by all fragments (just take the lcm of all denominators), so the latter isn't a problem. And I'm still convinced that irrationals can't appear in any solution unless there's an equally good or better one without them (I have a half-thought-out proof idea involving treating R as a vector space over Q), so I'm not worried about the former either.

 Fri 2014-02-21 14:17

So far it is tediously slow and hasn't got anything harder than 5,7...

 Fri 2014-02-21 16:50

Apparently I'm not exactly doing this the optimal way... because 7 x 10 in 1/3 steps is, er, ENOMEMORY. Fantastic.

5 x 8 sticks in half integer steps is best with 4 sticks cut into 2/3 and 4 uncut assembled into 4 lots of 3/5 and 1 of 2/2/2/2 which gives more than 3 stick-parts.

With m and n <= 10 and m<n in half integer steps 12 combinations have a smallest-stick-fragment larger than gcd(m,n); 4 of which are non-integer (5 x7 is the smallest). I have no idea how to prove whether any given answer could be bested by taking smaller steps other than by trying progressively smaller steps and seeing.