Partitioning the plane into three sets each intersecting the vertices of every square with side 1?

Question

Q1. Is it possible to partition the plane into three sets such that each of them contains at least one vertex of every square with side 1 ? (I mean all squares of side-length 1, not just those with sides parallel to the coordinate axes.)

Q2. Let $n$ be the largest integer such that the plane could be partitioned into $n$ sets such that each of them contains at least one vertex of every square with side 1. It is easily seen that $2\le n \le 4$. What is the value of $n$? Any references? Edit. @Zander below proved that $n=4$ is not possible (is this a new result? I didn't expect that $n=4$ would be possible, but I didn't have a proof).

Q3. Any variations of the above question, when, instead of the vertices of a square with side $1$, we take and fix any subset $S$ of the plane. Let $n(S)$ be the largest integer such that the plane could be partitioned into $n(S)$ sets such that each of them intersects every congruent (perhaps orientation-preserving) copy of $S$. Clearly $1\le n(S) \le |S|$. What is the value of $n(S)$? Part of the answer here would be to find suitable $S$ for which this question is interesting. Are there any references to work along these lines that has been done? (The question seems natural for finite sets, but perhaps also interesting for some infinite $S$.)

Answer 1

For Q2 $n=4$ is not possible.

Let $c(\mathbf{x}) \in \{A,B,C,D\}$ denote the color of a point $\mathbf{x}$. As you noted in the comments, a 4-coloring with every unit square having four different-colored vertices would require

C1: No pair of points separated by a distance of $1$ or $\sqrt 2$ can have the same color.

From C1 we can show:

C2: For any point $\mathbf{o}$ and any orthonormal vectors $\mathbf{u},\mathbf{v}$ either $$ c(\mathbf{x}+2\mathbf{u}) = c(\mathbf{x}) \text{ for every } \mathbf{x}=\mathbf{o}+m\mathbf{u}+n\mathbf{v} $$ or $$ c(\mathbf{x}+2\mathbf{v}) = c(\mathbf{x}) \text{ for every } \mathbf{x}=\mathbf{o}+m\mathbf{u}+n\mathbf{v} $$ for $m,n\in\mathbb{Z}$. That is, $c$ is periodic with period $2\mathbf{u}$ or $2\mathbf{v}$ on the lattice generated by $\mathbf{u},\mathbf{v}$.

From C1 and C2 we get:

C3: For $\mathbf{o},\mathbf{u},\mathbf{v}$ as above there is some $\mathbf{x}=\mathbf{o}+m\mathbf{u}+n\mathbf{v}$ with $$ c(\mathbf{x}) = c(\mathbf{x}+2\mathbf{u}) = c(\mathbf{x}+2\mathbf{v}) $$ or $$ c(\mathbf{x}) = c(\mathbf{x}+4\mathbf{u}) = c(\mathbf{x}+4\mathbf{v}) $$

And C2 and C3 contradict C1, hence no such coloring is possible.

Proof: C1$\implies$C2:

Either $c(\mathbf{o}+2m\mathbf{u})=c(\mathbf{o}),c(\mathbf{o}+(2m+1)\mathbf{u})=c(\mathbf{o}+\mathbf{u}) $ for all $m$, or else there is some $\mathbf{x} = \mathbf{o}+m_0\mathbf{u}$ with $c(\mathbf{x}),c(\mathbf{x}+\mathbf{u}),c(\mathbf{x}+2\mathbf{u})$ three different colors, wlog $A,B,C$. In that case the constraints of C1 uniquely determine $c(\mathbf{x}+n\mathbf{v})$. Specifically $c(\mathbf{x}+2n\mathbf{v})=A$ and $c(\mathbf{x}+(2n+1)\mathbf{v})=C$. In a picture, starting with $\mathbf{x}$ in the top left with $\mathbf{u}$ going right and $\mathbf{v}$ going down: $$ \begin{array}{cccc} \cdots & A & B & C & \cdots \\ \cdots & C & D & A & \cdots \\ \cdots & A & B & C & \cdots \\ \cdots & C & D & A & \cdots \\ \cdots & A & B & C & \cdots \\ & \vdots & \vdots & \vdots \end{array} $$ Hence either the row containing $\mathbf{o}$ or the column containing $\mathbf{x}$ is periodic with period $2\mathbf{u}$ or $2\mathbf{v}$ respectively, and it's easy to see that either implies that the rest of the lattice is periodic with the same period.

