Problem

Source: Romania TST 2015 Day 2 Problem 4

Tags: combinatorics, Romanian TST



Consider the integral lattice $\mathbb{Z}^n$, $n \geq 2$, in the Euclidean $n$-space. Define a line in $\mathbb{Z}^n$ to be a set of the form $a_1 \times \cdots \times a_{k-1} \times \mathbb{Z} \times a_{k+1} \times \cdots \times a_n$ where $k$ is an integer in the range $1,2,\ldots,n$, and the $a_i$ are arbitrary integers. A subset $A$ of $\mathbb{Z}^n$ is called admissible if it is non-empty, finite, and every line in $\mathbb{Z}^{n}$ which intersects $A$ contains at least two points from $A$. A subset $N$ of $\mathbb{Z}^n$ is called null if it is non-empty, and every line in $\mathbb{Z}^n$ intersects $N$ in an even number of points (possibly zero). (a) Prove that every admissible set in $\mathbb{Z}^2$ contains a null set. (b) Exhibit an admissible set in $\mathbb{Z}^3$ no subset of which is a null set .