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

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

Wed 2014-02-19 10:52
Unsolved problem
LinkReply
[personal profile] simontWed 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 :-)
Link Reply to this | Parent | Thread
[personal profile] naathFri 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....

Link Reply to this | Parent | Thread
[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
navigation
[ go | Previous Entry | Next Entry ]
[ add | to Memories ]