chiark / gitweb /
Fill in a lot of the web page.
authorSimon Tatham <anakin@pobox.com>
Thu, 20 Mar 2014 18:59:54 +0000 (18:59 +0000)
committerSimon Tatham <anakin@pobox.com>
Thu, 20 Mar 2014 19:47:42 +0000 (19:47 +0000)
There's still a lot of writeup left to do, though!

tabulate.py
template.html

index 7130aff..79d6153 100755 (executable)
@@ -151,8 +151,8 @@ def read_and_build_table_cell(n,m):
         ret += show_bound % str(bound)
     ret += "</a></td>\n"
 
-    dump = "<h2><a name=\"details_%d_%d\">n=%d, m=%d</a></h2>\n" % (n, m, n, m)
-    dump += "<p>Best dissection known for %d into %d, with minimum fragment %s:\n" % (n, m, str(best))
+    dump = "<h3><a name=\"details_%d_%d\">n=%d, m=%d</a></h3>\n" % (n, m, n, m)
+    dump += "<p>Best dissection known for %d into %d: minimum fragment is %s.\n" % (n, m, str(best))
     dump += "<ul><li>Cut up %d sticks of length %d as follows:<ul>\n" % (m, n)
     for count, pieces in dissection[0]:
         dump += "<li>%d &times; (%s)\n" % (count, " + ".join(map(str, pieces)))
@@ -187,7 +187,7 @@ def main(args):
 
     table = "<table>"
     table += "<tr>\n"
-    table += "<th>n \\ m</th>\n"
+    table += "<th>n&nbsp;\\&nbsp;m</th>\n"
     for m in range(2,limit-1):
         table += "<th>%d</th>\n" % m
     table += "</tr>\n"
index cd6da57..6d2d755 100644 (file)
 <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&nbsp;+&nbsp;3)
+and then reassembling as two lots of (2&nbsp;+&nbsp;2&nbsp;+&nbsp;2)
+and three lots of (3&nbsp;+&nbsp;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&nbsp;+&nbsp;5/2
+and the last one evenly into 2&nbsp;+&nbsp;2, then make two length-5
+sticks as 5/2&nbsp;+&nbsp;5/2 and the other two as
+3/2&nbsp;+&nbsp;3/2&nbsp;+&nbsp2.
+</p>
+
+<h2>Theory</h2>
+
+<p>
+To begin with, we'll establish the convention
+that <i>m</i>&nbsp;&lt;&nbsp;<i>n</i>. (The problem is obviously
+symmetric in interchange of the two variables, and the
+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>
+
+<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>