simont | Unsolved problem

Crossposts: http://simont.livejournal.com/239857.html

Unsolved problem

Here's a mathematical sort of question that occurred to me last year. I've been pondering it off and on ever since, but not reached any useful conclusions; and I just came across my file of notes on it, and thought perhaps I should post it somewhere for other people to ponder as well.

Let m and n be positive integers. Suppose you have m sticks of length n, and you want to turn them into n sticks of length m, by cutting them into pieces and gluing the pieces back together. And the tricky bit is that you want to do this in a way that maximises the length of the shortest fragment involved in the dissection.

One obvious approach is to glue all your sticks end-to-end into one long stick of length mn, then cut that into n equal pieces. If you do that, the shortest fragment will have a length equal to gcd(m,n). So that's a lower bound on the solution in general, and in some cases (e.g. m=3, n=2) it really will be the best you can do.

But gcd(m,n) is not always the best you can do. For example, consider m=6 and n=5. The obvious gcd solution gives a shortest fragment of 1, but actually this case has a solution with shortest fragment 2: cut each of the six 5-sticks into pieces of length 2 and 3, then reassemble as three lots of 3+3 and two lots of 2+2+2. (In fact this was the case that first brought the problem to my attention.)

I also know that the best solution will not necessarily involve fragments of integer length. For example, consider m=5 and n=7. If you constrain yourself to only use integer-length fragments, then you can't make the shortest fragment any longer than 1. (If you try to make it 2, then you have no option but to cut up each 7-stick as 2+2+3, but then you have ten 2s and five 3s, out of which you can't make the seven 5s you need without bisecting a 2.) But with fractional fragment lengths you can improve on a shortest fragment of 1, by cutting up three 7-sticks as (8/3 + 8/3 + 5/3) and the other two as (7/3 + 7/3 + 7/3), then reassembling as six lots of (8/3 + 7/3) and one (5/3 + 5/3 + 5/3). So now your shortest fragment is one and two-thirds units long.

So, does anyone have thoughts? Other than the above examples, I haven't managed very many myself. I haven't even come up with a sensible computer search algorithm to reliably determine the best answer for a given m,n pair – so, in particular, I don't even know that 5/3 is the best answer for the example above, only that it's the best answer I know of. I have a vague idea that the best answer generally seems to involve at least one stick (on either the source or the destination side) being cut into equal-length fragments, but I wouldn't be at all surprised to find that wasn't true in all cases.

Flat | Top-Level Comments Only

Have you yet found an example where the (apparent) optimal solution requires dividing any stick into more than three pieces?

Is there any good reason not to consider wlog m<n? Beyond that, I'm too woozy at the moment, which is a pity as this problem is going to bug me without my getting much traction on it!

Have you yet found an example where the (apparent) optimal solution requires dividing any stick into more than three pieces?

No, but I haven't looked at any especially large examples, and that's where I'd most expect to see large dissections. I was rather hoping to find a sensible search algorithm and then run it on lots of pairs to collect data for a conjecture, but so far I haven't thought of a good criterion for the search algorithm figuring out when it can be sure all subsequent solutions it finds will be worse.

Is there any good reason not to consider wlog m<n?

None at all – the problem is certainly symmetric in m,n.

Is there an obvious limit on the size of the denominator in the best solution for a particular pair? Then at least you could brute force small cases to ensure you have the best answer.

Indeed, but I haven't yet found such a limit, or even a proof of rationality!

As I was saying to someone in another forum:

One would like to think that there's some nice proof involving local perturbations – pick the smallest fragment size and adjust it by ε, then adjust some other fragment of the same stick by −ε to make up for it, which means in turn that a fragment of the appropriate stick at the other end of the dissection goes by +ε, and ... you hope to end up with a closed loop of adjustments, or several such loops superimposed, and hence an adjustment to your original dissection which is legal for some sufficiently small ε > 0 and increases the length of every currently minimal fragment. If you can do that, then the dissection you started with was not a local optimum, and hence not a global optimum either.

The point of doing this would be that it gives you a reason why the smallest fragment keeps turning out to be achieved by cutting a single stick into equal pieces – because then clearly no such perturbation can increase the length of all those pieces at once, or else the result wouldn't fit in that stick any more.

But I don't actually have a proof along those lines, only a sketch of the sort of thing I'd like the proof to achieve. And even that wouldn't prove that an optimum dissection had to have all fragments rational, only that the smallest fragment had to be rational.

In fact I'd guess it's quite likely that optimal dissections need not have the longer fragments all rational (there's probably some situation in which you can find a closed loop of those local perturbations that never touch a minimal fragment, in which case you can apply that change with irrational ε to get a partially irrational and equally good answer), but I'd at least hope that there exists a rational optimal dissection in every case...

there's probably some situation in which you can find a closed loop of those local perturbations that never touch a minimal fragment, in which case you can apply that change with irrational ε to get a partially irrational and equally good answer

In fact, yes, the 7/5 example in my original post admits just such a transformation. Where we previously dissected three 7-sticks as (8/3 + 8/3 + 5/3) and the other two as (7/3 + 7/3 + 7/3), we now do:

two lots of (8/3+ε) + (8/3−ε) + (5/3)
one unmodified (8/3) + (8/3) + (5/3)
two lots of (7/3+ε) + (7/3−ε) + (7/3)

which reassembles as:

two lots of (8/3+ε) + (7/3−ε)
two lots of (8/3−ε) + (7/3+ε)
two lots of (8/3 + 7/3)
one lot of (5/3) + (5/3) + (5/3) as before.

And then you can set ε = π/1000 or some such and you have some irrational pieces – but not interestingly irrational.

At a guess, you can probably rule this out by introducing a tie-breaking rule, in which solutions with the same shortest fragment length are now compared by their second shortest, and so on. That'd probably put a stop to frivolous irrationality :-)

Because you have to match up the + and - irrationals I don't think you get a longer smallest stick doing this; although obviously you can have the same-length smallest stick.

I've written a thing that looks for integer solutions; but it's slow and crap and obviously "I searched exhaustively and found this" is much less interesting than "I thought really hard about it and realised that all solutions look like this". Also it can't handle irrationals and so far can do fractions only where all stick-fragments share a denominator....

Indeed, you certainly can't get a longer smallest stick by small perturbations of that answer, because one of the 5-sticks is entirely made up of smallest-fragments and so if you lengthen them all by any ε > 0 then that stick overflows. What I was hoping to show was that the converse is also true – that the only way in which a dissection can be locally optimal is if some stick is made up entirely of smallest-fragments, by showing that in all other cases you can find a system of ε-adjustments that lengthens every smallest-fragment. No luck yet, though!

(In fact,

writinghawk has proved over on LJ that my dissection for 5-into-7 is globally as well as locally optimal, which is more than I had previously known.)

I've written a thing that looks for integer solutions

Ooh, I'd like to see whatever data it's generated.

Also it can't handle irrationals and so far can do fractions only where all stick-fragments share a denominator

In any rational dissection there must be some denominator shared by all fragments (just take the lcm of all denominators), so the latter isn't a problem. And I'm still convinced that irrationals can't appear in any solution unless there's an equally good or better one without them (I have a half-thought-out proof idea involving treating R as a vector space over Q), so I'm not worried about the former either.

So far it is tediously slow and hasn't got anything harder than 5,7...

Apparently I'm not exactly doing this the optimal way... because 7 x 10 in 1/3 steps is, er, ENOMEMORY. Fantastic.

5 x 8 sticks in half integer steps is best with 4 sticks cut into 2/3 and 4 uncut assembled into 4 lots of 3/5 and 1 of 2/2/2/2 which gives more than 3 stick-parts.

With m and n <= 10 and m<n in half integer steps 12 combinations have a smallest-stick-fragment larger than gcd(m,n); 4 of which are non-integer (5 x7 is the smallest). I have no idea how to prove whether any given answer could be bested by taking smaller steps other than by trying progressively smaller steps and seeing.

5 x 8 sticks in half integer steps is best with 4 sticks cut into 2/3 and 4 uncut assembled into 4 lots of 3/5 and 1 of 2/2/2/2 which gives more than 3 stick-parts.

Borrowing

writinghawk's proof technique: in a better solution, each of the five 8-sticks would have to be cut into at most three pieces (if you cut one in four then a piece must be <=2), which gives 15 pieces overall, and so at least one of the eight 5-sticks must end up as a single piece (15 isn't enough pieces for two each). The 8-stick including that whole 5-stick then has 3 units of length left over; if you divide that in two then you have a piece <=1.5 (no good) and OTOH if you leave it whole then that leaves 2 units on the 5-stick you cut it off.

So this dissection for 5 into 8 cannot be beaten even if you were to increase the denominator, and hence

gerald_duck's question is indeed answered.

(I do wonder how far that proof technique can be automated. It might give rise to a better search algorithm!)

