template.html

   1 <html>
   2 <meta http-equiv="Content-type" content="text/html; charset=UTF-8">
   3 <head>
   4 <title>Minimax matchstick dissection</title>
   5 <style type="text/css">
   6 table, td, th {
   7     border: 1px solid black;
   8     border-collapse: collapse;
   9 }
  10 .box {
  11     border: 1px solid black;
  12     padding-left: 0.3em;
  13     padding-right: 0.3em;
  14 }
  15 .known {
  16     background-color: #00ff00;
  17 }
  18 .believed {
  19     background-color: #aaff00;
  20 }
  21 .probable {
  22     background-color: #ffff00;
  23 }
  24 .range {
  25     background-color: #ff8888;
  26 }
  27 </style>
  28 </head>
  29 <body>
  30
  31 <h1>Minimax matchstick dissection</h1>
  32
  33 <p>
  34 This web page documents my current state of knowledge about a
  35 combinatorial problem that occurred to me in the summer of 2013 and
  36 intrigued me by having no obviously simple answer. Several people have
  37 been kind enough to help me gather data and thoughts on the problem,
  38 so I'm putting up a web page collating all of that.
  39 </p>
  40
  41 <p>
  42 I have so far not heard of any previous work on the problem,
  43 although there is a strong possibility that such work exists and I
  44 just haven't heard about it. Please send details, if you have any!
  45 </p>
  46
  47 <h2>The problem</h2>
  48
  49 <p>
  50 The problem is a one-dimensional dissection. Let <i>m</i> and <i>n</i>
  51 be positive integers. Suppose we have <i>m</i> matchsticks, each of
  52 length <i>n</i>. We want to turn them into <i>n</i> sticks of
  53 length <i>m</i>, by cutting them into shorter fragments and then
  54 gluing the fragments back together.
  55 </p>
  56
  57 <p>
  58 The catch is that we don't like short fragments, and we like them less
  59 the shorter they are. So we want all the fragments to be nice and
  60 large. Specifically, we want to find a dissection whose <em>shortest
  61 fragment length</em> is as long as we can make it.
  62 </p>
  63
  64 <p>
  65 Obviously, one possible dissection is to cut up every stick
  66 into <i>n</i> pieces of length 1, and then stick them all back
  67 together in groups of <i>m</i>, giving a shortest fragment of 1.
  68 If <i>m</i> and <i>n</i> have a common factor, we can improve on this
  69 by cutting them into larger pieces, still all the same size. In
  70 general, this gives us a minimum fragment of gcd(<i>m</i>,<i>n</i>).
  71 (Another way to achieve this same result would be to glue all the
  72 sticks into one long stick and then cut that into <i>n</i> equal
  73 pieces. That dissection uses fewer fragments, but the shortest
  74 fragment length is still gcd(<i>m</i>,<i>n</i>), and we don't care
  75 about the details of the dissection other than that.)
  76 </p>
  77
  78 <p>
  79 In many cases, however, you can do better than that. The case that
  80 first brought this problem to my attention was the one with <i>n</i>=6
  81 and <i>m</i>=5. The trivial gcd solution gives you a minimum fragment
  82 of 1, but in fact we can dissect 6 sticks into 5 sticks with minimum
  83 fragment 2, by cutting up every length-5 stick as (2&nbsp;+&nbsp;3)
  84 and then reassembling as two lots of (2&nbsp;+&nbsp;2&nbsp;+&nbsp;2)
  85 and three lots of (3&nbsp;+&nbsp;3).
  86 </p>
  87
  88 <p>
  89 More interestingly still, the minimum fragment need not always even be
  90 an <em>integer</em>. (That was the aspect that surprised me enough to
  91 make the question really stick in my mind.) For example,
  92 consider <i>n</i>=5 and <i>m</i>=4: obviously if you use integer-sized
  93 fragments then you can't make the biggest fragment any larger than 1
  94 (each length-5 stick would need a fragment of odd length, and you
  95 can't cut an odd piece from a length-4 stick without generating a
  96 piece of length 1). However, if you don't insist on integer fragments,
  97 the dissection of 5 into 4 can be done with shortest fragment 3/2: cut
  98 four of the length-4 sticks slightly unevenly into 3/2&nbsp;+&nbsp;5/2
  99 and the last one evenly into 2&nbsp;+&nbsp;2, then make two length-5
 100 sticks as 5/2&nbsp;+&nbsp;5/2 and the other two as
 101 3/2&nbsp;+&nbsp;3/2&nbsp;+&nbsp2.
 102 </p>
 103
 104 <h2>Theory</h2>
 105
 106 <p>
 107 To begin with, we'll establish the convention
 108 that <i>m</i>&nbsp;&lt;&nbsp;<i>n</i>. (The problem is obviously
 109 symmetric in interchange of the two variables, and the
 110 case <i>m</i>&nbsp;=&nbsp;<i>n</i> requiring no cuts at all is so
 111 uninteresting that we may as well ignore it.)
 112 </p>
 113
 114 <p>
 115 FIXME: min frag is rational.
 116 </p>
 117
 118 <p>
 119 FIXME: empirical observation suggests conjecture that denominator is
 120 bounded by <i>n</i>, but no proof of this.
 121 </p>
 122
 123 <p>
 124 FIXME: state the known upper bound proofs.
 125 </p>
 126
 127 <h2>Computer search</h2>
 128
 129 <p>
 130 FIXME: describe our two search strategies.
 131 </p>
 132
 133 <p>
 134 FIXME: stress that one is exhaustive but the other depends on the
 135 conjectured denominator bound.
 136 </p>
 137
 138 <p>
 139 FIXME: the two strategies are good at different cases.
 140 </p>
 141
 142 <p>
 143 FIXME: link to git repo.
 144 </p>
 145
 146 <h2>Table of known values</h2>
 147
 148 <p>
 149 The table below shows the best minimum fragment size for all
 150 the <i>n</i>,<i>m</i> pairs I currently know the answer to, and the
 151 best upper and lower bounds I have for a few values I don't know.
 152 </p>
 153
 154 <p>
 155 The table cells are colour-coded to indicate our confidence in each
 156 number. <span class="box known">Green</span> indicates that the
 157 correctness of the result depends only on our upper-bound
 158 proofs; <span class="box believed">greenish-yellow</span> indicates
 159 that the correctness depends on our exhaustive search program not
 160 having a bug in it; <span class="box probable">yellow</span> indicates
 161 that the correctness depends on our conjecture that denominators are
 162 no larger than <i>n</i> (and <em>also</em> on a search program not
 163 having a bug); <span class="box range">red</span> indicates that we
 164 actually don't know the value and have listed a range of possible
 165 answers.
 166 </p>
 167
 168 <p>
 169 Each table cell links to a section further down the page giving an
 170 explicit dissection and discussing which (if any) upper bound proofs
 171 apply in that case.
 172 </p>
 173
 174 <div>
 175 %TABLE%
 176 </div>
 177
 178 <h2>Observations from the data</h2>
 179
 180 <p>
 181 FIXME: clear patterns in the <i>m</i>=3 and <i>m</i>=4 columns, and
 182 the bounding proofs seem consistently tight there too, so those cases
 183 may be tractable to establish a complete proof for.
 184 </p>
 185
 186 <p>
 187 FIXME: the diagonal <i>n</i>=<i>m</i>+1 also looks nicely patterned.
 188 We don't have a reliably tight bound there, but it might be worth
 189 trying to prove that diagonal anyway, in the hope that we <em>can</em>
 190 discover another useful bounding proof!
 191 </p>
 192
 193 <p>
 194 FIXME: the patterns in columns 3 and 4 suggest to me the more
 195 ambitious conjecture that perhaps a similar pattern holds in every
 196 column if you look at cells spaced vertically by <i>m</i>, e.g. all
 197 the points with <i>m</i>=5 and <i>n</i>≡1 mod 5. I don't think we have
 198 enough data here to say anything with confidence about that idea,
 199 though.
 200 </p>
 201
 202 <p>
 203 FIXME: the case <i>n</i>=29,<i>m</i>=19 is especially intriguing for
 204 the heavy use of denominator 28 in a dissection with min fragment
 205 something/4.
 206 </p>
 207
 208 <h2>Credits</h2>
 209
 210 <p>
 211 FIXME: credit Ian, Tom, writinghawk, Jack for deAOCisation, anyone else?
 212 </p>
 213
 214 <h2>The individual dissections</h2>
 215
 216 <p>
 217 The output below is generated by a script from a collection of data
 218 files and simple on-the-fly algorithms, so that I can easily re-run it
 219 if and when I acquire more data. So it will look a bit stilted and
 220 formulaic; sorry about that.
 221 </p>
 222
 223 <div>
 224 %DISSECTIONS%
 225 </div>
 226
 227 </body>
 228 </html>