Kvant Math Problem 1531

Verified: no
Verdicts: UNKNOWN + UNKNOWN
Solve time: 10m23s
Source on kvant.digital

Problem

A square and an invisible point $Р$ are given in the plane. One may draw any straight line and ask on which side of it (or on the line itself) $Р$ lies. What is the smallest number of questions needed to determine whether $Р$ lies inside the square?

A. Ya. Kanel-Belov

Exploration

Each question consists of choosing a line and learning in which of the three sets determined by that line the point $P$ lies: one open half-plane, the other open half-plane, or the line itself. Thus a sequence of $n$ questions partitions the plane into regions, and all points in the same region produce exactly the same answers.

We must decide whether $P$ is inside a fixed square. Let $S$ denote the square. After all questions, every region of the partition must lie entirely inside $S$ or entirely outside $S$; otherwise two points from the same region would yield the same answers but require different outputs.

The first task is a lower bound. One line intersects the boundary of a convex quadrilateral in at most two points, hence $n$ lines intersect the boundary of the square in at most $2n$ points. These points divide the boundary into at most $2n$ arcs. Along each arc, the sign pattern with respect to all chosen lines is constant, so each arc belongs to a single final region. Every region meeting the boundary contributes at most one connected arc of the boundary, because the region is convex, being an intersection of half-planes and lines.

To separate the interior of the square from the exterior, each side of the square must be cut away from the exterior. Intuitively one needs enough boundary pieces to alternate between regions lying inside and regions lying outside. The square boundary has four vertices, and if no line passes through a vertex, every vertex is a transition between an inside boundary arc and an outside boundary arc. Hence at least eight boundary arcs are needed. Since there are at most $2n$ arcs, we obtain $2n\ge8$, thus $n\ge4$.

Can four questions suffice? Yes. Ask the four supporting lines of the square, one for each side. From the answers we know on which side of each side-line the point lies. The point is inside the square exactly when it lies in the appropriate half-plane for all four side-lines. Thus four questions are enough.

The delicate point is the lower bound. One must justify rigorously that fewer than four lines cannot produce enough boundary pieces to separate inside from outside.

Problem Understanding

A fixed square is given. An unknown point $P$ is somewhere in the plane. For any chosen line, we may ask whether $P$ lies on one side of the line, on the other side, or on the line itself. We seek the minimum number of such questions that always allows us to determine whether $P$ belongs to the square.

This is a Type C problem. We must determine the minimum number of questions, exhibit a strategy achieving that number, and prove that no smaller number can suffice.

The core difficulty is proving the lower bound. Any collection of questions partitions the plane into regions on which all answers are identical. Every such region must be entirely inside or entirely outside the square. The geometry of how lines cut the boundary of a square limits how many such regions can meet the boundary.

The answer should be $4$, because the four side-lines of the square immediately test the four defining inequalities of the square.

Proof Architecture

Lemma 1. After all questions, the plane is partitioned into convex regions, and every region must lie entirely inside the square or entirely outside it.

Sketch: Points in one region give identical answers; if a region contained both an interior and an exterior point, the procedure could not distinguish them.

Lemma 2. If $n$ lines are drawn, they intersect the boundary of the square in at most $2n$ points, hence divide the boundary into at most $2n$ connected arcs.

Sketch: A line meets the boundary of a convex polygon in at most two points.

Lemma 3. Every final region intersects the boundary of the square in at most one connected arc.

Sketch: A region is convex; the intersection of a convex set with the boundary of a convex polygon cannot consist of two disjoint arcs.

Lemma 4. Any correct partition requires at least eight boundary arcs.

Sketch: Traversing the boundary of the square, the four vertices separate boundary portions adjacent to the interior of the square from portions adjacent to the exterior. Thus the boundary must contain four inside arcs and four outside arcs alternating cyclically.

The hardest direction is the lower bound. Lemma 4 is the point most likely to fail if one argues informally.

Solution

Let $S$ be the given square.

