.range {
background-color: #ff8888;
}
+sub {
+ vertical-align: -0.3em;
+ font-size: 70%;
+ line-height: 0;
+}
</style>
</head>
<body>
uninteresting that we may as well ignore it.)
</p>
+<h3>No irrationals</h3>
+
+<p>
+We've established that the minimum fragment size need not be an
+integer, so an obvious next question is, need it even
+be <em>rational</em>?
+</p>
+
+<p>
+The answer is yes, and we can prove it as follows. Consider an
+arbitrary dissection of <i>m</i> sticks into <i>n</i> containing at
+least one irrational fragment length. The lengths of all the fragments
+generate a finite-dimensional vector space over ℚ; let
+{ <i>e</i><sub>1</sub>, …, <i>e</i><sub><i>k</i></sub> }
+be a basis for that space in which <i>e</i><sub>1</sub> is rational.
+Then the shortest irrational fragment length must have a nonzero
+coefficient of some basis element other than <i>e</i><sub>1</sub>,
+say <i>e</i><sub><i>i</i></sub>.
+</p>
+
+<p>
+Now we construct a new dissection based on the old one, in which we
+adjust every fragment length by adding <i>ε</i> times its original
+value's coefficient of <i>e</i><sub><i>i</i></sub>, for some
+constant <i>ε</i>. Doing this must preserve the property that the
+fragments making up each input and output stick sum to the right total
+length (proof: the original <i>e</i><sub><i>i</i></sub> coefficients
+must have summed to zero in order to generate an integer stick length
+previously, so adding a constant multiple of all
+those <i>e</i><sub><i>i</i></sub> coefficients doesn't change the
+overall sum). So now we choose |<i>ε</i>| small enough that no two
+original fragment lengths change their ordering and no fragment length
+becomes negative or more than the entire stick size. (We can do this,
+since those constraints give us finitely many upper bounds all of
+which are strictly positive, so we can certainly find an <i>ε</i>
+smaller than all of them and still nonzero. The only interesting case
+is when a fragment was the whole of its stick – in which case it has a
+zero coefficient of <i>e</i><sub><i>i</i></sub> anyway, so we aren't
+changing it at all and no bound is placed on <i>ε</i> by the
+requirement for it not to overflow.) Finally, we choose the sign
+of <i>ε</i> so that it lengthens rather than shortening the smallest
+irrational fragment.
+</p>
+
+<p>
+So now we've constructed a new dissection of basically the same shape
+as the old one, in which every fragment length is adjusted by at most
+a small amount, with the properties that:
+<ul>
+<li>
+ordering of lengths is preserved (if one fragment was shorter than
+another in the old dissection then it is in the new dissection too)
+<li>
+in particular, equal fragment lengths remain equal (because they had
+the same <i>e</i><sub><i>i</i></sub> coefficient so we adjusted them
+by the same amount)
+<li>
+rational fragment lengths are unchanged from the original dissection
+(they had a zero <i>e</i><sub><i>i</i></sub> coefficient)
+<li>
+what was previously the shortest irrational fragment length is now
+slightly longer.
+</ul>
+This means that no dissection with the shortest fragment irrational
+can be optimal, since the above construction would improve it.
+</p>
+
+<p>
+Also, if we were to strengthen our optimisation criterion by imposing
+a tie-breaking condition in which dissections with the same shortest
+fragment were compared by looking at the <em>next</em> shortest
+fragment and so on, then any dissection optimal under that stronger
+condition would have to have <em>every</em> fragment length rational
+(because, again, we could always lengthen the shortest irrational one,
+without changing any of the rational fragment lengths shorter than
+it). This implies that not only must the minimum fragment size always
+be rational, but also there must always be an all-rational dissection
+which attains it. So we can rule irrationals completely out of
+consideration, which is a relief!
+</p>
+
+<h3>Upper bounds</h3>
+
+<p>
+A problem with searching for dissections is, once you've found one,
+how do you prove there isn't a completely different one that does
+better?
+</p>
+
+<p>
+One way to solve that problem is to find a genuinely exhaustive search
+strategy, one of which is described in the next section. But
+exhaustive searches are expensive, so it would be nice to have some
+other tools in our toolbox as well, such as strategies for proving
+that no solution for a given <i>n</i>,<i>m</i> can be better than a
+given value. Then, if you can find an upper bound proof <em>and</em> a
+dissection attaining that bound, you know you don't have to look any
+further.
+</p>
+
+<p>
+One such upper bound proof, largely due
+to <a href="http://writinghawk.livejournal.com/profile">writinghawk</a>,
+works by counting the pieces in the dissection. For this proof, we
+start by assuming that every length-<i>m</i> stick (i.e. every shorter
+stick) is cut into at least two pieces; this doesn't lose generality,
+because if any stick remains whole in a dissection, we can just cut it
+in half and put both the pieces into the same <i>n</i>-stick. (And
+this does not decrease the minimum fragment length
+unless <em>all</em> <i>m</i>-sticks were whole, i.e. <i>m</i>
+divides <i>n</i>, which is a special case with such an obvious answer
+that we don't need this proof anyway.)
+</p>
+
+<p>
+So, let's suppose that every piece is at least length <i>s</i>. Also,
+every piece must be at <em>most</em>
+length <i>m</i> − <i>s</i> (because it must have been part
+of some <i>m</i>-stick, which had a piece of at least <i>s</i> cut off
+it).
+</p>
+
+<p>
+That means that each stick of length <i>n</i> has to be cut into at
+least <i>n</i>/(<i>m</i>−<i>s</i>) and at most <i>n</i>/<i>s</i>
+pieces (otherwise some piece would have to be too long or too short).
+Because the number of pieces also has to be an integer, that really
+means it's at least ⌈<i>n</i>/(<i>m</i>−<i>s</i>)⌉ and at most
+⌊<i>n</i>/<i>s</i>⌋. Summing those expressions over
+all <i>n</i>-sticks tells us that the total number of pieces <i>P</i>
+in the whole dissection must satisfy the
+inequality <i>m</i>⌈<i>n</i>/(<i>m</i>−<i>s</i>)⌉ ≤ <i>P</i> ≤ <i>m</i>⌊<i>n</i>/<i>s</i>⌋.
+</p>
+
+<p>
+By similarly considering the number of pieces that a stick of
+length <i>m</i> is cut into, we derive a second
+inequality <i>n</i>⌈<i>m</i>/(<i>m</i>−<i>s</i>)⌉ ≤ <i>P</i> ≤ <i>n</i>⌊<i>m</i>/<i>s</i>⌋.
+(This is identical to the first inequality, but with <i>n</i>
+and <i>m</i> swapped everywhere they appear except in the
+divisor <i>m</i>−<i>s</i>).
+</p>
+
+<p>
+So when <i>s</i> becomes big enough that either of those inequalities
+is self-inconsistent (with its LHS strictly larger than its RHS), or
+when the two are incompatible (because they define ranges for <i>P</i>
+that do not meet), there can be no dissection with <i>s</i> that
+large. This allows us to establish an upper bound on <i>s</i> for a
+given instance of the problem, which is often (but, results below
+indicate, not always) actually achievable.
+</p>
+
<p>
-FIXME: min frag is rational.
+A second upper-bound proof, due to Tom Womack, applies in a restricted
+set of cases, some of which are not solved optimally by the above
+proof. Specifically: if <i>m</i>/3 is an integer and is also a
+multiple of <i>n</i>−<i>m</i>, then no solution can be better
+than <i>m</i>/3.
</p>
<p>
-FIXME: empirical observation suggests conjecture that denominator is
-bounded by <i>n</i>, but no proof of this.
+Proof: suppose the shortest fragment is <i>m</i>/3 + <i>ε</i> for
+some <i>ε</i> > 0. Then if any segment of stick less
+than <em>twice</em> that length arises while you're dissecting, it
+must remain whole. In particular, any fragment shorter than
+2<i>m</i>/3 + 2<i>ε</i> must be monolithic in this way.
</p>
<p>
-FIXME: state the known upper bound proofs.
+So consider a stick of length m from which we cut a piece of
+length <i>m</i>/3+<i>ε</i>. The other piece of that stick has length 2<i>m</i>/3−<i>ε</i> and
+hence is monolithic; so it must have been cut as a whole from a longer
+stick of length <i>n</i>. Let <i>n</i> = <i>m</i>+<i>k</i>, because we'll want to talk about <i>k</i> a
+lot. Now we reason as follows:
+<ul>
+<li>
+a piece <i>m</i>/3+<i>ε</i> shares a short stick with
+2<i>m</i>/3−<i>ε</i>
+<li>
+that 2<i>m</i>/3−<i>ε</i> shares a long stick
+with <i>m</i>/3+<i>k</i>+<i>ε</i>
+<li>
+that <i>m</i>/3+<i>k</i>+<i>ε</i> shares a short stick with
+2<i>m</i>/3−<i>k</i>−<i>ε</i>
+<li>
+that 2<i>m</i>/3−<i>k</i>−<i>ε</i> shares a long stick
+with <i>m</i>/3+2<i>k</i>+<i>ε</i>
+</ul>
+... and so on, so that we derive the existence of pieces of lengths
+<i>m</i>/3+<i>ε</i>, <i>m</i>/3+<i>k</i>+<i>ε</i>,
+<i>m</i>/3+2<i>k</i>+<i>ε</i>, …, 2<i>m</i>/3+<i>ε</i> (which we must
+reach since <i>m</i>/3 is an exact multiple of k). That
+2<i>m</i>/3+<i>ε</i> is still monolithic (recall that only a piece of
+at least 2<i>m</i>/3+2<i>ε</i> can avoid being so) and so it must
+share a short stick with a piece of length <i>m</i>/3−<i>ε</i>, which
+is shorter than our presumed minimum fragment. This is a
+contradiction, and hence we reject the initial assumption that a
+minimum fragment greater than
+<i>m</i>/3 was possible in the first place.
</p>
<h2>Computer search</h2>
</p>
<p>
-FIXME: stress that one is exhaustive but the other depends on the
+FIXME: stress that one is exhaustive but the other depends on a
conjectured denominator bound.
</p>
~ianmdlvl / matchsticks-search.git / commitdiff