Kvant Math Problem 344
The 64 marked points are the centers of the squares of an $8\times 8$ grid, hence they can be identified as
Verified: no
Verdicts: SKIP + SKIP
Solve time: 7m32s
Source on kvant.digital
Problem
On a chessboard, the centers of all 64 squares are marked. Is it possible to draw 13 straight lines on the board such that in each of the regions into which these lines divide the board there is no more than one marked point? (The lines must not pass through the centers of the squares, see Fig. 1).
Figure 1
A. N. Pechkovsky
Exploration
The 64 marked points are the centers of the squares of an $8\times 8$ grid, hence they can be identified as
$\left(i+\tfrac12,; j+\tfrac12\right), \quad i,j\in{0,1,\dots,7}.$
Drawing $13$ lines produces a planar arrangement whose complement is partitioned into regions. The requirement that each region contains at most one marked point is equivalent to the condition that no two centers lie in the same cell of the arrangement.
Each line assigns to every point a binary value according to which side of the line it lies on. Thus $13$ lines produce a sign vector in ${\pm 1}^{13}$ for each of the $64$ points. Two points lie in the same region if and only if they induce the same sign vector for all lines.
Hence the task is equivalent to finding $13$ lines such that the induced map from the $64$ grid points to ${\pm 1}^{13}$ is injective.
There are $2^{13}=8192$ possible sign vectors, far exceeding $64$, so there is no combinatorial obstruction. The real difficulty is geometric: all separating hyperplanes must be realized by straight lines in the plane avoiding all grid centers.
A deterministic coordinate-encoding construction is complicated because axis-aligned partitions do not produce enough regions. A probabilistic approach suggests itself: a random line separates any fixed pair of points with probability $\tfrac12$, and independence across lines suggests exponential decay of failure probability.
The key issue is whether one can ensure simultaneously that all $\binom{64}{2}$ pairs are separated by at least one of the $13$ lines. This becomes a union of finitely many measure-zero events in a continuous parameter space of line configurations.
This indicates that a generic choice of $13$ lines should work, provided degeneracies (passing through centers or failing separations) are excluded.
Problem Understanding
This is a Type D problem. One must construct $13$ straight lines so that the induced partition of the plane separates the $64$ centers of an $8\times 8$ grid into singleton regions.
Equivalently, one must show the existence of $13$ lines such that every pair of distinct grid centers is separated by at least one of the lines.
The core difficulty is not combinatorial counting, since $13$ lines can produce up to $92$ regions, which exceeds $64$, but geometric: ensuring that the arrangement can be chosen so that no region contains more than one of the distinguished lattice points.
The correct strategy is to view the problem as one of random hyperplane separation in $\mathbb{R}^2$ and show that a generic configuration works.
Proof Architecture
The proof proceeds by reformulating lines as random affine linear functionals on $\mathbb{R}^2$, inducing sign vectors on the finite set of $64$ points.
A lemma establishes that for any fixed pair of distinct points, the probability that a random line fails to separate them is exactly $\tfrac12$.
A second lemma shows that for $13$ independent random lines, the probability that a fixed pair is never separated is $2^{-13}$.
A third lemma applies a union bound over all $\binom{64}{2}$ pairs to show that the probability that some pair is never separated is strictly less than $1$, hence positive probability of success exists.
A final lemma ensures that with probability $1$, no line passes through any center, so all constructions are admissible.
The hardest point is the justification that probabilistic independence is sufficient to guarantee existence of a deterministic configuration satisfying all constraints simultaneously.
Solution
Identify the $64$ marked points as
$P_{ij}=\left(i+\tfrac12,; j+\tfrac12\right), \quad i,j\in{0,1,\dots,7}.$
Consider a random line in the plane given in normal form
$ax+by+c=0,$
where $(a,b,c)$ is chosen from a continuous distribution that is absolutely continuous with respect to Lebesgue measure and such that $(a,b)\neq(0,0)$ almost surely.
For any fixed pair of distinct points $P$ and $Q$, define the event that a line does not separate them. This occurs exactly when $P$ and $Q$ lie in the same open half-plane determined by the line, which is equivalent to
$(aP_x+bP_y+c)(aQ_x+bQ_y+c)>0.$
For a random line, symmetry under reflection through the midpoint of segment $PQ$ implies that the probability that $P$ and $Q$ lie on opposite sides is $\tfrac12$, and hence the probability that they lie on the same side is also $\tfrac12$.
Now choose $13$ independent random lines $L_1,\dots,L_{13}$ from such a distribution. For a fixed pair $(P,Q)$, the probability that none of the $13$ lines separates them equals
$\left(\tfrac12\right)^{13}.$
There are $\binom{64}{2}=2016$ unordered pairs of distinct points. By the union bound, the probability that there exists a pair not separated by any of the $13$ lines is at most
$2016\cdot 2^{-13} < 1.$
Hence there exists a choice of $13$ lines such that every pair of distinct marked points is separated by at least one line.
It remains to ensure that no line passes through any marked point. For a fixed point $P$, the set of parameters $(a,b,c)$ such that $aP_x+bP_y+c=0$ is a codimension-one subset of measure zero in parameter space, hence the probability that any chosen random line passes through any of the $64$ points is zero. With finitely many lines, the probability that any degeneracy occurs remains zero, so the chosen configuration can be assumed non-degenerate.
For such a configuration, for any two distinct points $P,Q$, there exists a line $L_k$ that separates them. Therefore $P$ and $Q$ lie in different regions of the complement of the union of the lines. Consequently no region contains more than one marked point.
This completes the construction of $13$ lines satisfying the required condition. ∎
Verification of Key Steps
The separation probability for a fixed pair relies on symmetry of the space of oriented lines: reflecting a line through the midpoint of two points swaps the events “same side” and “opposite sides,” forcing equal probability for both outcomes.
The union bound step is numerically consistent since $2016\cdot 2^{-13}=\frac{2016}{8192}<1$, ensuring that the failure probability is strictly less than $1$, which guarantees existence of a successful configuration.
The non-degeneracy argument follows from the fact that for any fixed point, the condition that a line passes through it imposes a single linear constraint on $(a,b,c)$, producing a measure-zero subset; a finite union over all points and lines remains measure zero, so generic choices avoid all centers simultaneously.
Alternative Approaches
A deterministic construction could be attempted by encoding the coordinates of each grid point into a binary vector using carefully chosen separating directions, for example lines with progressively steeper slopes designed to implement lexicographic ordering of coordinates. However, ensuring that such a construction simultaneously separates all $64$ points without accidental coincidences is technically intricate.
The probabilistic method is preferable because it bypasses explicit geometric encoding and replaces it with a measure argument in a finite configuration space, where all failure events reduce to unions of zero-measure sets.