Track / Stage 6 / 367 of 400 #1367 of 1964

Problem 1367

National olympiad, first round

Combinatorics Difficulty 6.8 Find the answer

What is the maximal number of crosses than can fit in a $10\times 11$ board without overlapping?
Is this problem well-known?

Figure (Asymptote source)

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 */

Your answer

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Official solution

To determine the maximal number of crosses that can fit in a $10 \times 11$ board without overlapping, we need to analyze the structure and placement of crosses on the board.

1. Understanding the Cross Structure:
A cross occupies 5 unit squares in a plus shape:
$\begin{array}{ccc} & \square & \\ \square & \square & \square \\ & \square & \\ \end{array}$
This means each cross covers 5 unit squares.

2. Calculating the Total Number of Unit Squares:
The total number of unit squares in a $10 \times 11$ board is:
$10 \times 11 = 110$

3. Upper Bound on the Number of Crosses:
Since each cross covers 5 unit squares, the maximum number of crosses that can fit in the board is:
$\left\lfloor \frac{110}{5} \right\rfloor = 22$
However, this is an ideal upper bound and does not account for the actual arrangement and boundary conditions.

4. Boundary Conditions:
- Out of 4 consecutive boundary unit squares, only 2 can be covered by crosses.
- The board has 22 boundary unit squares on the side of length 11 and 18 boundary unit squares on the side of length 10.
- At least 12 boundary unit squares on the side of length 11 and 10 boundary unit squares on the side of length 10 cannot be covered by crosses.

5. Calculating the Number of Crosses:
- The number of boundary unit squares that cannot be covered is at least:
$12 + 10 = 22$
- The remaining unit squares that can be covered are:
$110 - 22 = 88$
- The number of crosses that can fit in these 88 unit squares is:
$\left\lceil \frac{88}{6} \right\rceil = 14.67 \approx 14$

6. Example Arrangement:
- Place crosses starting at points $(1,2), (1,4), (1,6), (1,8), (1,10)$ facing left and right alternately.
- Place symmetrical crosses on the other side.
- Place 4 crosses in the middle.

Thus, the maximal number of crosses that can fit in a $10 \times 11$ board without overlapping is 14.

The final answer is $\boxed{14}$

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.