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

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

Wed 2014-02-19 10:52
Unsolved problem
LinkReply
[identity profile] writinghawk.livejournal.comWed 2014-03-12 15:00

You're right, the bound is 7/4 and hence gives the correct answer in that case.

Your account is more complicated than need be because the bound always operates when the m-sticks are constrained to be divided into only two pieces, making the first constraint P=2n. So the n-sticks are presumably going to be divided into about 2n/m pieces, give or take some rounding somewhere. Ignoring the trivial case where m | 2n, set p = floor(2n/m) and by considering the four possible cases we get a bound of

max [ min (n/p, m-n/p), min (n/(p+1), m-n/(p+1)) ]

In the s(4,9) case, p=4 and this gives

max [ min (9/4, 7/4), min (9/5, 11/5) ] = max (7/4,9/5) = 7/4.

(I didn't do this explicit calculation earlier as my brain was full and I hoped to get some work done today, but I have overcome both weaknesses :-)

As we've said, this bound isn't always tight but it seems it very often is. I'd be interested in whether your data has any cases refuting my conjecture that, when the bound isn't tight, s is still >= m/3. Also of course to see if one can characterise the cases where the bound is not tight.

Link Reply to this | Parent | Thread
[identity profile] writinghawk.livejournal.comWed 2014-03-12 15:50

Grr, that's still completely wrong, though the right elements are there. Unfortunately I've gone back to trying to get some work done, but some anagram of the above is true which I will identify when I have some more time!

Link Reply to this | Parent
[personal profile] simontWed 2014-03-12 16:07

I'd be interested in whether your data has any cases refuting my conjecture that, when the bound isn't tight, s is still >= m/3

No.

I've implemented a piece of Python that computes your bound (that is, computes my statement of it, without attempting to simplify based on this followup) and compared it with all the data I have so far (which is everything up to n=10, and some but not all for n=11).

The complete list of cases I know of in which your bound is not tight (assuming I haven't made any errors in my implementation) is: s(6,7), s(7,8), s(9,10), s(3,11), s(4,11), s(5,11), s(7,11). And in all those cases, we do still have s ≥ m/3.

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