10
$\begingroup$

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$.)

$\endgroup$
  • $\begingroup$ Just a comment to explain why this problem might be difficult. I came up with it while reading about a known difficult problem. This relation does not seem specific enough to suggest any particular conclusions, but at any rate these potentially related knows problems are the Hadwiger-Nelson problem and the Moser spindle example that goes with it. See also Unit distance graph $\endgroup$ – Mirko Nov 16 '14 at 13:29
  • $\begingroup$ Let $T$ be the set of vertices of an equilateral triangle with side-length $1$. Let $M$ be the Moser spindle. $M$ shows that (as defined in Q3 above) $n(T)<3$ (strictly). It follows that $n(T)=2$ (partition the plane into horizontal halp-open strips of width $\sqrt{3}/2$, and take the union of the "even" strips, and the union of the "odd" strips to show $n(T)\ge2$). If the chromatic number (i.e. the answer of Hadwiger–Nelson problem) of the plane were $4$, then this would imply that $n(M)\ge4$ (though it is not unlikely that $n(M)\ge4$ anyway). $\endgroup$ – Mirko Nov 17 '14 at 20:28
  • $\begingroup$ Let $Q$ be the set of vertices of a square with side 1. I do not know if $n(Q)=4$, but IF $n(Q)=4$ THEN the chromatic number of the plane $\chi(R^2)=4$(the answer to Hadwiger-Nelson problem). Indeed, if there is a 4-coloring of the plane such that the vertices of every square with side 1 have different colors, then clearly every 2 points distance 1 apart would have different colors (take a square such that the two points are two neighboring vertices) AND every two points distance $\sqrt{2}$ apart would also have different colors (take a square so that the two points are diagonally opposite). $\endgroup$ – Mirko Nov 21 '14 at 1:59
1
$\begingroup$

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$.

enter image description here

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.

$\endgroup$
  • $\begingroup$ thanks I'll take a look, I am certainly interested to see your proof ... but re the bounty I already had awarded it and it doesn't seem I could take it back now ... but let me read what you posted $\endgroup$ – Mirko Nov 23 '14 at 23:05
  • $\begingroup$ I am a slow reader ... it took me an hour or so, but I read through it, it is a very nice proof! $\endgroup$ – Mirko Nov 24 '14 at 0:33
1
+50
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ By "square of side-length 1"$ I guess you mean "square of side-length 1 with sides parallel to the coordinate axes"? I don't believe that's what the OP meant by "square". $\endgroup$ – bof Nov 16 '14 at 8:31
  • 1
    $\begingroup$ Ohhh, thank you very much. I knew this seemed too easy... $\endgroup$ – KidA424 Nov 16 '14 at 8:35
  • $\begingroup$ @Kid Thank you for your answer, I did mean that the sides of the squares could be oriented any way, need not be parallel to a coordinate axis. (For the interesting construction in this answer clearly the vertices of a square that has a side with slope 1 have only two colors, which does not answer the question as stated.) I also posted a comment,after my question to explain why it might be difficult. $\endgroup$ – Mirko Nov 16 '14 at 13:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.