I don't think so. Let's do s(4,5). If s>3/2, t<5/2 and each 5-stick must be in exactly 3 pieces (the constraint is tight on t). So there are exactly 12 pieces; but each 4-stick is in 2 pieces, so there are exactly 10 pieces, contradiction. 3/2 is achievable, so is the answer. Works like a dream.
Actually I spoke too soon. The method works fine for s(4,5) and also for s(3,7). However, for s(7,8) it gives a bound of s=8/3. This is certainly a bound, but it's not achievable: however, it's not necessary to drop down to 7/3, since the intermediate value of 5/2 is achievable (again, with a quite easy but fiddly proof).
So I must make a more modest claim: the method gives a reliable bound b, which is usually achievable. When it isn't achievable, m/3 may be the best achievable, but there may be some other intermediate value that will work.
As you can see, I've simply relaxed one of the two claims I made without any good reason. I'm still making one claim without proof (that m/3 is always achievable, because there is so much floppiness in the dissection).
For s(4,9) my method gives a bound of s<=9/5, which is another clearly not achievable case, so my new weakened claim is that 4/3 <= s < 9/5. As I haven't found the value yet this is an interesting test case ...
Incidentally, the cases where the proved bound is not achievable seem to be those where the candidate values of s and t are 'too close' to each other (e.g. 7/3 and 8/3 in the (5,7) case), or 9/5 and 11/5 in the (4,9) case), or 'too distant' (or perhaps 'too close to a multiple of each other') (e.g. 8/3 and 13/3 in the (7,8) case). But this is a rather woolly observation.
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.
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.
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!
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.
![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
simont's journal
I don't think so. Let's do s(4,5). If s>3/2, t<5/2 and each 5-stick must be in exactly 3 pieces (the constraint is tight on t). So there are exactly 12 pieces; but each 4-stick is in 2 pieces, so there are exactly 10 pieces, contradiction. 3/2 is achievable, so is the answer. Works like a dream.
Actually I spoke too soon. The method works fine for s(4,5) and also for s(3,7). However, for s(7,8) it gives a bound of s=8/3. This is certainly a bound, but it's not achievable: however, it's not necessary to drop down to 7/3, since the intermediate value of 5/2 is achievable (again, with a quite easy but fiddly proof).
So I must make a more modest claim: the method gives a reliable bound b, which is usually achievable. When it isn't achievable, m/3 may be the best achievable, but there may be some other intermediate value that will work.
As you can see, I've simply relaxed one of the two claims I made without any good reason. I'm still making one claim without proof (that m/3 is always achievable, because there is so much floppiness in the dissection).
For s(4,9) my method gives a bound of s<=9/5, which is another clearly not achievable case, so my new weakened claim is that 4/3 <= s < 9/5. As I haven't found the value yet this is an interesting test case ...
... At least this weaker claim does hold true, since 4/3 is easily achievable, whether or not there is a better intermediate value available.
Incidentally, the cases where the proved bound is not achievable seem to be those where the candidate values of s and t are 'too close' to each other (e.g. 7/3 and 8/3 in the (5,7) case), or 9/5 and 11/5 in the (4,9) case), or 'too distant' (or perhaps 'too close to a multiple of each other') (e.g. 8/3 and 13/3 in the (7,8) case). But this is a rather woolly observation.
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.
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.
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!
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.