bounds.py

   1 # -*- coding: utf-8 -*-
   2
   3 # Compute upper bounds on min fragment.
   4
   5 import sys, fractions
   6 from fractions import Fraction
   7
   8 def floor(q):
   9     """Floor function that can cope with Fraction. Bah, why does the
  10 fractions module not contain one of these?"""
  11     if q < 0: return -ceil(-q)
  12     return int(q)
  13 def ceil(q):
  14     """Ceiling function that can cope with Fraction. Also bah."""
  15     if q < 0: return -floor(-q)
  16     if q == int(q): return int(q)
  17     return int(q) + 1
  18
  19 def ceilpe(q):
  20     """ceil(q+ε)"""
  21     return floor(q) + 1
  22 def floorme(q):
  23     """floor(q-ε)"""
  24     return ceil(q) - 1
  25
  26 def writinghawk(n,m):
  27     """Upper bound on the best solution by <lj user="writinghawk">.
  28
  29 We begin by ruling out the case where m | n, which is the only case in
  30 which we can avoid cutting _any_ m-stick. With that constraint, we
  31 know the min frag must be at most m/2, and we assume we will cut
  32 _every_ m-stick at least once.
  33
  34 Now suppose the min frag is s, so that every piece is at least s and
  35 at most m-s. We derive constraints on s by considering the total
  36 number of pieces in the dissection.
  37
  38 Each stick of length n is cut into at least n/(m-s) and at most n/s
  39 pieces. Because it must also have an integer number of pieces, that
  40 means it's at least ⌈n/(m-s)⌉ and at most ⌊n/s⌋. Summing over all
  41 n-sticks, the total number of pieces P in the dissection must satisfy
  42 m⌈n/(m-s)⌉ ≤ P ≤ m⌊n/s⌋.
  43
  44 By similarly considering the number of pieces that a stick of length m
  45 is cut into, we derive a second inequality n⌈m/(m-s)⌉ ≤ P ≤ n⌊m/s⌋
  46 (identical to the first inequality, but with n,m are swapped
  47 everywhere they appear except in the divisor m-s).
  48
  49 So when s becomes big enough that either of those inequalities is
  50 self-inconsistent (with LHS > RHS) or when the two are incompatible
  51 (because they define ranges for P that do not meet), there can be no
  52 dissection with s that large."""
  53     if n % m == 0:
  54         return m
  55
  56     s = 1
  57     while True:
  58         # See if s+ε is viable.
  59
  60         # lo_n = m * ⌈n/(m - s - ε)⌉
  61         #      = m * ⌈n/(m - s) + ε'⌉
  62         lo_n = m * ceilpe(Fraction(n, m - s))
  63
  64         # hi_n = m * ⌊n/(s + ε)⌋
  65         #      = m * ⌊n/s - ε'⌋
  66         hi_n = m * floorme(Fraction(n, s))
  67
  68         # lo_m = n * ⌈m/(m - s - ε)⌉
  69         #      = n * ⌈m/(m - s) + ε'⌉
  70         lo_m = n * ceilpe(Fraction(m, m - s))
  71
  72         # hi_m = n * ⌊m/(s + ε)⌋
  73         #      = n * ⌊m/s - ε'⌋
  74         hi_m = n * floorme(Fraction(m, s))
  75
  76         if max(lo_n, lo_m) > min(hi_n, hi_m):
  77             return s
  78
  79         # Find the next point where one of those floors changes.
  80         s_new = min(m - Fraction(n, ceilpe(Fraction(n, m - s))),
  81                     Fraction(n, floorme(Fraction(n, s))),
  82                     m - Fraction(m, ceilpe(Fraction(m, m - s))),
  83                     Fraction(m, floorme(Fraction(m, s))))
  84         s = s_new
  85
  86 def fivemack(n, m):
  87     """Upper bound on certain n,m pairs by Tom Womack.
  88
  89 If m/3 is an integer and also a multiple of n-m, then no solution can
  90 be better than m/3.
  91
  92 Proof: suppose the shortest fragment is m/3 + ε for some ε > 0. Then
  93 if any segment of stick less than _twice_ that length arises while
  94 you're dissecting, it must remain whole. In particular, any fragment
  95 shorter than 2m/3 + 2ε must be monolithic in this way.
  96
  97 So consider a short stick (of length m) from which we cut a piece of
  98 length m/3+ε. The other piece of that stick has length 2m/3-ε and
  99 hence is monolithic; so it must have been cut as a whole from a longer
 100 stick of length n. Let n = m+k, because we'll want to talk about k a
 101 lot. Now we reason as follows:
 102
 103  - a piece m/3+ε shares a short stick with 2m/3-ε
 104  - that 2m/3-ε shares a long stick with m/3+k+ε
 105  - that m/3+k+ε shares a short stick with 2m/3-k-ε
 106  - that 2m/3-k-ε shares a long stick with m/3+2k+ε
 107
 108 ... and so on, so that we derive the existence of pieces of lengths
 109 m/3+ε, m/3+k+ε, m/3+2k+ε, ... 2m/3+ε (which we must reach since m/3 is
 110 an exact multiple of k). That 2m/3+ε is still monolithic (recall that
 111 only a piece of at least 2m/3+2ε can avoid being so) and so it must
 112 share a short stick with a piece of length m/3-ε, which is shorter
 113 than our presumed minimum fragment. Contradiction."""
 114     if m % (3*(n-m)) == 0:
 115         return m/3
 116     return None
 117
 118 def most_trivial(n, m):
 119     """The most trivial possible bound."""
 120     return m
 121
 122 def trivial(n, m):
 123     """Trivial upper bound of m/2.
 124
 125 If m does not divide n, then at least one m-stick must be cut into
 126 more than one piece, reducing the best option to at most m/2."""
 127     if n % m == 0:
 128         return None
 129     return Fraction(m, 2)
 130
 131 bounds = [
 132     (writinghawk, "writinghawk's piece-counting bound"),
 133     (fivemack, "fivemack's conditional m/3 bound"),
 134     (trivial, "trivial bound of m/2"),
 135     (most_trivial, "trivial bound of m"),
 136 ]
 137
 138 def upper_bound(n, m):
 139     assert n > m
 140     best = m+1, None
 141     for boundtype in bounds:
 142         b = boundtype[0](n, m)
 143         if b is not None:
 144             if b < best[0]:
 145                 best = b, boundtype[1]
 146             elif b == best[0]:
 147                 best = b, best[1] + ", " + boundtype[1]
 148     return best
 149
 150 def main():
 151     n = int(sys.argv[1])
 152     m = int(sys.argv[2])
 153     if n < m: m,n = n,m
 154     b = upper_bound(n, m)
 155     print "upper_bound(%d,%d) = %s (%s)" % (n, m, b[0], b[1])
 156
 157 if __name__ == "__main__":
 158     main()