From 83522686e4bd5f0a877f3adf5d94e3b351a774f6 Mon Sep 17 00:00:00 2001 From: Simon Tatham Date: Thu, 20 Mar 2014 18:59:54 +0000 Subject: [PATCH] Fill in a lot of the web page. There's still a lot of writeup left to do, though! --- tabulate.py | 6 +- template.html | 211 ++++++++++++++++++++++++++++++++++++++++++++++++-- 2 files changed, 209 insertions(+), 8 deletions(-) diff --git a/tabulate.py b/tabulate.py index 7130aff..79d6153 100755 --- a/tabulate.py +++ b/tabulate.py @@ -151,8 +151,8 @@ def read_and_build_table_cell(n,m): ret += show_bound % str(bound) ret += "\n" - dump = "

n=%d, m=%d

\n" % (n, m, n, m) - dump += "

Best dissection known for %d into %d, with minimum fragment %s:\n" % (n, m, str(best)) + dump = "

n=%d, m=%d

\n" % (n, m, n, m) + dump += "

Best dissection known for %d into %d: minimum fragment is %s.\n" % (n, m, str(best)) dump += "

Cut up %d sticks of length %d as follows:

%d × (%s)\n" % (count, " + ".join(map(str, pieces))) @@ -187,7 +187,7 @@ def main(args): table = "" table += "\n" - table += "\n" + table += "\n" for m in range(2,limit-1): table += "\n" % m table += "\n" diff --git a/template.html b/template.html index cd6da57..6d2d755 100644 --- a/template.html +++ b/template.html @@ -1,27 +1,228 @@ + -Known bounds for stick-dissecting problem +Minimax matchstick dissection + +

Minimax matchstick dissection

+ +

+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. +

+ +

+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! +

+ +

The problem

+ +

+The problem is a one-dimensional dissection. Let m and n +be positive integers. Suppose we have m matchsticks, each of +length n. We want to turn them into n sticks of +length m, by cutting them into shorter fragments and then +gluing the fragments back together. +

+ +

+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 shortest +fragment length is as long as we can make it. +

+ +

+Obviously, one possible dissection is to cut up every stick +into n pieces of length 1, and then stick them all back +together in groups of m, giving a shortest fragment of 1. +If m and n 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(m,n). +(Another way to achieve this same result would be to glue all the +sticks into one long stick and then cut that into n equal +pieces. That dissection uses fewer fragments, but the shortest +fragment length is still gcd(m,n), and we don't care +about the details of the dissection other than that.) +

+ +

+In many cases, however, you can do better than that. The case that +first brought this problem to my attention was the one with n=6 +and m=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). +

+ +

+More interestingly still, the minimum fragment need not always even be +an integer. (That was the aspect that surprised me enough to +make the question really stick in my mind.) For example, +consider n=5 and m=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. +

+ +

Theory

+ +

+To begin with, we'll establish the convention +that m < n. (The problem is obviously +symmetric in interchange of the two variables, and the +case m = n requiring no cuts at all is so +uninteresting that we may as well ignore it.) +

+ +

+FIXME: min frag is rational. +

+ +

+FIXME: empirical observation suggests conjecture that denominator is +bounded by n, but no proof of this. +

+ +

+FIXME: state the known upper bound proofs. +

+ +

Computer search

+ +

+FIXME: describe our two search strategies. +

+ +

+FIXME: stress that one is exhaustive but the other depends on the +conjectured denominator bound. +

+ +

+FIXME: the two strategies are good at different cases. +

+ +

+FIXME: link to git repo. +

+ +

Table of known values

+ +

+The table below shows the best minimum fragment size for all +the n,m pairs I currently know the answer to, and the +best upper and lower bounds I have for a few values I don't know. +

+ +

+The table cells are colour-coded to indicate our confidence in each +number. Green indicates that the +correctness of the result depends only on our upper-bound +proofs; greenish-yellow indicates +that the correctness depends on our exhaustive search program not +having a bug in it; yellow indicates +that the correctness depends on our conjecture that denominators are +no larger than n (and also on a search program not +having a bug); red indicates that we +actually don't know the value and have listed a range of possible +answers. +

+ +

+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. +

+ +

%TABLE% +

+ +

Observations from the data

+ +

+FIXME: clear patterns in the m=3 and m=4 columns, and +the bounding proofs seem consistently tight there too, so those cases +may be tractable to establish a complete proof for. +

+ +

+FIXME: the diagonal n=m+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 can +discover another useful bounding proof! +

+ +

+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 m, e.g. all +the points with m=5 and nâ¡1 mod 5. I don't think we have +enough data here to say anything with confidence about that idea, +though. +

+ +

+FIXME: the case n=29,m=19 is especially intriguing for +the heavy use of denominator 28 in a dissection with min fragment +something/4. +

+ +

Credits

+ +

+FIXME: credit Ian, Tom, writinghawk, Jack for deAOCisation, anyone else? +

+ +

The individual dissections

+ +

+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. +

+ +

%DISSECTIONS% +

+ -- 2.30.2

n \\ m	n \\ m	%d