Hm. My guess would have been that the best dissection is rational, but isn't always equal sized. But I've not tried it at all, just read what you wrote here.

Aha, now I think I've got a proof of rationality. Suppose we have some dissection containing an irrational fragment. We will show it isn't optimal (under my extended criterion that if two dissections' shortest fragment lengths are equal then you tie-break by looking at the second shortest distinct length and so on).

Choose a basis B for R as a vector space over Q, and choose it so that it includes an actual rational q. Write every fragment length in the dissection as its unique weighted sum of elements of B. Rational lengths will therefore be represented as straightforward multiples of q.

The shortest irrational fragment length, being irrational, must have a nonzero coefficient for at least one element of B that isn't q; let b be such an element. Look at the coefficients of b across all fragments of the dissection. They must sum to zero in every input and output stick (because those sticks' lengths are all rational, hence have zero coefficient of everything other than q). So if we pick any real ε and adjust every fragment length by ε times its coefficient of b, we must get a system of adjustments that preserves every input and output stick length, and which always adjusts equally long sticks by the same amount. So in particular we can choose ε so that it has the correct sign to slightly increase the shortest irrational length (and has absolute value small enough not to make any two lengths cross over each other), and then applying those adjustments yields a strictly better solution.

Hence, no dissection with any irrational fragment can be optimal (under the extended criterion including tie-breaking), and in particular no dissection with an irrational shortest fragment can be optimal even under the original criterion. []

(Slightly icky because it uses the Axiom of Choice, almost certainly unnecessarily. But AC is obviously true, right? So no problem really. :-)

Edited (state clearly both results that are proved by this) 2014-02-21 15:35 (UTC)

I now actually read this proof, and it sounds right to me, though I don't guarantee I haven't missed some exception.

What confused me in the pub is, you use the axiom of choice to get a basis for R over Q. But don't you just need a basis over Q for the vector space generated by the fragment lengths you actually have, not over any possible irrationals? Isn't that just some subset of the fragment lengths, throwing away any non-linearly-independent ones?

Ah! Yes, good thought. And that vector space is finite-dimensional, because we have at most finitely many frag lengths, and hence we don't need AC to conclude that it has a basis. Well done.

Ian has written a fairly shiny search program which confirms your guess that the best dissection is not always equal-sized. 7 into 4 has minimum fragment 5/3, which is not an integer fraction of either stick length. So much for my conjecture.

(I leave the exact dissection of 7 into 4 as an exercise, but it shouldn't be hard given the minimum length :-)

Ah! Very cool. I'm glad someone wrote a search program :)

I'm flattered you call my comment a conjecture, when it was only really saying I wasn't convinced by your conjecture. But I'm glad we found an answer deciding it :)

Stupid question, if the search program finds a best answer, how does it show that's the best? Is there an obvious limit on something? Previously we seemed to have no way of clearly showing an answer _is_ the best, except by special-case proofs like writing-hawk's.

Stupid question, if the search program finds a best answer, how does it show that's the best?

Not a stupid question at all, since nobody else had thought of an answer to that problem!

Ian's basic idea is to start by (WLOG) assuming each input stick contributes at most one piece to each output stick (clearly if that's not true then you can merge fragments until it is without making your score worse). So now you have an n × m matrix of fragment lengths. Next, we want to treat the problem as a linear-programming optimisation exercise, trying to maximise one variable ("smallest nonzero matrix entry") under a collection of linear constraints (matrix entries all positive, rows and columns sum to the right thing). The trouble with that is that it's not actually a linear problem, since the objective criterion is nonlinear (taking min of all the matrix entries isn't a linear function). But if you knew the adjacency matrix (that is, you knew which input sticks contribute at all to which output sticks) it would be, because you could introduce the minimum frag length itself as an extra variable, so that some matrix elements were constrained to zero and others were of the form (min_frag + some positive extra value). So Ian simply iterates over all possible adjacency matrices and appeals to a linear-programming library to solve that optimisation problem for each one, and once he's gone through all possible matrices then he knows he's considered every answer!

Of course, then you optimise as hard as you can (by e.g. iterating over adjacency matrices in a sensible order that means you see the best ones first, stopping as soon as your matrix gets too dense because then some stick has to be cut into enough pieces that the smallest won't beat your existing best answer, parallelising over all the CPUs you can find, etc). But that's the basic idea.

Ah! Thank you. I couldn't see how the program would find it, I assumed it was obvious in some other way, but that approach makes sense even if it's brute force. It's considerable progress to be able to find optimal solutions at all.

Has any pattern emerged in the results found?

I wonder if it's possible to make any theoretical progress following the same approach? (But I'm just speculating I haven't even had time to start thinking about it yet.)

We're still working on getting the searcher to be both fast and accurate :-/ (I know it's missing at least one optimal solution in its current state.) When I have a large amount of data I more or less trust, I'll post it somewhere.

