Kvant Math Problem 321

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

Problem

There is a rectangular table of area 1. Prove that for any $\eps\gt0$ one can specify a system of rectangular napkins covering this table (the edges of the napkins are parallel to the edges of the table) such that any subsystem consisting of pairwise non-overlapping napkins has total area less than $\eps$.

A. V. Brailov

Exploration

The table may be taken to be the unit square $[0,1]\times[0,1]$.

The requirement concerns independent sets in the intersection graph of the napkins. Every pairwise non-overlapping subsystem is an independent set, and we want the total area of every independent set to be less than $\varepsilon$.

A natural way to force this is to arrange the napkins in layers. If every napkin from one layer intersects every napkin from another layer, then any pairwise disjoint subsystem can contain napkins from at most one layer. Hence the total area of a disjoint subsystem is bounded by the total area of the layer from which its members come.

Consider first a family of vertical strips covering the square. Any two distinct strips are disjoint, so this alone does not help. Add a second family of horizontal strips. Every vertical strip intersects every horizontal strip. Then a pairwise disjoint subsystem must consist entirely of vertical strips or entirely of horizontal strips. If the total area of each family is small, we are done.

The difficulty is that each family must still cover the whole square. A family of disjoint vertical strips covering the square has total area $1$, not small.

The way out is to allow heavy overlap inside a family. Let the vertical family consist of many copies of strips whose widths sum to $1$. Then the family covers the square, and its total area equals the sum of the widths. By choosing widths with sum $\delta$, we obtain total area $\delta$. This is impossible if the strips are disjoint, but possible if they overlap heavily.

Take vertical strips of widths $w_1,\dots,w_n$ whose union in the $x$ direction is $[0,1]$ while $\sum w_i$ is arbitrarily small. This can be done by covering $[0,1]$ with many overlapping intervals. For example, divide $[0,1]$ into $N$ equal subintervals and let each vertical strip have width $2/N$, centered at a division point. Then the union covers $[0,1]$, while the total width is about $2$; not small. We need the total width small.

A better idea is to use many levels. Let $k$ families be present. Inside family $i$, the napkins cover the table and have total area less than $\varepsilon$. If every napkin from different families intersects, then a disjoint subsystem lies in a single family and has area less than $\varepsilon$.

How can one make a covering family whose total area is arbitrarily small? A family of rectangles covering a set of area $1$ must have total area at least $1$, since the area of the union does not exceed the sum of the areas. Thus a single family cannot have total area below $1$.

So that idea is impossible.

The previous interpretation was wrong. A disjoint subsystem may contain many napkins from one family. We need a different combinatorial structure.

A standard trick is to use a fine grid. Let the square be partitioned into $m^2$ small cells. For each cell construct a napkin equal to the complement of that cell. Then all napkins together cover the table, because every point belongs to all napkins except possibly one.

Any two such napkins intersect enormously, so every pairwise non-overlapping subsystem contains at most one napkin. The area of each napkin is $1-\frac1{m^2}$, which is huge, not small.

Taking complements of thin cells does not help because the allowed shapes must be rectangles.

The crucial observation is that the intersection graph need only have very small weighted independence number. If every napkin has area less than $\varepsilon$, and every two napkins intersect, then any pairwise non-overlapping subsystem contains at most one napkin and hence has area less than $\varepsilon$. Thus it suffices to construct a covering of the table by rectangles of area less than $\varepsilon$, with the property that every two rectangles intersect.

Can such a covering exist? For intervals on a line, pairwise intersection implies a common point. For axis-parallel rectangles, pairwise intersection also implies a common point, because intervals satisfy Helly's theorem in one dimension and rectangles are products of intervals. Hence all rectangles may be arranged to contain one common point. Then their union can cover the whole square if enough small rectangles emanate from that point.

Take a common point at the center. Let a fine grid partition the square into cells of area less than $\varepsilon$. For each cell, take the smallest axis-parallel rectangle containing both the cell and the center. Every such rectangle contains the center, so all rectangles pairwise intersect. The collection covers the square because each cell is contained in its corresponding rectangle. We only need to check that every such rectangle has area less than $\varepsilon$.

That fails: a cell near a corner together with the center spans roughly one quarter of the square.

We need rectangles all of small area and all sharing a point. A common point forces a rectangle reaching a distant corner to have large area. So this route fails.

A different idea is to use several common points. Let the square be partitioned into many tiny rectangles. For each tiny cell $C$, use $C$ itself as a napkin. Then areas are small, but independent sets can contain all cells, total area $1$.

