Unsolved problem [entries|reading|network|archive]

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

Wed 2014-02-19 10:52
Unsolved problem
[personal profile] simontFri 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, [livejournal.com profile] writinghawk 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.

Link Reply to this | Parent | Thread
[personal profile] naathFri 2014-02-21 14:17

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

Link Reply to this | Parent
[personal profile] naathFri 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.

Link Reply to this | Parent | Thread
[personal profile] simontFri 2014-02-21 17:18

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.

Borrowing [livejournal.com profile] writinghawk's proof technique: in a better solution, each of the five 8-sticks would have to be cut into at most three pieces (if you cut one in four then a piece must be <=2), which gives 15 pieces overall, and so at least one of the eight 5-sticks must end up as a single piece (15 isn't enough pieces for two each). The 8-stick including that whole 5-stick then has 3 units of length left over; if you divide that in two then you have a piece <=1.5 (no good) and OTOH if you leave it whole then that leaves 2 units on the 5-stick you cut it off.

So this dissection for 5 into 8 cannot be beaten even if you were to increase the denominator, and hence [personal profile] gerald_duck's question is indeed answered.

(I do wonder how far that proof technique can be automated. It might give rise to a better search algorithm!)

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