I know it's missing at least one optimal solution in its current state.

Oops! I hope it comes into shape.

Hold on a second. Did you mean that the best dissection involved the shortest fragment being coming from an equal size division of some stick? Or that the best dissection involved SOME stick being equally divided? Because I wasn't sure there was an obvious reason for the first, but the second could still be true (if I've got the right solution for 4<->7)?

Or rather, what happens if you try to increase all the shortest lengths by epsilon? That obviously fails if several of them compose a single stick. That's what you were trying to explain to me before. But if you follow through adjusting all other stick lengths epsilon as you described, it has to fail *somewhere* or you didn't start with a local optimum. Another way it could fail is if the *complements* of the shortest fragments are equal divisions of a stick. But there may be other ways as well, if you end up with a stick made of fragments that all have to get longer or all have to get shorter, but came from a different number of steps from the original perturbation.

But if the optimal solution for some division is 5/3, I can't help but wonder if that means *something* has to be divided into three equal pieces.

I wonder if this might be easier to imagine looking at perturbing a matrix as you described, instead of sticks.

A more specific conjecture would be that any optimal dissection (in your extended criterion of tie-breaking) of a set of n m-sized sticks and a set of m n-sized sticks into two identical piles of fragments can be performed by a sequence of "Divide (the remainder of) some stick from one set into N (N>=1) equal sized fragments, and removing the corresponding fragments from sticks in the other set. Then repeat, dividing one of the new remainders, until nothing is left."

I don't think that's worded quite right, but I think something like that. If so, maybe a perturbations argument could show that if at some step you divide into the same number of fragments of slightly different lengths, you can follow through the remainder of the steps in the same way. And if so, the non-equal division would be sub-optimal (because one stick of that length gets shorter).

But I'm not sure if that's actually right, or just another plausible guess that will turn out to have exceptions.

This seems like just the sort of conjecture that we could actually check against the piles of data from the search program! (Which may now be working [crosses fingers], so some data might actually be forthcoming once I've sorted out a way to present it legibly.)

What a nice and curious problem. It's rather startling at first that the answers needn't be integers.

I don't even know that 5/3 is the best answer for the example above,

It seems most implausible that it isn't. Hmm, yes, let's see: in a better solution, each 5 stick must be cut into at most 2 pieces, obviously. The resulting (wlog) 14 pieces must be assembled into five 7-sticks so one 7-stick must get at most two pieces. One of these must be at least 3.5 long. Whichever 5-stick that came from, you had a length of 1.5 left over, which is too short.

Edited 2014-02-21 08:50 (UTC)

Yes, the non-integer answer was startling to me too, and is really what made the problem stick in my head rather than falling out again shortly after it occurred to me.

The resulting (wlog) 14 pieces must be assembled into five 7-sticks so one 7-stick must get at most two pieces. One of these must be at least 3.5 long.

Oh yes, that's a nice approach to proving optimality. Thank you!

Just to point out - the 'wlog 14' is because if any 5-sticks are left whole by the dissection, we can chop them in half to get 14 pieces. I didn't make this very explicit but we need it for the final step, where the two-piece 7-stick must not be 5+2.

[Error: Irreparable invalid markup ('<n [...] length.>') 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 ...

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.

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

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.

Edited 2014-03-12 14:20 (UTC)

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.

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?

Edited 2014-03-12 21:06 (UTC)

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

writinghawk, or under some other name?

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 writinghawk

I should be honoured!

Edited 2014-03-14 18:35 (UTC)

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.

Edited 2014-03-14 21:01 (UTC)

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.

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.

Edited 2014-03-14 21:58 (UTC)

Flat | Top-Level Comments Only

Unsolved problem

no subject

no subject

no subject

no subject

no subject

no subject

no subject

no subject

no subject

no subject

no subject

no subject

no subject

no subject

no subject

no subject

no subject

no subject

no subject

no subject

no subject

no subject

no subject

no subject

no subject

no subject

no subject

no subject

no subject

no subject

no subject

no subject

no subject

no subject

no subject

no subject

no subject

no subject

no subject

no subject

no subject

no subject

no subject