IBM Research | Ponder This | November 2001 solutions
Skip to main content

November 2001

<<October November December>>


1) 1 (or, 1-epsilon; as close to 1 as desired).
Pick a large integer N.
Let your slice of bread consist of N discs of unit diameter, randomly spaced in a square of side N**5 (that's N to the fifth power), and connected by extremely narrow ridges.
Compute the N(N-1)/2 distances between centers of the discs. Each distance is some random variable between 1 and about N**5.
It is highly unlikely (probability about 1/N) that any two of these distances are within 1 of each other; or that any three of the discs are "close" to being collinear. If the unlikely event occurs, then choose another loaf of bread.
Now match up a slice with its mirror image. At best you can get two pairs of discs to line up, which can happen in one of two ways:

  • disc B can line up with its own image B', and disc C with its own image C';
  • or B can line up with C', and C can line up with B'.

    For a third disc to line up, one of the "unlikely" events would have had to happen. So the maximum overlap is 2/N, and the asymmetry is 1-2/N = 1-epsilon.

    2) Unknown.
    An upper bound is 1/2, as follows:
    Pick a longest line BC contained within your convex shape S, and line up BC with its reversal C'B'. We'll consider the part of S above the line BC; the part below will
    follow similarly.
    Think of B as being on the left and C on the right.
    Let D be the midpoint of BC, and let E be the highest point of S such that ED is perpendicular to BC.
    Let F be on line BE such that CF is perpendicular to BC.
    Let the length of BC be x, and the length of DE be y.
    The overlap contains the triangle BEC, with area xy/2.
    The part of S to the right of DE has area at most 3xy/4, since it is confined within the trapezoid DEFC.
    (If any part of S lay to the right of CD, there would be a longer line segment contained in S.)
    So the overlap (above the line BC) has area at least xy/2, and the nonoverlap (S-S') (above the line) has area at most xy/2.

    By sliding S with respect to S' along the line BC (as in the argument for the triangle, below), one might prove a better upper bound, maybe 1/3. This is left as a challenge to the reader.

    A lower bound is the same as for the triangle (below): we think, 0.172.


    3) An upper bound is 3-sqrt(8)=0.172.
    Let the triangle S have sides of length X,Y,Z, with Y<X<Z.
    If Z/X<sqrt(2), line up the triangle with its image so that the side Z hits the image X', and X hits Z'; the angle between Z and X is just flipped.
    The bisector of that angle divides the triangle into two pieces whose areas are in the ratio X:Z, by the law of sines.
    The area of the overlap, divided by the area of the whole triangle, is then (X+X)/(Z+X), and the asymmetry is no more than (Z-X)/(Z+X).
    Since Z/X<sqrt(2), this asymmetry is bounded by 3-sqrt(8).

    Otherwise X/Z<sqrt(1/2). Let x and y denote the projections of X and Y onto side Z, respectively, so that x+y=Z, and x/Z<X/Z<sqrt(1/2).
    Line up side Z along its reversal Z', and slide S with respect to its mirror image S' so as to maximize the overlap.
    Claim: at that maximum, the following condition is satisfied:
        the height 2H of the overlap at the center of symmetry, is twice
        the height H of the intersection of side X with Y', or Y with X'.
    (If you continue sliding, you're gaining one infinitesimal slice of height 2H and losing two of height H each, so the derivative is 0.)

    Letting W be the horizontal distance between these two points, we get that
        (x+y-3W)/y=W/x, or W=x(x+y)/(3x+y).
    Let T denote the height of the original triangle (the distance from Z to its opposite vertex). So the area of S is ZT/2.
    The overlapping area is a pentagon, whose area we compute as
        (x+y)H=(x+y)(TW/x).

    The ratio (overlap/total area) is
        (2x+2y)/(3x+y),

    and (nonoverlap/total area) is
        (x-y)/(3x+y)=(2x-Z)/(2x+Z).

    Since x/Z<sqrt(1/2), this is again upper bounded by 3-sqrt(8).

    Given a long skinny triangle S, whose sides (X,Y,Z) have ratios (X:Y:Z) very close to (1:(sqrt(2)-1):sqrt(2)), we're pretty sure that 3-sqrt(8) is the actual asymmetry of S, and thus the worst case for triangles.


    If you have any problems you think we might enjoy, please send them in. All replies should be sent to: ponder@il.ibm.com

  •