Cover a 10X11 board by crosses
Source: Greece TST 2011
February 11, 2016
combinatorics
Problem Statement
What is the maximal number of crosses than can fit in a board without overlapping?
Is this problem well-known?
[asy]
size(4.58cm);
real labelscalefactor = 0.5; /* changes label-to-point distance */
pen dps = linewidth(0.7) + fontsize(10); defaultpen(dps); /* default pen style */
pen dotstyle = black; /* point style */
real xmin = -3.18, xmax = 1.4, ymin = -0.22, ymax = 3.38; /* image dimensions */ /* draw figures */
draw((-3.,2.)--(1.,2.));
draw((-2.,3.)--(-2.,0.));
draw((-2.,0.)--(-1.,0.));
draw((-1.,0.)--(-1.,3.));
draw((-1.,3.)--(-2.,3.));
draw((-3.,1.)--(1.,1.));
draw((1.,1.)--(1.,2.));
draw((-3.,2.)--(-3.,1.));
draw((0.,2.)--(0.,1.));
draw((-1.,2.)--(-1.,1.));
draw((-2.,2.)--(-2.,1.));
/* dots and labels */
clip((xmin,ymin)--(xmin,ymax)--(xmax,ymax)--(xmax,ymin)--cycle);
/* end of picture */
[/asy]