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 sub {
  28     vertical-align: -0.3em;
  29     font-size: 70%;
  30     line-height: 0;
  31 }
  32 </style>
  33 </head>
  34 <body>
  35
  36 <h1>Minimax matchstick dissection</h1>
  37
  38 <p>
  39 This web page documents my current state of knowledge about a
  40 combinatorial problem that occurred to me in the summer of 2013 and
  41 intrigued me by having no obviously simple answer. Several people have
  42 been kind enough to help me gather data and thoughts on the problem,
  43 so I'm putting up a web page collating all of that.
  44 </p>
  45
  46 <p>
  47 I have so far not heard of any previous work on the problem,
  48 although there is a strong possibility that such work exists and I
  49 just haven't heard about it. Please send details, if you have any!
  50 </p>
  51
  52 <h2>The problem</h2>
  53
  54 <p>
  55 The problem is a one-dimensional dissection. Let <i>m</i> and <i>n</i>
  56 be positive integers. Suppose we have <i>m</i> matchsticks, each of
  57 length <i>n</i>. We want to turn them into <i>n</i> sticks of
  58 length <i>m</i>, by cutting them into shorter fragments and then
  59 gluing the fragments back together.
  60 </p>
  61
  62 <p>
  63 The catch is that we don't like short fragments, and we like them less
  64 the shorter they are. So we want all the fragments to be nice and
  65 large. Specifically, we want to find a dissection whose <em>shortest
  66 fragment length</em> is as long as we can make it.
  67 </p>
  68
  69 <p>
  70 Obviously, one possible dissection is to cut up every stick
  71 into <i>n</i> pieces of length 1, and then stick them all back
  72 together in groups of <i>m</i>, giving a shortest fragment of 1.
  73 If <i>m</i> and <i>n</i> have a common factor, we can improve on this
  74 by cutting them into larger pieces, still all the same size. In
  75 general, this gives us a minimum fragment of gcd(<i>m</i>,<i>n</i>).
  76 (Another way to achieve this same result would be to glue all the
  77 sticks into one long stick and then cut that into <i>n</i> equal
  78 pieces. That dissection uses fewer fragments, but the shortest
  79 fragment length is still gcd(<i>m</i>,<i>n</i>), and we don't care
  80 about the details of the dissection other than that.)
  81 </p>
  82
  83 <p>
  84 In many cases, however, you can do better than that. The case that
  85 first brought this problem to my attention was the one with <i>n</i>=6
  86 and <i>m</i>=5. The trivial gcd solution gives you a minimum fragment
  87 of 1, but in fact we can dissect 6 sticks into 5 sticks with minimum
  88 fragment 2, by cutting up every length-5 stick as (2&nbsp;+&nbsp;3)
  89 and then reassembling as two lots of (2&nbsp;+&nbsp;2&nbsp;+&nbsp;2)
  90 and three lots of (3&nbsp;+&nbsp;3).
  91 </p>
  92
  93 <p>
  94 More interestingly still, the minimum fragment need not always even be
  95 an <em>integer</em>. (That was the aspect that surprised me enough to
  96 make the question really stick in my mind.) For example,
  97 consider <i>n</i>=5 and <i>m</i>=4: obviously if you use integer-sized
  98 fragments then you can't make the biggest fragment any larger than 1
  99 (each length-5 stick would need a fragment of odd length, and you
 100 can't cut an odd piece from a length-4 stick without generating a
 101 piece of length 1). However, if you don't insist on integer fragments,
 102 the dissection of 5 into 4 can be done with shortest fragment 3/2: cut
 103 four of the length-4 sticks slightly unevenly into 3/2&nbsp;+&nbsp;5/2
 104 and the last one evenly into 2&nbsp;+&nbsp;2, then make two length-5
 105 sticks as 5/2&nbsp;+&nbsp;5/2 and the other two as
 106 3/2&nbsp;+&nbsp;3/2&nbsp;+&nbsp2.
 107 </p>
 108
 109 <h2>Theory</h2>
 110
 111 <p>
 112 To begin with, we'll establish the convention
 113 that <i>m</i>&nbsp;&lt;&nbsp;<i>n</i>. (The problem is obviously
 114 symmetric in interchange of the two variables, and the
 115 case <i>m</i>&nbsp;=&nbsp;<i>n</i> requiring no cuts at all is so
 116 uninteresting that we may as well ignore it.)
 117 </p>
 118
 119 <h3>No irrationals</h3>
 120
 121 <p>
 122 We've established that the minimum fragment size need not be an
 123 integer, so an obvious next question is, need it even
 124 be <em>rational</em>?
 125 </p>
 126
 127 <p>
 128 The answer is yes, and we can prove it as follows. Consider an
 129 arbitrary dissection of <i>m</i> sticks into <i>n</i> containing at
 130 least one irrational fragment length. The lengths of all the fragments
 131 generate a finite-dimensional vector space over ℚ; let
 132 {&nbsp;<i>e</i><sub>1</sub>,&nbsp;…,&nbsp;<i>e</i><sub><i>k</i></sub>&nbsp;}
 133 be a basis for that space in which <i>e</i><sub>1</sub> is rational.
 134 Then the shortest irrational fragment length must have a nonzero
 135 coefficient of some basis element other than <i>e</i><sub>1</sub>,
 136 say <i>e</i><sub><i>i</i></sub>.
 137 </p>
 138
 139 <p>
 140 Now we construct a new dissection based on the old one, in which we
 141 adjust every fragment length by adding <i>ε</i> times its original
 142 value's coefficient of <i>e</i><sub><i>i</i></sub>, for some
 143 constant <i>ε</i>. Doing this must preserve the property that the
 144 fragments making up each input and output stick sum to the right total
 145 length (proof: the original <i>e</i><sub><i>i</i></sub> coefficients
 146 must have summed to zero in order to generate an integer stick length
 147 previously, so adding a constant multiple of all
 148 those <i>e</i><sub><i>i</i></sub> coefficients doesn't change the
 149 overall sum). So now we choose |<i>ε</i>| small enough that no two
 150 original fragment lengths change their ordering and no fragment length
 151 becomes negative or more than the entire stick size. (We can do this,
 152 since those constraints give us finitely many upper bounds all of
 153 which are strictly positive, so we can certainly find an <i>ε</i>
 154 smaller than all of them and still nonzero. The only interesting case
 155 is when a fragment was the whole of its stick – in which case it has a
 156 zero coefficient of <i>e</i><sub><i>i</i></sub> anyway, so we aren't
 157 changing it at all and no bound is placed on <i>ε</i> by the
 158 requirement for it not to overflow.) Finally, we choose the sign
 159 of <i>ε</i> so that it lengthens rather than shortening the smallest
 160 irrational fragment.
 161 </p>
 162
 163 <p>
 164 So now we've constructed a new dissection of basically the same shape
 165 as the old one, in which every fragment length is adjusted by at most
 166 a small amount, with the properties that:
 167 <ul>
 168 <li>
 169 ordering of lengths is preserved (if one fragment was shorter than
 170 another in the old dissection then it is in the new dissection too)
 171 <li>
 172 in particular, equal fragment lengths remain equal (because they had
 173 the same <i>e</i><sub><i>i</i></sub> coefficient so we adjusted them
 174 by the same amount)
 175 <li>
 176 rational fragment lengths are unchanged from the original dissection
 177 (they had a zero <i>e</i><sub><i>i</i></sub> coefficient)
 178 <li>
 179 what was previously the shortest irrational fragment length is now
 180 slightly longer.
 181 </ul>
 182 This means that no dissection with the shortest fragment irrational
 183 can be optimal, since the above construction would improve it.
 184 </p>
 185
 186 <p>
 187 Also, if we were to strengthen our optimisation criterion by imposing
 188 a tie-breaking condition in which dissections with the same shortest
 189 fragment were compared by looking at the <em>next</em> shortest
 190 fragment and so on, then any dissection optimal under that stronger
 191 condition would have to have <em>every</em> fragment length rational
 192 (because, again, we could always lengthen the shortest irrational one,
 193 without changing any of the rational fragment lengths shorter than
 194 it). This implies that not only must the minimum fragment size always
 195 be rational, but also there must always be an all-rational dissection
 196 which attains it. So we can rule irrationals completely out of
 197 consideration, which is a relief!
 198 </p>
 199
 200 <h3>Upper bounds</h3>
 201
 202 <p>
 203 A problem with searching for dissections is, once you've found one,
 204 how do you prove there isn't a completely different one that does
 205 better?
 206 </p>
 207
 208 <p>
 209 One way to solve that problem is to find a genuinely exhaustive search
 210 strategy, one of which is described in the next section. But
 211 exhaustive searches are expensive, so it would be nice to have some
 212 other tools in our toolbox as well, such as strategies for proving
 213 that no solution for a given <i>n</i>,<i>m</i> can be better than a
 214 given value. Then, if you can find an upper bound proof <em>and</em> a
 215 dissection attaining that bound, you know you don't have to look any
 216 further.
 217 </p>
 218
 219 <p>
 220 One such upper bound proof, largely due
 221 to <a href="http://writinghawk.livejournal.com/profile">writinghawk</a>,
 222 works by counting the pieces in the dissection. For this proof, we
 223 start by assuming that every length-<i>m</i> stick (i.e. every shorter
 224 stick) is cut into at least two pieces; this doesn't lose generality,
 225 because if any stick remains whole in a dissection, we can just cut it
 226 in half and put both the pieces into the same <i>n</i>-stick. (And
 227 this does not decrease the minimum fragment length
 228 unless <em>all</em> <i>m</i>-sticks were whole, i.e. <i>m</i>
 229 divides <i>n</i>, which is a special case with such an obvious answer
 230 that we don't need this proof anyway.)
 231 </p>
 232
 233 <p>
 234 So, let's suppose that every piece is at least length <i>s</i>. Also,
 235 every piece must be at <em>most</em>
 236 length <i>m</i>&nbsp;−&nbsp;<i>s</i> (because it must have been part
 237 of some <i>m</i>-stick, which had a piece of at least <i>s</i> cut off
 238 it).
 239 </p>
 240
 241 <p>
 242 That means that each stick of length <i>n</i> has to be cut into at
 243 least <i>n</i>/(<i>m</i>−<i>s</i>) and at most <i>n</i>/<i>s</i>
 244 pieces (otherwise some piece would have to be too long or too short).
 245 Because the number of pieces also has to be an integer, that really
 246 means it's at least ⌈<i>n</i>/(<i>m</i>−<i>s</i>)⌉ and at most
 247 ⌊<i>n</i>/<i>s</i>⌋. Summing those expressions over
 248 all <i>n</i>-sticks tells us that the total number of pieces <i>P</i>
 249 in the whole dissection must satisfy the
 250 inequality <i>m</i>⌈<i>n</i>/(<i>m</i>−<i>s</i>)⌉&nbsp;≤&nbsp;<i>P</i>&nbsp;≤&nbsp;<i>m</i>⌊<i>n</i>/<i>s</i>⌋.
 251 </p>
 252
 253 <p>
 254 By similarly considering the number of pieces that a stick of
 255 length <i>m</i> is cut into, we derive a second
 256 inequality <i>n</i>⌈<i>m</i>/(<i>m</i>−<i>s</i>)⌉&nbsp;≤&nbsp;<i>P</i>&nbsp;≤&nbsp;<i>n</i>⌊<i>m</i>/<i>s</i>⌋.
 257 (This is identical to the first inequality, but with <i>n</i>
 258 and <i>m</i> swapped everywhere they appear except in the
 259 divisor <i>m</i>−<i>s</i>).
 260 </p>
 261
 262 <p>
 263 So when <i>s</i> becomes big enough that either of those inequalities
 264 is self-inconsistent (with its LHS strictly larger than its RHS), or
 265 when the two are incompatible (because they define ranges for <i>P</i>
 266 that do not meet), there can be no dissection with <i>s</i> that
 267 large. This allows us to establish an upper bound on <i>s</i> for a
 268 given instance of the problem, which is often (but, results below
 269 indicate, not always) actually achievable.
 270 </p>
 271
 272 <p>
 273 A second upper-bound proof, due to Tom Womack, applies in a restricted
 274 set of cases, some of which are not solved optimally by the above
 275 proof. Specifically: if <i>m</i>/3 is an integer and is also a
 276 multiple of <i>n</i>−<i>m</i>, then no solution can be better
 277 than <i>m</i>/3.
 278 </p>
 279
 280 <p>
 281 Proof: suppose the shortest fragment is <i>m</i>/3&nbsp;+&nbsp;<i>ε</i> for
 282 some <i>ε</i>&nbsp;&gt;&nbsp;0. Then if any segment of stick less
 283 than <em>twice</em> that length arises while you're dissecting, it
 284 must remain whole. In particular, any fragment shorter than
 285 2<i>m</i>/3&nbsp;+&nbsp;2<i>ε</i> must be monolithic in this way.
 286 </p>
 287
 288 <p>
 289 So consider a stick of length m from which we cut a piece of
 290 length <i>m</i>/3+<i>ε</i>. The other piece of that stick has length 2<i>m</i>/3−<i>ε</i> and
 291 hence is monolithic; so it must have been cut as a whole from a longer
 292 stick of length <i>n</i>. Let <i>n</i>&nbsp;=&nbsp;<i>m</i>+<i>k</i>, because we'll want to talk about <i>k</i> a
 293 lot. Now we reason as follows:
 294 <ul>
 295 <li>
 296 a piece <i>m</i>/3+<i>ε</i> shares a short stick with
 297 2<i>m</i>/3−<i>ε</i>
 298 <li>
 299 that 2<i>m</i>/3−<i>ε</i> shares a long stick
 300 with <i>m</i>/3+<i>k</i>+<i>ε</i>
 301 <li>
 302 that <i>m</i>/3+<i>k</i>+<i>ε</i> shares a short stick with
 303 2<i>m</i>/3−<i>k</i>−<i>ε</i>
 304 <li>
 305 that 2<i>m</i>/3−<i>k</i>−<i>ε</i> shares a long stick
 306 with <i>m</i>/3+2<i>k</i>+<i>ε</i>
 307 </ul>
 308 ... and so on, so that we derive the existence of pieces of lengths
 309 <i>m</i>/3+<i>ε</i>, <i>m</i>/3+<i>k</i>+<i>ε</i>,
 310 <i>m</i>/3+2<i>k</i>+<i>ε</i>, …, 2<i>m</i>/3+<i>ε</i> (which we must
 311 reach since <i>m</i>/3 is an exact multiple of k). That
 312 2<i>m</i>/3+<i>ε</i> is still monolithic (recall that only a piece of
 313 at least 2<i>m</i>/3+2<i>ε</i> can avoid being so) and so it must
 314 share a short stick with a piece of length <i>m</i>/3−<i>ε</i>, which
 315 is shorter than our presumed minimum fragment. This is a
 316 contradiction, and hence we reject the initial assumption that a
 317 minimum fragment greater than
 318 <i>m</i>/3 was possible in the first place.
 319 </p>
 320
 321 <h2>Computer search</h2>
 322
 323 <p>
 324 FIXME: describe our two search strategies.
 325 </p>
 326
 327 <p>
 328 FIXME: stress that one is exhaustive but the other depends on a
 329 conjectured denominator bound.
 330 </p>
 331
 332 <p>
 333 FIXME: the two strategies are good at different cases.
 334 </p>
 335
 336 <p>
 337 FIXME: link to git repo.
 338 </p>
 339
 340 <h2>Table of known values</h2>
 341
 342 <p>
 343 The table below shows the best minimum fragment size for all
 344 the <i>n</i>,<i>m</i> pairs I currently know the answer to, and the
 345 best upper and lower bounds I have for a few values I don't know.
 346 </p>
 347
 348 <p>
 349 The table cells are colour-coded to indicate our confidence in each
 350 number. <span class="box known">Green</span> indicates that the
 351 correctness of the result depends only on our upper-bound
 352 proofs; <span class="box believed">greenish-yellow</span> indicates
 353 that the correctness depends on our exhaustive search program not
 354 having a bug in it; <span class="box probable">yellow</span> indicates
 355 that the correctness depends on our conjecture that denominators are
 356 no larger than <i>n</i> (and <em>also</em> on a search program not
 357 having a bug); <span class="box range">red</span> indicates that we
 358 actually don't know the value and have listed a range of possible
 359 answers.
 360 </p>
 361
 362 <p>
 363 Each table cell links to a section further down the page giving an
 364 explicit dissection and discussing which (if any) upper bound proofs
 365 apply in that case.
 366 </p>
 367
 368 <div>
 369 %TABLE%
 370 </div>
 371
 372 <h2>Observations from the data</h2>
 373
 374 <p>
 375 FIXME: clear patterns in the <i>m</i>=3 and <i>m</i>=4 columns, and
 376 the bounding proofs seem consistently tight there too, so those cases
 377 may be tractable to establish a complete proof for.
 378 </p>
 379
 380 <p>
 381 FIXME: the diagonal <i>n</i>=<i>m</i>+1 also looks nicely patterned.
 382 We don't have a reliably tight bound there, but it might be worth
 383 trying to prove that diagonal anyway, in the hope that we <em>can</em>
 384 discover another useful bounding proof!
 385 </p>
 386
 387 <p>
 388 FIXME: the patterns in columns 3 and 4 suggest to me the more
 389 ambitious conjecture that perhaps a similar pattern holds in every
 390 column if you look at cells spaced vertically by <i>m</i>, e.g. all
 391 the points with <i>m</i>=5 and <i>n</i>≡1 mod 5. I don't think we have
 392 enough data here to say anything with confidence about that idea,
 393 though.
 394 </p>
 395
 396 <p>
 397 FIXME: the case <i>n</i>=29,<i>m</i>=19 is especially intriguing for
 398 the heavy use of denominator 28 in a dissection with min fragment
 399 something/4.
 400 </p>
 401
 402 <h2>Credits</h2>
 403
 404 <p>
 405 FIXME: credit Ian, Tom, writinghawk, Jack for deAOCisation, anyone else?
 406 </p>
 407
 408 <h2>The individual dissections</h2>
 409
 410 <p>
 411 The output below is generated by a script from a collection of data
 412 files and simple on-the-fly algorithms, so that I can easily re-run it
 413 if and when I acquire more data. So it will look a bit stilted and
 414 formulaic; sorry about that.
 415 </p>
 416
 417 <div>
 418 %DISSECTIONS%
 419 </div>
 420
 421 </body>
 422 </html>