The plane has a dot at every point (x,y) where both x and y are integers.

geometry/lattice/ink.stains New

New entry, edited from material collected for the archive and not yet in a released version.

Problem

The plane has a dot at every point (x,y) where both x and y are
integers.  On it there is a group of ink stains (or a single stain)
whose total area is less than 1 unit area.  Prove that any such group
of stains may be moved in such a way that not a single dot of the
integer grid is covered by ink.

-- Amit Erez <amit@acri.fr>, October 1993

[ Editor: lightly reworded; the original begins "Given an infinitesimal
plan, with a dot on any (x,y) where both x and y are integer". ]

Show solution

Call this ink stain D.  Define D_ab=D intersect [a,a+1]x[b,b+1] for all
integers a and b.  E_ab is defined as D_ab translated over (-a,-b) and
E is defined as the union of all E_ab.  E is contained in [0,1]x[0,1]
and the area of E is at most the area of D, hence less than 1.  Choose
a point p in [0,1]x[0,1] which is not element of E.  Then -p is the
vector you have to translate D by.  QED

-- Mark van Hoeij <hoeij@sci.kun.nl> and Harm Derksen

Very true.  That's a valid solution, but a technical one.  I prefer a
more intuitive solution.  Following is a solution which was sent to me
by David Karr (karr@cs.cornell.edu):

-- Amit Erez <amit@acri.fr>

Map the ink stains onto the unit square [0,1)x[0,1) by taking the
fractional parts of the x-y coordinates of each point of each stain.
Stains that cross integer coordinate lines get mapped in pieces, but
that's OK.  If the resulting copies of the stains (or pieces of stain)
don't overlap, the area will be exactly the same as before; if they
overlap, it will be somewhat less.  In any case it is guaranteed less
than 1.  So some point (x0,y0) on the inside of the unit square is not
covered by any part of the stain.  Translate the entire plane
(including the original stain) so that the image of (x0,y0) is on the
origin.  Now the integer lattice points are just the images of the
points that had fractional parts x0 and y0 in their coordinates, so
none of them are covered by any part of the translated image of the
original stain.

-- David Karr <karr@cs.cornell.edu>