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 We've done some computer searching to find the answers, or the
 325 probable answers, to small cases. We've got two different search
 326 strategies:
 327 </p>
 328
 329 <p>
 330 <b>Iterate over adjacency matrices</b>. This strategy relies on the
 331 idea that we can assume, without loss of generality, that each input
 332 stick contributes at most one piece to each output stick. (This is the
 333 reverse of the assumption made in the proof of writinghawk's upper
 334 bound above! But fortunately they don't have to both be true at the
 335 same time.) So you could draw up an <i>n</i>&nbsp;×&nbsp;<i>m</i>
 336 matrix indicating which input sticks contributed to which output
 337 sticks. Given such a matrix, the problem of finding an optimal
 338 dissection <em>with that matrix</em> can be written as a linear
 339 programming problem. (One variable per dissection fragment is the
 340 obvious way, but then the objective function ‘take the minimum’ isn't
 341 linear. But if you add an extra variable showing the minimum size
 342 itself, and then make the other variables say by how much each other
 343 piece <em>exceeds</em> the minimum fragment, then it is linear.) So,
 344 in principle, we can just iterate over all the possible
 345 2<sup><i>nm</i></sup> adjacency matrices, and solve a linear
 346 programming problem for each one! Of course this takes exponential
 347 time, but it turns out reasonably practicable in small cases as long
 348 as you prune branches of the search tree early and often if you can
 349 easily show they can't give a result as good as the best one you
 350 already have.
 351 </p>
 352
 353 <p>
 354 <b>ILP over possible stick partitions</b>. A completely different
 355 approach is to enumerate the various ways in which a stick can be
 356 partitioned into smaller pieces. (There are infinitely many, of
 357 course, but if you pick a denominator <i>d</i> and constrain to
 358 multiples of 1/<i>d</i> then that's not too bad.) This approach
 359 requires us to make a guess at the minimum fragment, so that we can
 360 enumerate partitions which use pieces no smaller than that. Once we
 361 have a list of the partition types for the input and output sticks, we
 362 express them as vectors showing how many pieces of what lengths they
 363 use, and then solve an integer-linear-programming problem to find
 364 combinations of them for which all the piece counts add up. Again, ILP
 365 is a computationally hard problem, but this algorithm seems to work OK
 366 in small cases because if you start your minimum fragment <em>too
 367 big</em> and lower it until you get a solution, you never
 368 have <em>too</em> many possible partitions to worry about.
 369 </p>
 370
 371 <p>
 372 The first of these strategies is genuinely exhaustive: assuming no
 373 bugs in the search program, the algorithm must find the best possible
 374 dissection. The second, however, leaves open the possibility that a
 375 better dissection might exist using a denominator larger than any we
 376 had considered. Examination of the data we have so far strongly
 377 suggests the conjecture that no denominator larger than <i>n</i> is
 378 ever needed in an optimal dissection (though denominators larger
 379 than <i>m</i> can certainly occur), but we have no proof of that, and
 380 so results generated by the second search program cannot be considered
 381 reliable unless an upper bound proof confirms that they can't be
 382 beaten.
 383 </p>
 384
 385 <p>
 386 Disregarding that weakness of the ILP approach, the two search
 387 algorithms complement each other well, because once <i>n</i> gets a
 388 bit larger we find that the matrix iteration algorithm works best for
 389 small <i>m</i>, while the ILP approach works best for large <i>m</i>
 390 (i.e. not much smaller than <i>n</i>). So running both has allowed us
 391 to collect a reasonable amount of data.
 392 </p>
 393
 394 <p>
 395 FIXME: link to git repo.
 396 </p>
 397
 398 <h2>Table of known values</h2>
 399
 400 <p>
 401 The table below shows the best minimum fragment size for all
 402 the <i>n</i>,<i>m</i> pairs I currently know the answer to, and the
 403 best upper and lower bounds I have for a few values I don't know.
 404 </p>
 405
 406 <p>
 407 The table cells are colour-coded to indicate our confidence in each
 408 number. <span class="box known">Green</span> indicates that the
 409 correctness of the result depends only on our upper-bound
 410 proofs; <span class="box believed">greenish-yellow</span> indicates
 411 that the correctness depends on our exhaustive search program not
 412 having a bug in it; <span class="box probable">yellow</span> indicates
 413 that the correctness depends on our conjecture that denominators are
 414 no larger than <i>n</i> (and <em>also</em> on a search program not
 415 having a bug); <span class="box range">red</span> indicates that we
 416 actually don't know the value and have listed a range of possible
 417 answers.
 418 </p>
 419
 420 <p>
 421 Each table cell links to a section further down the page giving an
 422 explicit dissection and discussing which (if any) upper bound proofs
 423 apply in that case.
 424 </p>
 425
 426 <div>
 427 %TABLE%
 428 </div>
 429
 430 <h2>Observations from the data</h2>
 431
 432 <p>
 433 FIXME: clear patterns in the <i>m</i>=3 and <i>m</i>=4 columns, and
 434 the bounding proofs seem consistently tight there too, so those cases
 435 may be tractable to establish a complete proof for.
 436 </p>
 437
 438 <p>
 439 FIXME: the diagonal <i>n</i>=<i>m</i>+1 also looks nicely patterned.
 440 We don't have a reliably tight bound there, but it might be worth
 441 trying to prove that diagonal anyway, in the hope that we <em>can</em>
 442 discover another useful bounding proof!
 443 </p>
 444
 445 <p>
 446 FIXME: the patterns in columns 3 and 4 suggest to me the more
 447 ambitious conjecture that perhaps a similar pattern holds in every
 448 column if you look at cells spaced vertically by <i>m</i>, e.g. all
 449 the points with <i>m</i>=5 and <i>n</i>≡1 mod 5. I don't think we have
 450 enough data here to say anything with confidence about that idea,
 451 though.
 452 </p>
 453
 454 <p>
 455 FIXME: the case <i>n</i>=29,<i>m</i>=19 is especially intriguing for
 456 the heavy use of denominator 28 in a dissection with min fragment
 457 something/4.
 458 </p>
 459
 460 <h2>Credits</h2>
 461
 462 <p>
 463 FIXME: credit Ian, Tom, writinghawk, Jack for deAOCisation, anyone else?
 464 </p>
 465
 466 <h2>The individual dissections</h2>
 467
 468 <p>
 469 The output below is generated by a script from a collection of data
 470 files and simple on-the-fly algorithms, so that I can easily re-run it
 471 if and when I acquire more data. So it will look a bit stilted and
 472 formulaic; sorry about that.
 473 </p>
 474
 475 <div>
 476 %DISSECTIONS%
 477 </div>
 478
 479 </body>
 480 </html>