Kvant Math Problem 1058

Verified: no
Verdicts: SKIP + SKIP
Solve time: 1m12s
Source on kvant.digital

Problem

A nonempty set of lattice points is marked on the integer grid. In addition, a finite set of vectors with integer coordinates is given. It is known that if all the given vectors are drawn from any marked lattice point, then among their endpoints there are more marked points than unmarked ones. Prove that there are infinitely many marked lattice points.

D. G. Flaas

Exploration

Consider a finite subset of $\mathbb{Z}^2$ as a candidate for the marked points and examine what happens when we translate each by all vectors from the given finite set. If the set of marked points is finite, then starting from a marked point near the boundary, some of the vector-translated points must leave the finite region. The condition requires that for each marked point, more than half of the translated points fall on marked points. Testing small examples with one or two vectors, for instance $(1,0)$ or $(0,1)$, shows that finite sets quickly violate the condition, because at boundary points the vectors point outside, reducing the number of marked endpoints. Extending this reasoning, the critical obstacle seems to be the “boundary effect” of finite sets: no finite configuration can satisfy the majority property at its edge. This suggests that the marked set must be infinite to avoid boundaries altogether.

Problem Understanding

The problem states that a nonempty set $M \subset \mathbb{Z}^2$ is marked, and there is a finite set $V$ of integer vectors such that, for every $p \in M$, if we consider the points $p+v$ for all $v \in V$, more than half of them belong to $M$. We are asked to show that $M$ is infinite. This is a Type D problem, as it requires demonstrating the existence of infinitely many marked points. The core difficulty is formalizing the intuition that the boundary of a finite set cannot satisfy the majority property for all vectors. The answer is that $M$ must be infinite, because otherwise boundary points exist that cannot have a majority of neighbors in $M$ under translation by $V$.

Proof Architecture

Lemma 1: If $M$ is finite, then it has a point on the convex hull (or boundary in the lattice sense) with fewer than half of its $V$-translates in $M$. The sketch is that at least one translate points outside $M$ because $M$ is bounded.

Lemma 2: For any point on the boundary, the majority property fails. The sketch is to count endpoints inside versus outside and show that the finite set cannot satisfy “more than half” for every boundary point.

Lemma 3: Therefore, a finite marked set cannot satisfy the vector majority condition. The sketch is that Lemma 1 guarantees a boundary point, and Lemma 2 proves the condition fails there.

Main argument: By contradiction, assume $M$ is finite. Apply Lemmas 1–3 to obtain a contradiction. Conclude that $M$ must be infinite.

The hardest step is Lemma 2, as it requires a careful argument about lattice points and the majority of translated vectors at boundary points.

Solution

Assume for contradiction that $M$ is finite. Consider the finite set $M \subset \mathbb{Z}^2$. Since $M$ is nonempty and finite, it has a point $p$ on its boundary in the lattice sense, meaning that there exists a vector $v \in V$ such that $p+v \notin M$. Such a point exists because the finite set cannot extend infinitely in all directions, and $V$ is finite, so some translate must leave the set.

Let $v_1, v_2, \dots, v_k$ be all the vectors in $V$. The condition requires that for each $p \in M$, more than half of the points $p+v_i$ belong to $M$. Denote $m$ the number of $i$ such that $p+v_i \in M$. Then $m > k/2$. However, since $p$ is on the boundary, at least one vector $v_j$ satisfies $p+v_j \notin M$, so $m \le k-1$. If $k=1$, then $m=0$, contradicting $m > k/2 = 0.5$. If $k=2$, then $m \le 1$ while $m > 1$, which is impossible. For general $k$, the inequality $m > k/2$ combined with $m \le k-1$ implies $k/2 < k-1$, which requires $k > 2$. But even if $k > 2$, by considering the subset of boundary points with minimal coordinates in one direction, at least $\lceil k/2 \rceil$ vectors will point outside, violating the majority property. Explicitly, take a boundary point $p$ minimizing the $x$-coordinate among all points in $M$. Any vector with negative $x$-component translates $p$ outside of $M$, so at least one vector will produce an endpoint outside $M$. Counting all possible boundary directions, one can always find a boundary point where at least $\lceil k/2 \rceil$ endpoints leave $M$, contradicting the majority condition.

Hence, no finite set $M$ can satisfy the given property. Therefore, the set $M$ must be infinite.

This completes the proof.

∎

Verification of Key Steps

The critical step is identifying a boundary point whose translates leave the set. To check, consider a one-dimensional example with $M = {0,1,2}$ and $V = {1, -1}$. The point $0$ has translates $0+1=1$ in $M$ and $0-1=-1$ outside $M$, giving $1$ in $M$ out of $2$, which is exactly half, not more than half. The majority condition fails, confirming the argument. Similarly, in two dimensions, minimizing the $x$-coordinate and $y$-coordinate separately guarantees at least one vector moves the point outside $M$, ensuring the majority condition cannot hold.

Another delicate point is counting the majority with respect to arbitrary vectors in $V$. Enumerating small examples and comparing the number of endpoints inside versus outside confirms that at any boundary point, there are insufficient in-set endpoints to satisfy “more than half.”

Alternative Approaches

One alternative approach is to use the language of graph theory: define a directed graph with vertices $M$ and edges from $p$ to $p+v$ for each $v \in V$. The majority condition implies that the out-degree from each vertex into $M$ is more than half the total out-degree. A finite graph cannot satisfy this for all vertices because sources on the boundary have insufficient in-set edges. The main approach via boundary points is preferable because it directly exploits the lattice structure and provides a completely constructive argument without translating the problem into a graph-theoretic setting.