Python code to compute upper bounds on the solution.

Since I now know of two different ways to prove an upper bound, here's
a piece of code which tries both, picks the lowest, and explains which
one gave rise to the number it returns.

diff --git a/.gitignore b/.gitignore
index 1473b4190b4db474facf55bcd8ff7c2cbb44b7a2..161945da73e5a0f75867e25110a0c5e05dc1bcb8 100644 (file)
--- a/.gitignore
+++ b/.gitignore
@@ -7,3 +7,4 @@ core
 *.gcno
 *.gcov
 gmon.out
+*.pyc

diff --git a/bounds.py b/bounds.py
new file mode 100644 (file)
index 0000000..a26bb5e
--- /dev/null
+++ b/bounds.py
@@ -0,0 +1,143 @@
+# -*- coding: utf-8 -*-
+
+# Compute upper bounds on min fragment.
+
+import sys, fractions
+from fractions import Fraction
+
+def floor(q):
+    """Floor function that can cope with Fraction. Bah, why does the
+fractions module not contain one of these?"""
+    if q < 0: return -ceil(-q)
+    return int(q)
+def ceil(q):
+    """Ceiling function that can cope with Fraction. Also bah."""
+    if q < 0: return -floor(-q)
+    if q == int(q): return int(q)
+    return int(q) + 1
+
+def ceilpe(q):
+    """ceil(q+ε)"""
+    return floor(q) + 1
+def floorme(q):
+    """floor(q-ε)"""
+    return ceil(q) - 1
+
+def writinghawk(n,m):
+    """Upper bound on the best solution by <lj user="writinghawk">.
+
+We begin by ruling out the case where m | n, which is the only case in
+which we can avoid cutting _any_ m-stick. With that constraint, we
+know the min frag must be at most m/2, and we assume we will cut
+_every_ m-stick at least once.
+
+Now suppose the min frag is s, so that every piece is at least s and
+at most m-s. We derive constraints on s by considering the total
+number of pieces in the dissection.
+
+Each stick of length n is cut into at least n/(m-s) and at most n/s
+pieces. Because it must also have an integer number of pieces, that
+means it's at least ⌈n/(m-s)⌉ and at most ⌊n/s⌋. Summing over all
+n-sticks, the total number of pieces P in the dissection must satisfy
+m⌈n/(m-s)⌉ ≤ P ≤ m⌊n/s⌋.
+
+By similarly considering the number of pieces that a stick of length m
+is cut into, we derive a second inequality n⌈m/(m-s)⌉ ≤ P ≤ n⌊m/s⌋
+(identical to the first inequality, but with n,m are swapped
+everywhere they appear except in the divisor m-s).
+
+So when s becomes big enough that either of those inequalities is
+self-inconsistent (with LHS > RHS) or when the two are incompatible
+(because they define ranges for P that do not meet), there can be no
+dissection with s that large."""
+    if n % m == 0:
+        return m
+
+    s = 1
+    while True:
+        # See if s+ε is viable.
+
+        # lo_n = m * ⌈n/(m - s - ε)⌉
+        #      = m * ⌈n/(m - s) + ε'⌉
+        lo_n = m * ceilpe(Fraction(n, m - s))
+
+        # hi_n = m * ⌊n/(s + ε)⌋
+        #      = m * ⌊n/s - ε'⌋
+        hi_n = m * floorme(Fraction(n, s))
+
+        # lo_m = n * ⌈m/(m - s - ε)⌉
+        #      = n * ⌈m/(m - s) + ε'⌉
+        lo_m = n * ceilpe(Fraction(m, m - s))
+
+        # hi_m = n * ⌊m/(s + ε)⌋
+        #      = n * ⌊m/s - ε'⌋
+        hi_m = n * floorme(Fraction(m, s))
+
+        if max(lo_n, lo_m) > min(hi_n, hi_m):
+            return s
+
+        # Find the next point where one of those floors changes.
+        s_new = min(m - Fraction(n, ceilpe(Fraction(n, m - s))),
+                    Fraction(n, floorme(Fraction(n, s))),
+                    m - Fraction(m, ceilpe(Fraction(m, m - s))),
+                    Fraction(m, floorme(Fraction(m, s))))
+        s = s_new
+
+def fivemack(n, m):
+    """Upper bound on certain n,m pairs by Tom Womack.
+
+If m/3 is an integer and also a multiple of n-m, then no solution can
+be better than m/3.
+
+Proof: suppose the shortest fragment is m/3 + ε for some ε > 0. Then
+if any segment of stick less than _twice_ that length arises while
+you're dissecting, it must remain whole. In particular, any fragment
+shorter than 2m/3 + 2ε must be monolithic in this way.
+
+So consider a short stick (of length m) from which we cut a piece of
+length m/3+ε. The other piece of that stick has length 2m/3-ε and
+hence is monolithic; so it must have been cut as a whole from a longer
+stick of length n. Let n = m+k, because we'll want to talk about k a
+lot. Now we reason as follows:
+
+ - a piece m/3+ε shares a short stick with 2m/3-ε
+ - that 2m/3-ε shares a long stick with m/3+k+ε
+ - that m/3+k+ε shares a short stick with 2m/3-k-ε
+ - that 2m/3-k-ε shares a long stick with m/3+2k+ε
+
+... and so on, so that we derive the existence of pieces of lengths
+m/3+ε, m/3+k+ε, m/3+2k+ε, ... 2m/3+ε (which we must reach since m/3 is
+an exact multiple of k). That 2m/3+ε is still monolithic (recall that
+only a piece of at least 2m/3+2ε can avoid being so) and so it must
+share a short stick with a piece of length m/3-ε, which is shorter
+than our presumed minimum fragment. Contradiction."""
+    if m % (3*(n-m)) == 0:
+        return m/3
+    return None
+
+bounds = [
+    (writinghawk, "writinghawk's piece-counting bound"),
+    (fivemack, "fivemack's conditional m/3 bound"),
+]
+
+def upper_bound(n, m):
+    assert n > m
+    best = m, "trivial bound of m"
+    for boundtype in bounds:
+        b = boundtype[0](n, m)
+        if b is not None:
+            if b < m:
+                best = b, boundtype[1]
+            elif b == m:
+                best = b, best[1] + ", " + boundtype[1]
+    return best
+
+def main():
+    n = int(sys.argv[1])
+    m = int(sys.argv[2])
+    if n < m: m,n = n,m
+    b = upper_bound(n, m)
+    print "upper_bound(%d,%d) = %s (%s)" % (n, m, b[0], b[1])
+
+if __name__ == "__main__":
+    main()