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 .
Problem
Source: Romania TST 2015 Day 2 Problem 4
Tags: combinatorics, Romanian TST
05.06.2015 08:42
In the actual statement asked, point b) was rephrased "no proper subset of which is a null set", which created a snafu, since the most trivial $A = \{0,1\}^3$ is such.
14.06.2015 10:30
(a) Take a point $a_1\in A\subset \mathbb{Z}^2$. Choose $a_2\in A$ on the same horizontal line as $a_1$, then $a_3$ on the same vertical line as $a_2$ and so on, until at first time we get to $a_n$, which is in a line we've been before. Suppose that line is determined by $a_k, a_{k+1}$. Then $\{a_n, a_{k+1},a_{k+2},\dots, a_{n-1}\}$ is a null set. (b) Consider $A' := \{(i,j,k)\in \mathbb{Z}^3 : i,j,k \in \{0,1,2\} \}$. Remove from $A'$ the following points: $(0,0,0), (2,2,2), (2,1,0), (2,0,1), (1,2,1), (1,0,2), (0,1,2)$ and let $A$ is the remaining set. I think, $A$ is a required counterexample, thou proving it involves a bit of case chasing.
09.06.2020 17:04
dgrozev wrote: (b) Consider $A' := \{(i,j,k)\in \mathbb{Z}^3 : i,j,k \in \{0,1,2\} \}$. Remove from $A'$ the following points: $(0,0,0), (2,2,2), (2,1,0), (2,0,1), (1,2,1), (1,0,2), (0,1,2)$ and let $A$ is the remaining set. I think, $A$ is a required counterexample, thou proving it involves a bit of case chasing. Unfortunately it seems $A-\{(0,1,0),(1,1,0),(0,2,0),(0,1,1)\}$ is null. To construct an example for (b) we first note that (1) finite null sets are admissible, hence it suffices to construct a minimal admissible set in $\mathbb{Z}^3$ that's not null; (2) $\emptyset\neq A\subset\mathbb{Z}^n$ is admissible iff each $A\cap(\mathbb{Z}^{n-1}\times a_n)$ is either empty or admissible in $\mathbb{Z}^{n-1}$ and $A\cap((a_1,...,a_{n-1})\times\mathbb{Z})$ is never a singleton. Now let $S=\{0,1,2\}^2-\{(0,1),(1,0),(2,2)\}\subset\mathbb{Z}^2$, $r:\mathbb{Z}^2\rightarrow\mathbb{Z}^2$ be the $90^\circ$ clockwise rotation around $(1,1),$ then $S$ is a minimal admissible set in $\mathbb{Z}^2$ and we claim that \[T=\coprod_{k=0}^3r^kS\times k\subset\mathbb{Z}^3\]is a minimal admissible subset, which is clearly not null. By (2) it's easy to see that $T$ is admissible, meanwhile any admissible subset of $T$ must be a union of several $r^kS\times k$, and we see it has to be $T$ itself by considering its intersections with the lines $(0,1)\times\mathbb{Z},$ $(1,0)\times\mathbb{Z},$ $(1,2)\times\mathbb{Z}$ and $(2,1)\times\mathbb{Z}$.