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 09:51

A friend came over yesterday afternoon and we looked at this and made some progress. I can almost solve it, I think. In practice I can find the solution for given m and n with pen and paper and a small amount of fiddling, but at present this margin is too small to contain the details of the general method :-) But let's look at some examples. Let m

[Error: Irreparable invalid markup ('<n [...] it).>') in entry. Owner must fix manually. Raw contents below.]

A friend came over yesterday afternoon and we looked at this and made some progress. I can almost solve it, I think. In practice I can find the solution for given m and n with pen and paper and a small amount of fiddling, but at present this margin is too small to contain the details of the general method :-) But let's look at some examples. Let m<n and let s be the shortest length in the dissection, and t the longest length. We'll promise to never leave an m-stick whole in the dissection (this doesn't affect s, except in the trivial case where n is a multiple of m). With this constraint, t <= m-s.

Let's find s(3,10). If s is *more than*, um, 4/3, then t<5/3 if any 3-sticks are whole in the dissection, just cut them in half), so a 10-stick must be cut into at least 7 pieces (6 isn't quite enough - a tight constraint from t <5/3) and at most 7 (8 lots of 4/3 is too much) so exactly 7, so there are 21 pieces in the dissection. But each 3-stick must be cut in 2, so there are 20 pieces in the dissection, contradiction.

Note that 4/3 is the best number that gives this contradiction, since as I pointed out, the constraint was tight. So although it looked like I plucked it out of the air, I didn't really. Now all we need to do is find a 4/3-dissection, which is simplicity itself (try it).

Ok, let's find s(5,8). If s> ... let's say, 2, then t<3, so an 8-stick must be cut into at least 3 and at most 3 pieces (this time it's the maximum that's tight, from s>2, justifying my choice of the number 2), so there are 15 pieces in all. But the 5-sticks are all in 2 pieces, 16 in all, so s=2 is best, if we can find it. Again, it's easy.

Now let's find s(5,7) (your original example). if s>7/3, t<8/3 and each 7-stick must be in exactly two pieces by the argument above, and the constraint is tight. Can we find a 7/3-dissection? It's quite obvious that we can't after a moment's thought. Oh dear! Our method's gone wrong, so we use the fall-back of cutting m in 3 equal pieces. Can we find a 5/3-dissection? Yes we can, and then we use a slightly fiddlier proof to show that it's best.

Obviously there are a number of magic wands that need to be removed from this to make it a proof, but it seems to work in practice. The basic point is that the space of dissections is quite 'floppy', so if we can find a tight constraint with s>m/2 then there's a good chance we can also satisfy it, and if we can't, then the fall-back to cutting some m sticks into 3 equal parts means there's enough floppiness to do it now.

It wouldn't surprise me greatly if you found some cases where this doesn't work, but the first problem is to find out what it is actually claiming ...
Link Reply to this | Thread
[identity profile] writinghawk.livejournal.comWed 2014-03-12 10:29

Oh yes, and the other case is exemplified by s(5,6). If s=2, t=3 and each t-stick must be cut in 2 or 3 pieces. But both constraints are tight at the same time, so obviously it's not possible to do better.

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

Thanks for this! A couple of friends are currently working on an exhaustive search program to collect data on small cases (which I'll probably put up on the web at some point soonish, once I figure out how to format it most legibly) so it's nice to see someone else trying to approach it from the theoretical end and making progress.

In practice I can find the solution for given m and n with pen and paper and a small amount of fiddling, but at present this margin is too small to contain the details of the general method :-)

Looking at the data I have so far, here are some m,n pairs that might be interesting challenges to your method: s(5,4), s(3,7), s(7,8), s(4,9).

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

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.

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

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

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

... At least this weaker claim does hold true, since 4/3 is easily achievable, whether or not there is a better intermediate value available.

Link Reply to this | Parent
[identity profile] writinghawk.livejournal.comWed 2014-03-12 13:10

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.

Link Reply to this | Parent
[personal profile] simontWed 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.

Link Reply to this | Parent | Thread
[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 ]