<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;
}
</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>
+
+<p>
+FIXME: min frag is rational.
+</p>
+
+<p>
+FIXME: empirical observation suggests conjecture that denominator is
+bounded by <i>n</i>, but no proof of this.
+</p>
+
+<p>
+FIXME: state the known upper bound proofs.
+</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 the
+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 / commitdiff