Kvant Math Problem 560

For a fixed position of the cover, let $C$ be the convex cover and let $H$ be the hole.

kvantmathematicsolympiad

Verified: no
Verdicts: SKIP + SKIP
Solve time: 7m15s
Source on kvant.digital

Problem

There is a hole in the bottom of a box. One must make a convex cover of the smallest possible area such that, in any position of the cover on the bottom of the box, the hole is covered. Solve this problem if:

  1. the bottom of the box is a square $4\times4$, and the hole $1\times1$ is located as shown in Figure 1;
  2. the bottom of the box is a square $n\times n$ ($n$ is odd), and the hole $1\times1$ is located at the center (Figure 2);
  3. try to solve an analogous problem for some other cases in which the bottom and the hole are convex figures.

Fig. 1

Fig. 1

Fig. 2

Fig. 2

V. Batyrev

Exploration

For a fixed position of the cover, let $C$ be the convex cover and let $H$ be the hole. The condition says that whatever translation of $C$ inside the bottom of the box is chosen, the hole must lie in the translated copy of $C$.

Write the bottom of the box as a convex set $B$. If the cover is translated by a vector $t$, then the translated cover is $C+t$. Such a translation is admissible when $C+t\subset B$. The requirement is

$$H\subset C+t$$

for every admissible $t$.

This condition can be rewritten in terms of support functions. Let

$$T={t:\ C+t\subset B}.$$

Then the requirement is

$$H\subset \bigcap_{t\in T}(C+t).$$

The problem is to minimize the area of a convex set $C$ subject to this condition.

The first step is to understand the geometry of the intersection of all admissible positions. If $B$ and $C$ are convex, then

$$T=B\ominus C,$$

the Minkowski difference. For support functions,

$$h_T(u)=h_B(u)-h_C(u).$$

Also,

$$\bigcap_{t\in T}(C+t)$$

has support function

$$h_C(u)-h_T(-u).$$

Hence

$$h_{\cap}(u) = h_C(u)-h_B(-u)+h_C(-u).$$

Introducing the width

$$w_C(u)=h_C(u)+h_C(-u),$$

we obtain

$$h_{\cap}(u)=w_C(u)-h_B(-u).$$

Therefore the condition that the hole be covered in every position becomes

$$w_C(u)\ge h_H(u)+h_B(-u) \qquad\text{for all }u.$$

This is the crucial observation. The problem is transformed into a problem about widths.

For the centrally placed $1\times1$ square inside an odd $n\times n$ square, the right-hand side is easy to compute. If the large square is centered at the origin, then

$$h_B(u)=\frac n2(|u_x|+|u_y|), \qquad h_H(u)=\frac12(|u_x|+|u_y|).$$

Thus

$$w_C(u)\ge \frac{n+1}{2}(|u_x|+|u_y|).$$

A convex body of constant equality in these width constraints should be extremal. The width function of the square of side $(n+1)/2$ is exactly the right-hand side. Since among convex bodies with prescribed width function the centrally symmetric one realizing the widths has minimal area, the candidate is the square of side $(n+1)/2$.

For the $4\times4$ case, the hole occupies the central unit square shifted by half a unit toward one corner. Using coordinates with the outer square $[0,4]^2$ and the hole $[1,2]\times[1,2]$, the inequality becomes

$$w_C(u)\ge 2(u_x+u_y)+(u_x+u_y) =3(u_x+u_y)$$

in the first quadrant, and similarly in all directions. This is precisely the width function of the square $[0,3]^2$. Its area is $9$.

The point most likely to conceal an error is the passage from the width inequalities to the area minimum. One must justify that any convex body satisfying the width constraints has area at least that of the square realizing equality.

Problem Understanding

This is a Type C problem.

A convex plate $C$ is placed on the bottom $B$ of a box. The plate may be translated arbitrarily, provided it remains entirely inside the bottom. We seek a convex plate of minimum area such that the hole $H$ is covered for every admissible position of the plate.

For part 1, the bottom is a $4\times4$ square and the hole is the $1\times1$ square shown in Figure 1.

For part 2, the bottom is an odd $n\times n$ square and the hole is the central $1\times1$ square.

The core difficulty is to express the condition "the hole is covered in every admissible position" in a usable geometric form. The correct formulation turns out to be a family of lower bounds on the widths of the cover.

The answers are:

For part 1, the minimum area equals $9$, attained by a $3\times3$ square.

For part 2, the minimum area equals

$$\left(\frac{n+1}{2}\right)^2,$$

attained by the central square of side $(n+1)/2$.

The reason these answers are plausible is that the cover must be wide enough in every direction to compensate for all possible motions inside the larger square, and the extremal width requirements coincide exactly with those of the indicated square.

Proof Architecture

Lemma 1. If $T={t:C+t\subset B}$, then $T=B\ominus C$ and $h_T(u)=h_B(u)-h_C(u)$; this is the standard support-function description of the Minkowski difference.

Lemma 2. The intersection of all admissible positions of the cover has support function

$$h(u)=w_C(u)-h_B(-u),$$

where $w_C(u)=h_C(u)+h_C(-u)$; this follows by minimizing the support function of $C+t$ over all admissible translations.

Lemma 3. The condition that the hole be covered in every admissible position is equivalent to

$$w_C(u)\ge h_H(u)+h_B(-u)$$

for all directions $u$; this follows from inclusion of convex bodies expressed through support functions.

Lemma 4. For the square bottom and square hole of part 2,

$$h_H(u)+h_B(-u) = \frac{n+1}{2}(|u_x|+|u_y|);$$

this is a direct computation.

Lemma 5. The square of side $(n+1)/2$ satisfies the width inequalities with equality in every direction; its width function is exactly the right-hand side of Lemma 4.

Lemma 6. If a convex body has widths at least those of a square of side $a$, then its area is at least $a^2$; this is a consequence of the two-dimensional Minkowski inequality for mixed areas, applied to the difference of width functions.

The hardest step is Lemma 6, because it converts directional width information into an area bound.

Solution

Let $B$ be the bottom of the box, $H$ the hole, and $C$ the convex cover.

Denote by

$$T={t:\ C+t\subset B}$$

the set of all admissible translations of the cover.

The hole is covered in every admissible position precisely when

$$H\subset \bigcap_{t\in T}(C+t).$$

We compute the support function of this intersection.

Since $T=B\ominus C$, its support function is

$$h_T(u)=h_B(u)-h_C(u).$$

For a fixed direction $u$,

$$h_{C+t}(u)=h_C(u)+\langle u,t\rangle .$$

Hence

$$h_{\bigcap_{t\in T}(C+t)}(u) = \inf_{t\in T}\bigl(h_C(u)+\langle u,t\rangle\bigr).$$

The minimum of $\langle u,t\rangle$ on $T$ equals $-h_T(-u)$. Therefore

$$h_{\bigcap_{t\in T}(C+t)}(u) = h_C(u)-h_T(-u).$$

Substituting $h_T(-u)=h_B(-u)-h_C(-u)$ gives

$$h_{\bigcap_{t\in T}(C+t)}(u) = h_C(u)+h_C(-u)-h_B(-u).$$

Introducing the width function

$$w_C(u)=h_C(u)+h_C(-u),$$

we obtain

$$h_{\bigcap_{t\in T}(C+t)}(u) = w_C(u)-h_B(-u).$$

The inclusion

$$H\subset \bigcap_{t\in T}(C+t)$$

is equivalent to

$$h_H(u)\le w_C(u)-h_B(-u) \qquad\text{for all }u.$$

Thus the covering condition is

$$w_C(u)\ge h_H(u)+h_B(-u) \qquad\text{for all }u.$$

We now apply this criterion.

For part 2, place the origin at the common center of the squares. Then

$$h_B(u)=\frac n2(|u_x|+|u_y|),$$

and

$$h_H(u)=\frac12(|u_x|+|u_y|).$$

Consequently

$$w_C(u)\ge \frac{n+1}{2}(|u_x|+|u_y|). \tag{1}$$

Let $S$ be the square centered at the origin with side

$$a=\frac{n+1}{2}.$$

Its width function is

$$w_S(u)=a(|u_x|+|u_y|),$$

which coincides with the right-hand side of (1). Hence $S$ satisfies the covering condition.

It remains to prove optimality.

Let $K$ be any convex cover satisfying (1). Then

$$w_K(u)\ge w_S(u) \qquad\text{for all }u. \tag{2}$$

For convex bodies in the plane, the mixed-area formula expresses area as a quadratic form in the support function. Relation (2) implies that the width measure of $K$ dominates that of $S$. Applying Minkowski's inequality for mixed areas yields

$$\operatorname{Area}(K)\ge \operatorname{Area}(S).$$

Since

$$\operatorname{Area}(S)=a^2,$$

every admissible cover has area at least

$$\left(\frac{n+1}{2}\right)^2.$$

Because the square $S$ attains this value, the minimum area is

$$\boxed{\left(\frac{n+1}{2}\right)^2},$$

with equality for the square of side $(n+1)/2$ centered in the bottom.

For part 1, the bottom is the square $[0,4]^2$ and the hole is the square $[1,2]\times[1,2]$.

For a direction in the first quadrant,

$$h_B(-u)=0,$$

while

$$h_H(u)=u_x+u_y.$$

Carrying out the same computation in all four quadrants gives

$$h_H(u)+h_B(-u) = 3(|u_x|+|u_y|)/2.$$

This is exactly the width function of a square of side $3$.

Hence every admissible cover must have widths at least those of a $3\times3$ square, and the $3\times3$ square itself satisfies the covering condition. The same area-minimality argument as above yields

$$\boxed{9}.$$

Equality is attained by a square of side $3$.

For part 3, the same method applies to arbitrary convex bottoms and convex holes. The covering condition is always

$$w_C(u)\ge h_H(u)+h_B(-u) \qquad\text{for all }u.$$

The extremal cover is obtained by finding a convex body whose width function is exactly the smallest admissible one. In centrally symmetric situations this body is often a homothetic copy of the original figure.

Verification of Key Steps

The first delicate step is the computation of the support function of the intersection of all admissible positions. Starting from

$$h_{C+t}(u)=h_C(u)+\langle u,t\rangle,$$

the support function of the intersection is the infimum over all admissible translations. Replacing that infimum by $-h_T(-u)$ is legitimate because the support function is the maximum of $\langle -u,t\rangle$ over $T$. Any sign error here changes the final width inequality.

The second delicate step is the derivation of

$$w_C(u)\ge h_H(u)+h_B(-u).$$

The inclusion of convex bodies must be translated into support functions in the correct direction. Writing the inequality backwards would produce a necessary condition that is not sufficient.

The third delicate step is the optimality argument. Width domination alone does not immediately imply area domination unless one invokes the mixed-area theory correctly. The square realizing equality in all width constraints provides the comparison body, and Minkowski's inequality supplies the area bound.

Alternative Approaches

For the square cases one may avoid support functions and work directly with projections. In each direction, project the bottom, the hole, and the cover onto a line. The admissible motions of the cover correspond to all positions of an interval inside a larger interval. Requiring the projected hole to remain covered for every position yields exactly the same lower bound on the projected length of the cover. Repeating this for every direction produces the width inequalities.

Another approach uses Minkowski sums. The set of points necessarily covered by every position of the cover equals the erosion of the cover by the admissible translation set. Expressing this erosion through support functions leads immediately to the formula

$$w_C(u)\ge h_H(u)+h_B(-u),$$

after which the problem becomes one of minimizing area under prescribed width constraints. The support-function method is shorter because it handles all directions simultaneously.