chiark / gitweb /
Filled in the observations section.
[matchsticks-search.git] / template.html
index 6d2d755b456caac3013035b0bf276c4c38c4f1dd..a5c4951a8c8924aaefbeedf8904030799abe66d7 100644 (file)
@@ -24,6 +24,11 @@ table, td, th {
 .range {
     background-color: #ff8888;
 }
+sub {
+    vertical-align: -0.3em;
+    font-size: 70%;
+    line-height: 0;
+}
 </style>
 </head>
 <body>
@@ -111,32 +116,279 @@ case <i>m</i>&nbsp;=&nbsp;<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
+{&nbsp;<i>e</i><sub>1</sub>,&nbsp;…,&nbsp;<i>e</i><sub><i>k</i></sub>&nbsp;}
+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>
-FIXME: min frag is rational.
+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>
-FIXME: empirical observation suggests conjecture that denominator is
-bounded by <i>n</i>, but no proof of this.
+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>
-FIXME: state the known upper bound proofs.
+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>&nbsp;−&nbsp;<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>)⌉&nbsp;≤&nbsp;<i>P</i>&nbsp;≤&nbsp;<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>)⌉&nbsp;≤&nbsp;<i>P</i>&nbsp;≤&nbsp;<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&nbsp;+&nbsp;<i>ε</i> for
+some <i>ε</i>&nbsp;&gt;&nbsp;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&nbsp;+&nbsp;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>&nbsp;=&nbsp;<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.
+We've done some computer searching to find the answers, or the
+probable answers, to small cases. We've got two different search
+strategies:
+</p>
+
+<p>
+<b>Iterate over adjacency matrices</b>. This strategy relies on the
+idea that we can assume, without loss of generality, that each input
+stick contributes at most one piece to each output stick. (This is the
+reverse of the assumption made in the proof of writinghawk's upper
+bound above! But fortunately they don't have to both be true at the
+same time.) So you could draw up an <i>n</i>&nbsp;×&nbsp;<i>m</i>
+matrix indicating which input sticks contributed to which output
+sticks. Given such a matrix, the problem of finding an optimal
+dissection <em>with that matrix</em> can be written as a linear
+programming problem. (One variable per dissection fragment is the
+obvious way, but then the objective function ‘take the minimum’ isn't
+linear. But if you add an extra variable showing the minimum size
+itself, and then make the other variables say by how much each other
+piece <em>exceeds</em> the minimum fragment, then it is linear.) So,
+in principle, we can just iterate over all the possible
+2<sup><i>nm</i></sup> adjacency matrices, and solve a linear
+programming problem for each one! Of course this takes exponential
+time, but it turns out reasonably practicable in small cases as long
+as you prune branches of the search tree early and often if you can
+easily show they can't give a result as good as the best one you
+already have.
+</p>
+
+<p>
+<b>ILP over possible stick partitions</b>. A completely different
+approach is to enumerate the various ways in which a stick can be
+partitioned into smaller pieces. (There are infinitely many, of
+course, but if you pick a denominator <i>d</i> and constrain to
+multiples of 1/<i>d</i> then that's not too bad.) This approach
+requires us to make a guess at the minimum fragment, so that we can
+enumerate partitions which use pieces no smaller than that. Once we
+have a list of the partition types for the input and output sticks, we
+express them as vectors showing how many pieces of what lengths they
+use, and then solve an integer-linear-programming problem to find
+combinations of them for which all the piece counts add up. Again, ILP
+is a computationally hard problem, but this algorithm seems to work OK
+in small cases because if you start your minimum fragment <em>too
+big</em> and lower it until you get a solution, you never
+have <em>too</em> many possible partitions to worry about.
 </p>
 
 <p>
-FIXME: stress that one is exhaustive but the other depends on the
-conjectured denominator bound.
+The first of these strategies is genuinely exhaustive: assuming no
+bugs in the search program, the algorithm must find the best possible
+dissection. The second, however, leaves open the possibility that a
+better dissection might exist using a denominator larger than any we
+had considered. Examination of the data we have so far strongly
+suggests the conjecture that no denominator larger than <i>n</i> is
+ever needed in an optimal dissection (though denominators larger
+than <i>m</i> can certainly occur), but we have no proof of that, and
+so results generated by the second search program cannot be considered
+reliable unless an upper bound proof confirms that they can't be
+beaten.
 </p>
 
 <p>
-FIXME: the two strategies are good at different cases.
+Disregarding that weakness of the ILP approach, the two search
+algorithms complement each other well, because once <i>n</i> gets a
+bit larger we find that the matrix iteration algorithm works best for
+small <i>m</i>, while the ILP approach works best for large <i>m</i>
+(i.e. not much smaller than <i>n</i>). So running both has allowed us
+to collect a reasonable amount of data.
 </p>
 
 <p>
@@ -178,31 +430,49 @@ apply in that case.
 <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.
+Looking at the above table, there are clear patterns in the <i>m</i>=3
+and <i>m</i>=4 columns. The sequence of fractional values 5/4, 4/3,
+11/8, 7/5, 17/12, … shows an obvious regularity if you rewrite it as
+3/2&nbsp;−&nbsp;1/4, 3/2&nbsp;−&nbsp;1/6, 3/2&nbsp;−&nbsp;1/8,
+3/2&nbsp;−&nbsp;1/10, 3/2&nbsp;−&nbsp;1/12, …. And the fractions in
+the <i>m</i>=4 column tend upwards to 2 in a similar harmonic series
+too. The upper bound proofs seem to be tight everywhere in these
+columns as well (assuming the two uncertain cases in the <i>m</i>=4
+column go as expected), so it may be tractable to establish a rigorous
+proof completely solving the problem for these two values of <i>m</i>.
 </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>
+There's also a nice pattern down the diagonal <i>n</i>=<i>m</i>+1. Our
+current bounding proofs are not reliably tight in that region, but it
+might be worth trying anyway to prove that that pattern holds along
+the whole diagonal, in the hope that in the process 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.
+The patterns in columns 3 and 4 suggest a more ambitious conjecture to
+me. Each of those columns has obviously different behaviour depending
+on the value of <i>n</i> mod <i>m</i> (e.g. in the <i>m</i>=3 column
+the sequence of fractions is interrupted every third cell because
+something obviously different happens when <i>n</i> is a multiple of
+3), but if you split up each column into <i>m</i> subcolumns by taking
+every <i>m</i>th cell, the pattern in each subcolumn is much simpler,
+being either constant or harmonic. So the more ambitious conjecture
+isf that perhaps a similarly simple pattern (of some sort) might hold
+in <em>every</em> column, if you split it into subcolumns by the value
+of <i>n</i> mod <i>m</i>. 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.
+The case <i>n</i>=29,<i>m</i>=19 is especially intriguing for the fact
+that the largest denominator used in
+the <a href="#details_29_19">whole dissection</a> is 28, though the
+denominator of the <em>minimum</em> fragment is only 4. (And that
+dissection was found by the ILP search program, which tries small
+denominators first, so I think there probably is no dissection with
+the same minimum fragment and less silly other fragment lengths.)
 </p>
 
 <h2>Credits</h2>