Unsolved problem
simont

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

 Wed 2014-02-19 10:52
Unsolved problem
 Fri 2014-03-14 18:30

This seems to disagree with my version of your bound above in some cases. The smallest is s(5,7). The true optimum is 5/3

Ah yes, I lost sight of the possibility that the expression I was seeking would sometimes be lower than m/3 (whereas the actual bound from this approach can't be). I meant

s' = max [ m/3, min [ m-n/p, n/(p+1) ]]

but I'm less and less confident that I was right, so if you have cases where this expression is still different from the bound you've calculated, let me know and I'll have another go :-) It would be very nice to get an explicit expression for the bound, whatever it is.

would you like me to credit you as

I should be honoured!

 Fri 2014-03-14 20:36

Hmm, I've looked at this more and deleted a comment saying I thought I nearly knew what was going on. It looks as if my attempt to find an explicit expression - or at least a remotely simple one - was doomed, so I should just be happy that you can calculate the bound somehow or other.

On the other hand, 'you can calculate it somehow or other' actually makes it rather less useful, since you can also calculate the exact value of s!

To be clear, I was only trying to find the optimum value of s' such that for any greater s', the number of pieces that n-sticks are divided into would be constrained to an exact number, Q say, giving exactly Qm pieces in the dissection. Provided that this s'>m/3, the m-sticks are simultaneously constrained to be in 2 pieces, giving 2n pieces. Since by hypothesis m doesn't divide 2n, these two constraints are incompatible (Qm =/= 2n).

So actually, you were flattering me by saying my bound for s(5,7) would be 5/3. It would actually be 7/4. (Not 7/3, as I wrongly claimed above.) If s>7/4, then t<13/4 and the 7-sticks are constrained to be in exactly 3 pieces (P=15), whereas for a lower s, 4 pieces are possible (15<=P<=20). As you rightly noticed, in this particular example, in either case the fact that the 5-sticks are constrained to be in 2 pieces gives P=14 which is a contradiction, but I wasn't so optimistic as to expect to be able to get an exact expression for the bound which took account of that.

What I *can* prove is that the *max* of the two numbers I gave is a bound, i.e.

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

But this bound is almost always too strong. In fact, just considering the n-sticks alone you find there is no possible dissection, except in the special case where the two terms in the max are equal (for example for s(5,6), where they are both 2). Except in that special case therefore, this is higher than the bound I was looking for. At least it's something, though.

I still feel in my bones that there should be a reasonably accessible expression for the bound I'm after, if not for the (better) one which you have actually calculated, but it's more messy than I had hoped.

 Fri 2014-03-14 21:23

But this bound is almost always too strong. In fact, just considering the n-sticks alone you find there is no possible dissection, except ...

To further clarify, the bound thus obtained is only *just* too strong - you get a pair of constraints Q<=p and Q>p. So the next boundary-point down is the one you want. I wrongly hoped that this would be the other element in the min(), but as the s(5,7) case shows this isn't remotely true.