The hidden structure resembles a probabilistic or layered construction. Partition the square into $N$ vertical strips of width $1/N$. For each level $r=1,\dots,k$, group strips cyclically into blocks and create rectangles spanning full height. A disjoint subsystem can take at most one rectangle from each level. If the maximum area per rectangle is tiny and the number of levels is controlled, the total weight is small.

A cleaner construction is the standard one from hypergraph theory. Let $k$ be large. Partition the square into $k$ horizontal layers of height $1/k$. In layer $i$, partition into $n_i$ vertical rectangles. Every rectangle in the same layer is disjoint; rectangles from different layers are disjoint as well, so this is wrong.

Instead, for each $i$, let family $i$ consist of vertical strips covering the whole square, with widths summing to $1$. Any independent set can choose strips from only one family if strips from different families always intersect. Taking families with different orientations works only for two families.

The key idea is to use $m$ families, each family consisting of parallel strips in a distinct "combinatorial direction" encoded by partitions of $[0,1]$. Since rectangles must remain axis-parallel, a simpler argument is needed.

A known construction is to divide the square into $n\times n$ cells and, for each row and column pair, take the rectangle equal to their Cartesian product. That is just a cell.

The right construction is likely dualizing: choose $n$ vertical strips $V_i$ covering the square, each of area $1/n$. Choose $n$ horizontal strips $H_j$ covering the square, each of area $1/n$. The system consists of all intersections $R_{ij}=V_i\cap H_j$. Then each rectangle has area $1/n^2$. They cover the square. Any pairwise disjoint subsystem corresponds to a set of cells no two sharing a row or column, because cells in the same row or column intersect? Check. If $V_i$ are overlapping rather than partitioning, intersections behave differently.

Take $V_i=[\frac{i-1}{n},\frac{i}{n}]\times[0,1]$ and similarly horizontal strips. Then $R_{ij}$ are grid cells, pairwise disjoint. Independence number weight equals $1$.

Need overlapping strips. Let $V_i$ and $H_j$ each cover the whole square with multiplicity. Then $R_{ij}$ form a rectangle family. Two rectangles $R_{ij}$ and $R_{pq}$ are disjoint whenever $V_i\cap V_p=\varnothing$ or $H_j\cap H_q=\varnothing$.

Take $V_i$ pairwise disjoint partition strips. Then an independent set corresponds to a matching between rows and columns. Maximum size $n$, giving area $n\cdot (1/n^2)=1/n$. This works. Indeed, let $V_i$ be the $n$ vertical partition strips and $H_j$ the $n$ horizontal partition strips. Then $R_{ij}$ are exactly the $n^2$ grid cells. A pairwise non-overlapping subsystem can contain all $n^2$ cells, so not a matching. Wait, cells are pairwise disjoint. So failure.

Need rectangles not cells. Let napkins be $N_{ij}=V_i\cup H_j$, but unions are not rectangles.

Use rectangles $V_i\times H_j$ in coordinate notation with overlapping strip families. Let $V_i$ and $H_j$ each be intervals covering the line such that every point belongs to many intervals. Then each rectangle area small. An independent set corresponds to a set of pairs with disjoint $x$ intervals or disjoint $y$ intervals. This becomes a combinatorial problem. The standard construction: choose $n$ intervals on the line with independence number $1$ but small lengths summing little? No.

The classical solution is simpler: partition into $n$ vertical strips. For each strip create a rectangle covering the whole height. Any independent set has one rectangle, area $1/n$. But these rectangles do not cover? They do cover. In fact the system itself already works if $1/n<\varepsilon$, because pairwise non-overlapping subsystem of vertical partition strips can contain all strips, area $1$. So not.

Need all napkins intersecting enough.

Consider rectangles $R_i=I_i\times[0,1]$, where intervals $I_i$ cover $[0,1]$ and are pairwise intersecting. Then any independent set has at most one rectangle. By Helly on intervals, all $I_i$ share a point. To cover $[0,1]$, take intervals $I_i$ of length $2/n$ centered at points $i/n$, all additionally containing $1/2$? Impossible near ends.

Need area of each rectangle < ε. Since area equals interval length, intervals must be short. Yet pairwise intersecting intervals on a line have common point and total union length at most sum lengths. To cover length 1 with intervals all length < ε, need many intervals; that's fine. Let all intervals contain 1/2 and have length < ε. Can their union cover [0,1]? An interval containing 1/2 and length < ε cannot reach both far ends. Union of such intervals can cover [0,1] if there are intervals extending left and right. Example intervals [0,1/2] and [1/2,1], lengths 1/2. For ε small impossible because any interval containing 1/2 and length < ε lies inside [1/2-ε,1/2+ε]. Union cannot cover whole line. So impossible.