Suppose that $n$ questions are asked. The chosen lines are fixed in advance or may depend on previous answers; in either case, after all answers are obtained, the point $P$ belongs to a cell determined by the lines that have been drawn. Each cell is an intersection of half-planes and possibly some lines, hence is convex.

Two points belonging to the same cell produce exactly the same answers to all questions. Consequently, if one cell contained a point of $S$ and a point outside $S$, the procedure could not determine whether the unknown point lies in $S$. Hence every cell must be entirely contained in $S$ or entirely disjoint from the interior of $S$.

We now prove that $n\ge4$.

Each drawn line intersects the boundary $\partial S$ of the square in at most two points, because the square is convex. Therefore $n$ lines create at most $2n$ intersection points on $\partial S$. These points divide $\partial S$ into at most $2n$ connected arcs.

Consider any cell $C$. Since $C$ is convex, $C\cap\partial S$ cannot contain two disjoint nonempty arcs. Indeed, if it contained two such arcs, choose one point on each arc. The segment joining them lies in the convex set $C$. Since the two arcs are separated along the boundary of the square, that segment passes through points of the square boundary outside those arcs, forcing $C\cap\partial S$ to contain the boundary portion between them, a contradiction. Thus every cell contributes at most one boundary arc.

Since every cell is either entirely inside $S$ or entirely outside $S$, each boundary arc belongs to either an inside cell or an outside cell.

Traverse the boundary of the square once. Near the midpoint of any side, points immediately inside the square belong to inside cells, while points immediately outside belong to outside cells. At each of the four vertices these two types must alternate. Consequently the boundary must be divided into at least four inside arcs and four outside arcs, alternating cyclically. Hence at least eight boundary arcs are required.

Since the number of boundary arcs is at most $2n$, we obtain

$$2n\ge 8,$$

so

$$n\ge4.$$

It remains to show that four questions suffice.

Take the four lines containing the sides of the square. Ask, for each of these lines, on which side of the line the point $P$ lies, or whether it lies on the line.

Each side-line determines a half-plane containing the square. The point $P$ lies inside the square, or on its boundary, exactly when for all four side-lines it lies in the corresponding half-plane or on the line itself. The four answers therefore determine completely whether $P\in S$.

Thus four questions are sufficient, and no fewer than four questions can suffice.

Hence the minimum number of questions is

$$\boxed{4}.$$

Verification of Key Steps

The first delicate step is the assertion that every cell must be entirely inside or entirely outside the square. Suppose a cell contained points $A\in S$ and $B\notin S$. Since all points of the cell give identical answers, the procedure would return the same verdict for $A$ and $B$. One of these verdicts would be wrong. Thus such a cell cannot exist.

The second delicate step is the estimate of at most $2n$ boundary arcs. A single line can intersect the boundary of a convex quadrilateral in at most two points. For $n$ lines there are at most $2n$ intersection points on the boundary. A circle cut at $m$ points yields $m$ arcs, so the boundary of the square is divided into at most $2n$ arcs.

The third delicate step is the necessity of at least eight arcs. Consider the four vertices. Between consecutive vertices, a boundary portion is adjacent on one side to points inside the square and on the other side to points outside the square. Since cells cannot mix inside and outside points, the boundary portions adjacent to inside cells and those adjacent to outside cells must alternate around the boundary. Four alternations require at least four inside arcs and four outside arcs, giving at least eight arcs in total.

Alternative Approaches

A different lower-bound argument uses the fact that the square is the intersection of four supporting half-planes. Any correct procedure induces a decomposition of the plane into cells, each labelled “inside” or “outside”. The boundary between the inside and outside labels must contain the entire boundary of the square. Since one line can contribute at most two intersection points with the square boundary, fewer than four lines cannot generate enough distinct boundary segments to realize all four sides of the square as separating curves.

The boundary-arc method used above is preferable because it converts the problem into a simple counting argument. The geometry needed is limited to two facts: a line meets a convex quadrilateral in at most two boundary points, and each cell produced by lines is convex. These facts lead directly to the sharp bound $n\ge4$, which is then attained by the four side-lines of the square.