C1 and C2 $\implies$ C3:

From C2 wlog assume coloring on the $\mathbf{o},\mathbf{u},\mathbf{v}$ lattice has period $2\mathbf{u}$. Either there is some $\mathbf{x}$ with $c(\mathbf{x}+2\mathbf{v})=c(\mathbf{x})=c(\mathbf{x}+2\mathbf{u})$, satisfying the first condition of C3, or else $c(\mathbf{x}+2\mathbf{v})\ne c(\mathbf{x})$ for every $\mathbf{x}$ in the lattice. In that case wlog let the colors of $\mathbf{o},\mathbf{o}+\mathbf{u},\mathbf{o}+\mathbf{v},\mathbf{o}+\mathbf{u}+\mathbf{v}$ be $A,B,C,D$ respectively, and this condition along with the constraints of C1 can fill out the coloring on the lattice. In a picture, we must continue: $$ \begin{array}{cccc} \cdots & A & B & A & \cdots \\ \cdots & C & D & C & \cdots \\ \cdots & B & A & B & \cdots \\ \cdots & D & C & D & \cdots \\ \cdots & A & B & A & \cdots \\ & \vdots & \vdots & \vdots \end{array} $$ Hence $c(\mathbf{o}+4\mathbf{v}) = c(\mathbf{o}) = c(\mathbf{o}+4\mathbf{u})$.

C2 and C3 $\implies$ not C1:

On a lattice with $\mathbf{o},\mathbf{u},\mathbf{v}$ as above, from C3 there is an $\mathbf{X}$ with $\mathbf{Y}=\mathbf{X}+t\mathbf{u}, \mathbf{Z}=\mathbf{X}+t\mathbf{v}$ and $$ c(\mathbf{X}) = c(\mathbf{Y}) = c(\mathbf{Z}) $$ for either $t=2$ or $t=4$. There are orthonormal vectors $\mathbf{u}',\mathbf{v}'$ such that $\mathbf{Y}' = \mathbf{X}+t\mathbf{u}', \mathbf{Z}' = \mathbf{X}+t\mathbf{v}'$ and $\left\vert \mathbf{YY}'\right\vert = \left\vert \mathbf{ZZ}'\right\vert = 1$.

Then by C2 either $c(\mathbf{Y}')=c(\mathbf{X})=c(\mathbf{Y})$ or $c(\mathbf{Z}')=c(\mathbf{X})=c(\mathbf{Z})$, contradicting C1.

Answer 2

Q1. Yes. First, note that the plane can be partitioned as the set of all lines with slope 1. These lines can be indexed by their x-intercepts, so define $L_k$ to be the line with x-intercept $k$, which has equation $y=x-k$. Now, define three sets as follows:

$$A = \{k \in \mathbb{R} \mid \lfloor k \rfloor \equiv 0 \pmod 3 \}$$ $$B = \{k \in \mathbb{R} \mid \lfloor k \rfloor \equiv 1 \pmod 3 \}$$ $$C = \{k \in \mathbb{R} \mid \lfloor k \rfloor \equiv 2 \pmod 3 \}$$

The three sets which partition the plane such that each of them contains at least one vertex of every square with side 1 are

$$S_A = \bigcup_{k \ \in \ A} L_k \ \ \ \ \ \ \ \ \ S_B = \bigcup_{k \ \in \ B} L_k \ \ \ \ \ \ \ \ \ S_C = \bigcup_{k \ \in \ C} L_k$$

Any square of side-length 1 is of the form $\{(x,y), (x+1,y), (x,y+1), (x+1,y+1) \}$ for some $x,y \in \mathbb{R}$. The x-intercepts of the slope-1 lines which these points lie on are $x-y -1$, $x-y$, and $x-y+1$ (the first and fourth points both have x-intercept $x-y$).

Now, note that $\lfloor x-y-1 \rfloor = \lfloor x-y \rfloor - 1$ and $\lfloor x-y+1 \rfloor = \lfloor x-y \rfloor + 1$, and that none of $\lfloor x-y \rfloor - 1$, $\lfloor x-y \rfloor$, and $\lfloor x-y \rfloor + 1$ are congruent to each other mod 3. Thus each of the sets $S_A$, $S_B$, and $S_C$ contains at least one of the square's four vertices.