USA TSTST 2022, Problem 1

An interactive covering exercise — place rectangles so that they swallow the whole square except the marked points.

Problem (USA TSTST 2022 P1). Let n be a positive integer. Find the smallest positive integer k such that for any set S of n points in the interior of the unit square, there exists a set of k rectangles such that the following hold:

(The interior of a polygon does not contain its boundary.)

Rectangles placed: 0

How to play

  1. Choose n and a distribution, then press Generate points. The points of S appear as black dots inside the unit square.
  2. Drag on empty space to draw a rectangle. While dragging, each edge zips to the nearest vertical or horizontal line through a point of S, the boundary of the square, or an edge of an existing rectangle.
  3. Click a rectangle to select it. Drag its body to move it, or its small handles to resize it — edges still snap. Press Delete/Backspace or the button to remove it.
  4. Press Check. You win when (i) no marked point lies in the interior of a rectangle — so every point must sit on rectangle boundaries — and (ii) every other interior point of the square is covered by some rectangle's interior.
  5. Use as few rectangles as you can. The theoretical answer is k = 2n + 2; try not to exceed it.
Note: collinear points (sharing an x- or y-coordinate) are exactly where naive strip constructions fail — this is what makes the olympiad problem tricky.

About the problem

The answer is k = 2n + 2: a counting argument (every point must be "bracketed" by rectangle edges on all four sides, and the extremal rectangles can border at most one or two points) gives the lower bound for points on a diagonal, while an induction or strip-plus-patch construction gives the upper bound.

Only 8 of 63 TSTST contestants solved it; the author's account and solutions are in the AoPS thread.