Unsolved problem
simont

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

 Wed 2014-02-19 10:52
Unsolved problem
 Wed 2014-03-12 14:14

For s(4,9) my method gives a bound of s<=9/5

Hmm, does it? I tried to boil down your method into something I could state in a general way, and then applied that, and for s(4,9) I got what I think is actually the right bound.

If every piece is at least s and at most m-s, then every stick of length n is cut into at least n/(m-s) and at most n/s pieces, hence at least ⌈n/(m-s)⌉ and at most ⌊n/s⌋, hence the total number of pieces P in the dissection must satisfy m⌈n/(m-s)⌉ ≤ P ≤ m⌊n/s⌋. By similarly considering the number of pieces that a stick of length m is cut into, we derive a second inequality n⌈m/(m-s)⌉ ≤ P ≤ n⌊m/s⌋ (identical to the first except that n,m are swapped everywhere they appear except in the divisor m-s). So when s becomes big enough that either of those inequalities is self-inconsistent (with LHS > RHS) or when the two are incompatible (because they define ranges for P that do not meet), there can be no dissection with s that large.

It is true that s=9/5 is a threshold beyond which something goes wrong, namely that the first inequality for P is self-inconsistent (with s > 9/5 we would need 20 ≤ P ≤ 16). But something else has gone wrong before that – at s=7/4 the two intervals stop overlapping (because the first inequality switches from 16 ≤ P ≤ 20 to 20 ≤ P ≤ 20, while the second was at 18 ≤ P ≤ 18 all along). And the computer search data I have says that 7/4 really is the best solution.

I agree with you, on the other hand, that the method doesn't get the exact bound for s(7,8), and hence is not reliable in all circumstances.

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

 Wed 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!

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