#####
Séminaire Lotharingien de Combinatoire, B15b (1986), 1
p.

[Formerly: Publ. I.R.M.A. Strasbourg, 1987, 340/S-15, p.
129.]

# Walter Kern, Alfred Wanka

# On a Problem about Covering Lines by Squares

**Abstract.**
Let *S* be the square [0,*n*]x[0,*n*] of side length *n* and let
*T*={*S*(1),...,*S*(*t*)} be a set of unit squares lying inside *S*, whose sides
are parallel to those of *S*. The set *T* is called a line cover, if
every line intersecting *S* also intersects some *S* in *T*.
Let *t*(*n*) denote the minimum cardinality of a line cover, and let
*t*'(*n*) be defined in the same way, except that we restrict our
attention to lines which are parallel to either one of the axes
or one of the diagonals of *S*. It has been conjectured by Toth
that *t*(*n*)=2*n*+0(1) and Baranyi and Füredi that
*t*(*n*)=(3/2)*n*+0(1). We will prove instead, *t*'(*n*)=(4/3)+0(1), and as
to Toth's conjecture, we will exhibit a ``non integer" solution to a
related LP-relaxation, which has size equal to (3/2)+0(1).

The following versions are available: