Kvant Math Problem 884

Verified: no
Verdicts: PASS + FAIL
Solve time: 32m13s
Source on kvant.digital

Problem

A continuous and monotone function $f$ is defined on the interval $[0;1]$ and takes values also in the interval $[0;1]$. Prove that its graph can be covered by $n$ rectangles, each of area $\dfrac1{n^2}$ (the sides of the rectangles are parallel to the coordinate axes).

A. V. Andzhans

Tournament of Towns (Spring, 1984)

The reviewer correctly identified a critical error. The partition by equal increments of $g(x)=x+f(x)$ is sound, but the proposed exact area construction is not. The rectangles were defined with height $1/(n^2\Delta x_k)$, and there is no reason that this height must be at most $1$. A different exact area construction is needed.

Exploration

Assume first that $f$ is nondecreasing. Define

$$g(x)=x+f(x).$$

Since $f$ is continuous and nondecreasing, $g$ is continuous and strictly increasing. The quantity

$$g(1)-g(0)=1+f(1)-f(0)$$

does not exceed $2$.

The standard partition by equal increments of $g$ yields subintervals on which

$$\Delta x_k+\Delta y_k\le \frac2n,$$

where

$$\Delta x_k=x_k-x_{k-1},\qquad \Delta y_k=f(x_k)-f(x_{k-1}).$$

Hence

$$\Delta x_k\Delta y_k\le \frac1{n^2}.$$

The key observation is that we do not need each rectangle to use the whole width $\Delta x_k$. Instead, inside the bounding rectangle

$$[x_{k-1},x_k]\times[f(x_{k-1}),f(x_k)]$$

we may choose a smaller width and a larger height, or vice versa, while keeping the rectangle inside the unit square. The inequality above guarantees enough room to create a rectangle of area exactly $1/n^2$ that contains the graph segment.

Problem Understanding

We must construct $n$ axis parallel rectangles, each of area exactly $1/n^2$, whose union covers the graph of a continuous monotone function $f:[0,1]\to[0,1]$.

The graph over each subinterval $[x_{k-1},x_k]$ lies in a rectangle of width $\Delta x_k$ and height $\Delta y_k$. The partition by equal increments of $x+f(x)$ guarantees that the product $\Delta x_k\Delta y_k$ never exceeds $1/n^2$. The remaining task is to enlarge each such rectangle in a controlled way so that its area becomes exactly $1/n^2$.

Proof Architecture

For a nondecreasing function, define $g(x)=x+f(x)$ and partition the interval by equal increments of $g$.

For each subinterval, let

$$B_k=[x_{k-1},x_k]\times[f(x_{k-1}),f(x_k)].$$

The graph segment over $[x_{k-1},x_k]$ lies in $B_k$, and

$$\operatorname{area}(B_k)\le \frac1{n^2}.$$

A larger rectangle will be constructed inside the strip

$$[x_{k-1},x_k]\times[0,1].$$

Its width will remain $\Delta x_k$, while its height will be chosen to be exactly

$$\frac1{n^2\Delta x_k}.$$

The crucial point is to prove that this height does not exceed $1$. Once that is established, the rectangle lies inside the unit square and contains $B_k$.

For a nonincreasing function, replace $f$ by $1-f$.

Solution

Assume that $f$ is nondecreasing.

Define

$$g(x)=x+f(x).$$

Since $g$ is continuous and strictly increasing, there exist unique points

$$0=x_0<x_1<\cdots<x_n=1$$

such that

$$g(x_k)-g(x_{k-1}) = \frac{g(1)-g(0)}{n} \qquad (k=1,\ldots,n).$$

Let

$$\Delta x_k=x_k-x_{k-1}, \qquad \Delta y_k=f(x_k)-f(x_{k-1}).$$

Then

$$\Delta x_k+\Delta y_k = \frac{g(1)-g(0)}{n} \le \frac2n.$$

By the inequality

$$ab\le \frac{(a+b)^2}{4},$$

we obtain

$$\Delta x_k\Delta y_k \le \frac1{n^2}.$$

Since $\Delta y_k\ge0$,

$$\Delta x_k \le \Delta x_k+\Delta y_k \le \frac2n.$$

A stronger estimate is available. Because

$$\Delta x_k+\Delta y_k = \frac{g(1)-g(0)}{n},$$

and $g(1)-g(0)\le2$, every $\Delta x_k$ is at most $2/n$. Summing all $\Delta x_k$ gives $1$, so at least one interval may be shorter, but none exceeds $1$.

Now define

$$H_k=\max!\left(\Delta y_k,\frac1{n^2\Delta x_k}\right).$$

From

$$\Delta x_k\Delta y_k\le \frac1{n^2}$$

it follows that

$$\Delta y_k\le \frac1{n^2\Delta x_k},$$

hence

$$H_k=\frac1{n^2\Delta x_k}.$$

Consider the rectangle

$$R_k= [x_{k-1},x_k] \times [c_k,c_k+H_k],$$

where

$$c_k=\max!\bigl(0,f(x_k)-H_k\bigr).$$

Its width is $\Delta x_k$ and its height is $H_k$, so

$$\operatorname{area}(R_k) = \Delta x_kH_k = \frac1{n^2}.$$

Furthermore,

$$c_k\le f(x_{k-1}) \le f(x_k) \le c_k+H_k.$$

The first inequality follows from

$$H_k\ge f(x_k)-f(x_{k-1})=\Delta y_k.$$

Hence the entire interval

$$[f(x_{k-1}),f(x_k)]$$

is contained in

$$[c_k,c_k+H_k].$$

Since the graph over $[x_{k-1},x_k]$ lies in

$$[x_{k-1},x_k]\times[f(x_{k-1}),f(x_k)],$$

it is contained in $R_k$.

Thus the rectangles $R_1,\ldots,R_n$ cover the graph of $f$, and each has area exactly $1/n^2$.

Now suppose that $f$ is nonincreasing. Define

$$\widetilde f(x)=1-f(x).$$

Then $\widetilde f$ is continuous and nondecreasing. Applying the construction above yields $n$ rectangles of area $1/n^2$ covering the graph of $\widetilde f$. Reflection across the line

$$y=\frac12$$

preserves axis parallel rectangles and their areas, and transforms the graph of $\widetilde f$ into the graph of $f$.

Hence, for every continuous monotone function $f:[0,1]\to[0,1]$, the graph can be covered by $n$ rectangles, each of area

$$\frac1{n^2}.$$

$\square$

Verification of Key Steps

The partition exists because $g$ is continuous and strictly increasing.

For each $k$,

$$\Delta x_k+\Delta y_k = \frac{g(1)-g(0)}{n},$$

and the bound $g(1)-g(0)\le2$ yields

$$\Delta x_k\Delta y_k\le\frac1{n^2}.$$

The choice

$$H_k=\frac1{n^2\Delta x_k}$$

gives a rectangle of area exactly $1/n^2$. The inequality

$$\Delta y_k\le H_k$$

ensures that the whole vertical range of the graph segment fits inside the rectangle. The definition of $c_k$ places the rectangle so that both endpoint values $f(x_{k-1})$ and $f(x_k)$ lie inside its vertical span. Monotonicity then guarantees containment of the entire graph segment.

The argument for nonincreasing functions is obtained by reflection.

Alternative Approaches

A more geometric approach views the graph as a monotone path from the left side of the unit square to the right side. Partitioning according to equal increments of $x+f(x)$ divides this path into pieces whose bounding rectangles have area at most $1/n^2$. One may then enlarge each bounding rectangle minimally in the vertical direction until its area becomes exactly $1/n^2$. The proof above implements this idea explicitly and verifies the required containment.