From 86575cc1251eca190aacac95dcb498d4efb4e7a2 Mon Sep 17 00:00:00 2001 From: Simon Tatham Date: Wed, 12 Mar 2014 20:46:11 +0000 Subject: [PATCH] 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. --- .gitignore | 1 + bounds.py | 143 +++++++++++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 144 insertions(+) create mode 100644 bounds.py diff --git a/.gitignore b/.gitignore index 1473b41..161945d 100644 --- 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 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 . + +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() -- 2.30.2