Need 2D geometry. I recall a construction using all rectangles containing a common vertical segment. Rectangles can have arbitrarily small area yet extend far in one direction if very thin in the other. Let common segment be entire height at x=1/2? A rectangle containing that segment must have full height, area equals width. Then small width rectangles around x=1/2 cannot cover corners.

Take common point instead. Rectangle from common point to a tiny cell has area proportional to distance product.

Need final solution. Think of table unit square. Choose grid n x n. For each cell C_ij, define rectangle from center lines? Let's derive known construction yielding weighted independence <1/n. Let vertical strips V_i width1/n partition. Horizontal strips H_j height1/n partition. Define napkin N_ij = V_i ∪ H_j impossible.

Need rectangles. Maybe N_ij = V_i × H_j = cell. Not.

I think known solution uses rectangles R_ij = V_i × (complement of H_j) not rectangle.

Running out. Let's find a combinatorial rectangle family: Let vertical intervals V_i partition x. Let horizontal intervals H_j partition y. Define rectangle R_ij = V_i × H_j. Independent weight bad.

Need family where any two with different i and j intersect. Define R_ij = V_i × [0,1] union not rectangle. Hmm.

Maybe take rectangles spanning from left edge to vertical strip i and from bottom edge to horizontal strip j: R_ij=[0,i/n]×[0,j/n]. Area ij/n². Independent sets correspond to chains. Choose small corner rectangles? Not.

Need construction where all rectangles have area ~1/n² and any disjoint family size ≤ n. Standard rectangle intersection graph of grid cells gives size n². For rectangles anchored at origin, any two intersect, independence size 1, but large areas.

Take rectangles R_ij = [(i-1)/n,i/n] × [0,j/n]. Area j/n² ≤1/n. Cover? Every point in cell (i,k) belongs to R_ij for j≥k, so yes. Two rectangles same column i are nested. Disjointness requires different columns and heights. For pairwise disjoint family, if i differs, x-ranges disjoint. Then one can choose one rectangle per column. Total area ≤ Σ(1/n)=1. Need <ε. More carefully max area per chosen rectangle could vary, total ≤ (1/n²)Σ j_i ≤ ~1/2, not small.

Need area bound independent set ≤1/n maybe if heights sum constrained. Let's compute. Disjoint rectangles from different columns always disjoint? They share no x. Then can take all columns with j=n, total area 1. Fail.

Need a known construction: rectangles R_ij = V_i × H_j where V_i, H_j are intervals lengths 1/n but overlapping chain. Let's stop and derive a workable one.

Take intervals I_i=[(i-1)/n,(i+1)/n] length 2/n. Cover [0,1]. Define rectangles R_ij=I_i×I_j. Area 4/n². They cover square. If two rectangles are disjoint, then either |i-p|≥2 or |j-q|≥2. An independent set in this graph on grid indices has pairwise Chebyshev distance at least 2. Max size about n²/4. Total area about 1, not small.

Need stronger overlap. Let intervals length m/n with m large. Then area (m/n)^2. Independence size about (n/m)^2. Product roughly 1. Constant.

Key invariant. Need weighted independence arbitrarily small. Use multiple scales. Construction akin interval cover with huge overlap making packing number small while rectangle area small.

Take intervals all containing a common point and length ε. Then independence size1, area ε². But cover fails. Maybe in 2D, rectangles containing a common point can cover square with small area? Yes! Rectangle containing center and a tiny cell near a corner has area about 1/4, not small. But if we partition into many tiny cells and choose rectangle between center and cell, area varies. Cells near center give tiny area, corners give ~1/4. Need recursive centers.

Known solution likely uses dyadic rectangles. Let each rectangle area ≤ ε and cover square. If all pairwise intersect, impossible to cover. Need intersection graph with bounded independence.

Use k common points. Cover square by rectangles each containing one of k points. Any independent set chooses at most k rectangles. If each rectangle area < ε/k, total < ε. Now can we cover square? Yes. Choose k points forming fine grid. For each point p_t, rectangles containing p_t and covering nearby region. Let square partitioned into k regions around these points. For any cell in region t, choose a rectangle containing p_t and the cell. If regions are small enough, such rectangles have area < ε/k.

This is the insight. Let k large. Partition square into $m\times m$ small cells, choose one point in each cell, so $k=m^2$. For every cell C and every point p_t in that same cell, consider all points? Need finite system. Simpler: For each cell D of partition and its chosen point p(D), take rectangle equal to D itself? Must contain p(D). We need cover. Let's construct for every point x in cell D, not finite. Wait system can be finite.

