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 20:36

Ok, sorry about earlier brainstorm. When I saw your 7/4 and saw that that was one of the numbers in my calculation, I was hypnotised briefly by my earlier mistake into thinking 7/4 > 9/5.

As usual when one has been staring at something too long, the truth is perfectly simple - I was over-complicating things with that max(). The two min()'s give two constraints, one of which will be too strong (overconstrained), so I should take the lower of them - simply, the min of the 4 quantities. And two of them can be ruled out: n/(p+1) < n/p, and similarly m-n/p < m-n/(p+1), so the latter quantity in each inequality can be discarded.

I.e. if m and n are coprime, m>2, and

p = floor (2n/m)

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

Then s' is the bound: s(m,n) <= s' and very often s=s'.

If m=1, s=1. If m=2 and n is odd, s=1. If m = dm', n=dn' for some integer d>1 then s(m,n) = d s(m',n').

Does this agree with what you calculated?

Link Reply to this | Thread
[personal profile] simontFri 2014-03-14 14:56

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; my version of your bound also gives 5/3 (that's the point at which my second range for P switches from [14,21] to [14,14] while the first was at [15,20] and hence they stop overlapping). But the version in your comment here, as I calculate it, gives us p=2 and s' = min { 5-7/2, 7/3 } = min { 3/2, 7/3 } = 3/2, which isn't even a correct upper bound at all.

Incidentally, I'm starting to think about putting up a web page containing all the data I have so far, and trying to tabulate it so as to show at a glance where answers are known, where bounds are tight, and what's still uncertain. Your bounding technique will form an important part of that table, and you obviously deserve credit for coming up with it; would you like me to credit you as [livejournal.com profile] writinghawk, or under some other name?

Link Reply to this | Parent | Thread
[identity profile] writinghawk.livejournal.comFri 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 [livejournal.com profile] writinghawk

I should be honoured!

Link Reply to this | Parent | Thread
[identity profile] writinghawk.livejournal.comFri 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.

Link Reply to this | Parent | Thread
[identity profile] writinghawk.livejournal.comFri 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.

Link Reply to this | Parent
[identity profile] writinghawk.livejournal.comFri 2014-03-14 21:37

Provided that this s'>m/3,

Or rather, "since this s'>m/3", as it always is. If s'<=m/3, t>=2m/3, i.e. the longest length is at least twice the shortest length and there can't be a simple counting argument that means you can't fill up an n-stick. You just fill it up with copies of t until you get stuck; then you remove your last copy of t and fill up the remaining gap with two equal sized sticks, which are obviously shorter than t and longer than s.

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