<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.
+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> × <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>
+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>
+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>
<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 − 1/4, 3/2 − 1/6, 3/2 − 1/8,
+3/2 − 1/10, 3/2 − 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>
~ianmdlvl / matchsticks-search.git / blobdiff