(Reply) [entries|reading|network|archive]
simont

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

[identity profile] writinghawk.livejournal.com Wed 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 [...] dissection.>') 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 Read Comments
Reply:
From:
Anonymous( )Anonymous This account has disabled anonymous posting.
OpenID( )OpenID You can comment on this post while signed in with an account from many other sites, once you have confirmed your email address. Sign in using OpenID.
User
Account name:
Password:
If you don't have an account you can create one now.
Subject:
HTML doesn't work in the subject.

Message:

 
Notice: This account is set to log the IP addresses of everyone who comments.
Links will be displayed as unclickable URLs to help prevent spam.