Let cells side δ. In each cell D choose center p_D. For every cell E, define rectangle R(D,E) as minimal axis-parallel rectangle containing p_D and E. Any point in E lies in R(D,E). Family over all D,E. Rectangles associated to same D all contain p_D. Thus independent set contains at most one rectangle for each D, hence at most k rectangles. Area of R(D,E)? If cells side δ=1/m, point p_D in D. Rectangle spanning p_D and cell E has area at most ((|a-c|+δ) (|b-d|+δ)). This can be large ~1. Not good.

Need points dense so distance to assigned point small. Let partition into k regions of area < ε/k. For each region D with point p_D. For every point in D, rectangle containing p_D and point has area ≤ area bounding region, < ε/k. Then rectangles associated to D all contain p_D. We only need finite covering: take each region itself as rectangle? Let's choose regions rectangular cells area < ε/k. For each cell D, and for each cell E? Hmm.

Need cover whole table by finitely many rectangles each area < ε/k and grouped by point. Simpler: let cells themselves be napkins. Then independent issue.

Construct for each cell D and each point? Need finite family covering entire square. Take within each cell D, one rectangle equal D. All rectangles in same group contain p_D, but only one rectangle. Independence sum can be 1.

Need every napkin area < ε/k and at most k can be chosen disjoint. If we partition into k cells, disjoint subsystem can choose all k cells, total area1.

Need grouping: For each group D, many rectangles covering whole square, each containing p_D, area < ε/k. Then any independent set at most one per group. Since there are k groups, total area < ε.

Take k cells of side δ where δ²=ε/k? Need cover whole square by union over groups. For a fixed point p_D, can rectangles containing p_D and area < ε/k cover whole square? They cover only neighborhood area at most? If p_D fixed, any such rectangle has area < ε/k. Union of all such rectangles can cover whole square if infinitely many. Finite allowed? System can be finite. Let region around p_D of dimensions maybe. Need explicit.

Choose $k$ large and partition square into $k$ vertical strips width 1/k. Let p_i be a point on left edge? Time.

Need finish. Construct k groups indexed by vertical strips S_i width 1/k. Let p_i inside strip. For every horizontal subdivision cell in strip i, create rectangle inside strip i containing p_i. Then area small. But union only strip i. Independent set can choose one per group, total area < ε if each area<ε/k. Cover whole square because strips covered. Yes! Group i confined to strip i. Rectangles in same group all contain p_i, so at most one chosen from each group. Rectangles from different groups are in disjoint strips, so may all be chosen, giving at most k rectangles. If each rectangle area < ε/k, total < ε.

Now make coverage. Let strip S_i width 1/k. Partition S_i into many horizontal rectangles of height h< ε. Let napkins be those cells. They all contain p_i? Cell can't all contain same point. Modify: choose p_i on strip center. Create rectangles spanning strip width and a small vertical interval containing p_i and each target horizontal segment. Need cover strip. Let strip partition into m horizontal segments J_t length 1/m. For each segment, rectangle = full strip width times minimal interval containing J_t and y-coordinate of p_i. Area = (1/k)*(length interval). If p_i at middle, segments far away give interval length about 1/2. Area ~1/(2k). Choose k > 1/(2ε), then area < ε. Need area < ε/k, stronger. Instead total independent ≤ k * area_max. Need area_max < ε/k. Area_max≈1/k impossible unless <ε/k requires area_max<1/k times ε. Need choose more groups.

Let number groups N. Strip width 1/N. Max area about 1/N. Independent set size ≤ N, product ≈1. Not enough.

Need area per rectangle O(1/N²). Then N choices give O(1/N). Put points more local. Partition square into N strips and within each strip use rectangles of area ≤1/N² covering strip, all containing common point. Possible? Strip area 1/N. A family of rectangles all containing p_i and area ≤1/N² can cover strip if strip height partitioned into N pieces. Take p_i at center. Far segments need area ~1/(2N). Not 1/N².

Need choose k=m² groups as cells. Each group's region area 1/k. Rectangles confined to region, area ≤1/k²? Then cover region impossible. Running out.

Need known solution: partition square into n vertical strips. In each strip, choose group. Any independent set ≤ n. Rectangle areas ≤1/n². Then total ≤1/n. Cover strip by n rectangles each area 1/n² containing common point in strip. Yes! Let strip width 1/n. Partition strip into n horizontal cells area1/n². For strip i choose point p_i. For each horizontal cell C in strip, define rectangle as minimal rectangle containing p_i and C. Since both lie in same strip, width ≤1/n, height ≤1, area ≤1/n, not 1/n². Not enough.

Need point at center of each cell? Hmm.

I will craft a coherent solution with groups as small squares. Let n large, partition into n² squares side1/n. For each square Q choose center c_Q. For every point? Hard.

Given uncertainty, cannot provide rigorous correct solution.