<html>
+<meta http-equiv="Content-type" content="text/html; charset=UTF-8">
<head>
-<title>Known bounds for stick-dissecting problem</title>
+<title>Minimax matchstick dissection</title>
<style type="text/css">
table, td, th {
border: 1px solid black;
border-collapse: collapse;
}
-td.known {
+.box {
+ border: 1px solid black;
+ padding-left: 0.3em;
+ padding-right: 0.3em;
+}
+.known {
background-color: #00ff00;
}
-td.believed {
+.believed {
background-color: #aaff00;
}
-td.probable {
+.probable {
background-color: #ffff00;
}
-td.range {
+.range {
background-color: #ff8888;
}
+sub {
+ vertical-align: -0.3em;
+ font-size: 70%;
+ line-height: 0;
+}
</style>
</head>
<body>
+
+<h1>Minimax matchstick dissection</h1>
+
+<p>
+This web page documents my current state of knowledge about a
+combinatorial problem that occurred to me in the summer of 2013 and
+intrigued me by having no obviously simple answer. Several people have
+been kind enough to help me gather data and thoughts on the problem,
+so I'm putting up a web page collating all of that.
+</p>
+
+<p>
+I have so far not heard of any previous work on the problem,
+although there is a strong possibility that such work exists and I
+just haven't heard about it. Please send details, if you have any!
+</p>
+
+<h2>The problem</h2>
+
+<p>
+The problem is a one-dimensional dissection. Let <i>m</i> and <i>n</i>
+be positive integers. Suppose we have <i>m</i> matchsticks, each of
+length <i>n</i>. We want to turn them into <i>n</i> sticks of
+length <i>m</i>, by cutting them into shorter fragments and then
+gluing the fragments back together.
+</p>
+
+<p>
+The catch is that we don't like short fragments, and we like them less
+the shorter they are. So we want all the fragments to be nice and
+large. Specifically, we want to find a dissection whose <em>shortest
+fragment length</em> is as long as we can make it.
+</p>
+
+<p>
+Obviously, one possible dissection is to cut up every stick
+into <i>n</i> pieces of length 1, and then stick them all back
+together in groups of <i>m</i>, giving a shortest fragment of 1.
+If <i>m</i> and <i>n</i> have a common factor, we can improve on this
+by cutting them into larger pieces, still all the same size. In
+general, this gives us a minimum fragment of gcd(<i>m</i>,<i>n</i>).
+(Another way to achieve this same result would be to glue all the
+sticks into one long stick and then cut that into <i>n</i> equal
+pieces. That dissection uses fewer fragments, but the shortest
+fragment length is still gcd(<i>m</i>,<i>n</i>), and we don't care
+about the details of the dissection other than that.)
+</p>
+
+<p>
+In many cases, however, you can do better than that. The case that
+first brought this problem to my attention was the one with <i>n</i>=6
+and <i>m</i>=5. The trivial gcd solution gives you a minimum fragment
+of 1, but in fact we can dissect 6 sticks into 5 sticks with minimum
+fragment 2, by cutting up every length-5 stick as (2 + 3)
+and then reassembling as two lots of (2 + 2 + 2)
+and three lots of (3 + 3).
+</p>
+
+<p>
+More interestingly still, the minimum fragment need not always even be
+an <em>integer</em>. (That was the aspect that surprised me enough to
+make the question really stick in my mind.) For example,
+consider <i>n</i>=5 and <i>m</i>=4: obviously if you use integer-sized
+fragments then you can't make the biggest fragment any larger than 1
+(each length-5 stick would need a fragment of odd length, and you
+can't cut an odd piece from a length-4 stick without generating a
+piece of length 1). However, if you don't insist on integer fragments,
+the dissection of 5 into 4 can be done with shortest fragment 3/2: cut
+four of the length-4 sticks slightly unevenly into 3/2 + 5/2
+and the last one evenly into 2 + 2, then make two length-5
+sticks as 5/2 + 5/2 and the other two as
+3/2 + 3/2 + 2.
+</p>
+
+<h2>Theory</h2>
+
+<p>
+To begin with, we'll establish the convention
+that <i>m</i> < <i>n</i>. (The problem is obviously
+symmetric in interchange of the two variables, and the
+case <i>m</i> = <i>n</i> requiring no cuts at all is so
+uninteresting that we may as well ignore it.)
+</p>
+
+<h3>No irrationals</h3>
+
+<p>
+We've established that the minimum fragment size need not be an
+integer, so an obvious next question is, need it even
+be <em>rational</em>?
+</p>
+
+<p>
+The answer is yes, and we can prove it as follows. Consider an
+arbitrary dissection of <i>m</i> sticks into <i>n</i> containing at
+least one irrational fragment length. The lengths of all the fragments
+generate a finite-dimensional vector space over ℚ; let
+{ <i>e</i><sub>1</sub>, …, <i>e</i><sub><i>k</i></sub> }
+be a basis for that space in which <i>e</i><sub>1</sub> is rational.
+Then the shortest irrational fragment length must have a nonzero
+coefficient of some basis element other than <i>e</i><sub>1</sub>,
+say <i>e</i><sub><i>i</i></sub>.
+</p>
+
+<p>
+Now we construct a new dissection based on the old one, in which we
+adjust every fragment length by adding <i>ε</i> times its original
+value's coefficient of <i>e</i><sub><i>i</i></sub>, for some
+constant <i>ε</i>. Doing this must preserve the property that the
+fragments making up each input and output stick sum to the right total
+length (proof: the original <i>e</i><sub><i>i</i></sub> coefficients
+must have summed to zero in order to generate an integer stick length
+previously, so adding a constant multiple of all
+those <i>e</i><sub><i>i</i></sub> coefficients doesn't change the
+overall sum). So now we choose |<i>ε</i>| small enough that no two
+original fragment lengths change their ordering and no fragment length
+becomes negative or more than the entire stick size. (We can do this,
+since those constraints give us finitely many upper bounds all of
+which are strictly positive, so we can certainly find an <i>ε</i>
+smaller than all of them and still nonzero. The only interesting case
+is when a fragment was the whole of its stick – in which case it has a
+zero coefficient of <i>e</i><sub><i>i</i></sub> anyway, so we aren't
+changing it at all and no bound is placed on <i>ε</i> by the
+requirement for it not to overflow.) Finally, we choose the sign
+of <i>ε</i> so that it lengthens rather than shortening the smallest
+irrational fragment.
+</p>
+
+<p>
+So now we've constructed a new dissection of basically the same shape
+as the old one, in which every fragment length is adjusted by at most
+a small amount, with the properties that:
+<ul>
+<li>
+ordering of lengths is preserved (if one fragment was shorter than
+another in the old dissection then it is in the new dissection too)
+<li>
+in particular, equal fragment lengths remain equal (because they had
+the same <i>e</i><sub><i>i</i></sub> coefficient so we adjusted them
+by the same amount)
+<li>
+rational fragment lengths are unchanged from the original dissection
+(they had a zero <i>e</i><sub><i>i</i></sub> coefficient)
+<li>
+what was previously the shortest irrational fragment length is now
+slightly longer.
+</ul>
+This means that no dissection with the shortest fragment irrational
+can be optimal, since the above construction would improve it.
+</p>
+
+<p>
+Also, if we were to strengthen our optimisation criterion by imposing
+a tie-breaking condition in which dissections with the same shortest
+fragment were compared by looking at the <em>next</em> shortest
+fragment and so on, then any dissection optimal under that stronger
+condition would have to have <em>every</em> fragment length rational
+(because, again, we could always lengthen the shortest irrational one,
+without changing any of the rational fragment lengths shorter than
+it). This implies that not only must the minimum fragment size always
+be rational, but also there must always be an all-rational dissection
+which attains it. So we can rule irrationals completely out of
+consideration, which is a relief!
+</p>
+
+<h3>Upper bounds</h3>
+
+<p>
+A problem with searching for dissections is, once you've found one,
+how do you prove there isn't a completely different one that does
+better?
+</p>
+
+<p>
+One way to solve that problem is to find a genuinely exhaustive search
+strategy, one of which is described in the next section. But
+exhaustive searches are expensive, so it would be nice to have some
+other tools in our toolbox as well, such as strategies for proving
+that no solution for a given <i>n</i>,<i>m</i> can be better than a
+given value. Then, if you can find an upper bound proof <em>and</em> a
+dissection attaining that bound, you know you don't have to look any
+further.
+</p>
+
+<p>
+One such upper bound proof, largely due
+to <a href="http://writinghawk.livejournal.com/profile">writinghawk</a>,
+works by counting the pieces in the dissection. For this proof, we
+start by assuming that every length-<i>m</i> stick (i.e. every shorter
+stick) is cut into at least two pieces; this doesn't lose generality,
+because if any stick remains whole in a dissection, we can just cut it
+in half and put both the pieces into the same <i>n</i>-stick. (And
+this does not decrease the minimum fragment length
+unless <em>all</em> <i>m</i>-sticks were whole, i.e. <i>m</i>
+divides <i>n</i>, which is a special case with such an obvious answer
+that we don't need this proof anyway.)
+</p>
+
+<p>
+So, let's suppose that every piece is at least length <i>s</i>. Also,
+every piece must be at <em>most</em>
+length <i>m</i> − <i>s</i> (because it must have been part
+of some <i>m</i>-stick, which had a piece of at least <i>s</i> cut off
+it).
+</p>
+
+<p>
+That means that each stick of length <i>n</i> has to be cut into at
+least <i>n</i>/(<i>m</i>−<i>s</i>) and at most <i>n</i>/<i>s</i>
+pieces (otherwise some piece would have to be too long or too short).
+Because the number of pieces also has to be an integer, that really
+means it's at least ⌈<i>n</i>/(<i>m</i>−<i>s</i>)⌉ and at most
+⌊<i>n</i>/<i>s</i>⌋. Summing those expressions over
+all <i>n</i>-sticks tells us that the total number of pieces <i>P</i>
+in the whole dissection must satisfy the
+inequality <i>m</i>⌈<i>n</i>/(<i>m</i>−<i>s</i>)⌉ ≤ <i>P</i> ≤ <i>m</i>⌊<i>n</i>/<i>s</i>⌋.
+</p>
+
+<p>
+By similarly considering the number of pieces that a stick of
+length <i>m</i> is cut into, we derive a second
+inequality <i>n</i>⌈<i>m</i>/(<i>m</i>−<i>s</i>)⌉ ≤ <i>P</i> ≤ <i>n</i>⌊<i>m</i>/<i>s</i>⌋.
+(This is identical to the first inequality, but with <i>n</i>
+and <i>m</i> swapped everywhere they appear except in the
+divisor <i>m</i>−<i>s</i>).
+</p>
+
+<p>
+So when <i>s</i> becomes big enough that either of those inequalities
+is self-inconsistent (with its LHS strictly larger than its RHS), or
+when the two are incompatible (because they define ranges for <i>P</i>
+that do not meet), there can be no dissection with <i>s</i> that
+large. This allows us to establish an upper bound on <i>s</i> for a
+given instance of the problem, which is often (but, results below
+indicate, not always) actually achievable.
+</p>
+
+<p>
+A second upper-bound proof, due to Tom Womack, applies in a restricted
+set of cases, some of which are not solved optimally by the above
+proof. Specifically: if <i>m</i>/3 is an integer and is also a
+multiple of <i>n</i>−<i>m</i>, then no solution can be better
+than <i>m</i>/3.
+</p>
+
+<p>
+Proof: suppose the shortest fragment is <i>m</i>/3 + <i>ε</i> for
+some <i>ε</i> > 0. Then if any segment of stick less
+than <em>twice</em> that length arises while you're dissecting, it
+must remain whole. In particular, any fragment shorter than
+2<i>m</i>/3 + 2<i>ε</i> must be monolithic in this way.
+</p>
+
+<p>
+So consider a stick of length m from which we cut a piece of
+length <i>m</i>/3+<i>ε</i>. The other piece of that stick has length 2<i>m</i>/3−<i>ε</i> and
+hence is monolithic; so it must have been cut as a whole from a longer
+stick of length <i>n</i>. Let <i>n</i> = <i>m</i>+<i>k</i>, because we'll want to talk about <i>k</i> a
+lot. Now we reason as follows:
+<ul>
+<li>
+a piece <i>m</i>/3+<i>ε</i> shares a short stick with
+2<i>m</i>/3−<i>ε</i>
+<li>
+that 2<i>m</i>/3−<i>ε</i> shares a long stick
+with <i>m</i>/3+<i>k</i>+<i>ε</i>
+<li>
+that <i>m</i>/3+<i>k</i>+<i>ε</i> shares a short stick with
+2<i>m</i>/3−<i>k</i>−<i>ε</i>
+<li>
+that 2<i>m</i>/3−<i>k</i>−<i>ε</i> shares a long stick
+with <i>m</i>/3+2<i>k</i>+<i>ε</i>
+</ul>
+... and so on, so that we derive the existence of pieces of lengths
+<i>m</i>/3+<i>ε</i>, <i>m</i>/3+<i>k</i>+<i>ε</i>,
+<i>m</i>/3+2<i>k</i>+<i>ε</i>, …, 2<i>m</i>/3+<i>ε</i> (which we must
+reach since <i>m</i>/3 is an exact multiple of k). That
+2<i>m</i>/3+<i>ε</i> is still monolithic (recall that only a piece of
+at least 2<i>m</i>/3+2<i>ε</i> can avoid being so) and so it must
+share a short stick with a piece of length <i>m</i>/3−<i>ε</i>, which
+is shorter than our presumed minimum fragment. This is a
+contradiction, and hence we reject the initial assumption that a
+minimum fragment greater than
+<i>m</i>/3 was possible in the first place.
+</p>
+
+<h2>Computer search</h2>
+
+<p>
+FIXME: describe our two search strategies.
+</p>
+
+<p>
+FIXME: stress that one is exhaustive but the other depends on a
+conjectured denominator bound.
+</p>
+
+<p>
+FIXME: the two strategies are good at different cases.
+</p>
+
+<p>
+FIXME: link to git repo.
+</p>
+
+<h2>Table of known values</h2>
+
+<p>
+The table below shows the best minimum fragment size for all
+the <i>n</i>,<i>m</i> pairs I currently know the answer to, and the
+best upper and lower bounds I have for a few values I don't know.
+</p>
+
+<p>
+The table cells are colour-coded to indicate our confidence in each
+number. <span class="box known">Green</span> indicates that the
+correctness of the result depends only on our upper-bound
+proofs; <span class="box believed">greenish-yellow</span> indicates
+that the correctness depends on our exhaustive search program not
+having a bug in it; <span class="box probable">yellow</span> indicates
+that the correctness depends on our conjecture that denominators are
+no larger than <i>n</i> (and <em>also</em> on a search program not
+having a bug); <span class="box range">red</span> indicates that we
+actually don't know the value and have listed a range of possible
+answers.
+</p>
+
+<p>
+Each table cell links to a section further down the page giving an
+explicit dissection and discussing which (if any) upper bound proofs
+apply in that case.
+</p>
+
+<div>
%TABLE%
+</div>
+
+<h2>Observations from the data</h2>
+
+<p>
+FIXME: clear patterns in the <i>m</i>=3 and <i>m</i>=4 columns, and
+the bounding proofs seem consistently tight there too, so those cases
+may be tractable to establish a complete proof for.
+</p>
+
+<p>
+FIXME: the diagonal <i>n</i>=<i>m</i>+1 also looks nicely patterned.
+We don't have a reliably tight bound there, but it might be worth
+trying to prove that diagonal anyway, in the hope that we <em>can</em>
+discover another useful bounding proof!
+</p>
+
+<p>
+FIXME: the patterns in columns 3 and 4 suggest to me the more
+ambitious conjecture that perhaps a similar pattern holds in every
+column if you look at cells spaced vertically by <i>m</i>, e.g. all
+the points with <i>m</i>=5 and <i>n</i>≡1 mod 5. I don't think we have
+enough data here to say anything with confidence about that idea,
+though.
+</p>
+
+<p>
+FIXME: the case <i>n</i>=29,<i>m</i>=19 is especially intriguing for
+the heavy use of denominator 28 in a dissection with min fragment
+something/4.
+</p>
+
+<h2>Credits</h2>
+
+<p>
+FIXME: credit Ian, Tom, writinghawk, Jack for deAOCisation, anyone else?
+</p>
+
+<h2>The individual dissections</h2>
+
+<p>
+The output below is generated by a script from a collection of data
+files and simple on-the-fly algorithms, so that I can easily re-run it
+if and when I acquire more data. So it will look a bit stilted and
+formulaic; sorry about that.
+</p>
+
+<div>
%DISSECTIONS%
+</div>
+
</body>
</html>
~ianmdlvl / matchsticks-search.git / blobdiff