# Is it possible to cover all pairs of points at distance at most 1 by constant number of partitions into sets of diameter at most 1?

Let $n$ be a natural number and let $S_n$ be a square $[0,n] \times [0,n]$ in the plane.

We say that a partition $\mathcal{Q} = R_1 \cup \cdots \cup R_t$ of $S_n$ is simple if each of the sets $R_1, \ldots, R_t$ is connected, has positive area and has diameter at most 1.

Question. Does there exist a collection of at most $k$ ($k$ does not depend on $n$) simple partitions $\mathcal{Q}_1, \ldots, \mathcal{Q}_k$ of $S_n$ such that any two points $x,y \in S_n$ of distance at most 1 are contained in at least one of the sets of the partitions, that is there exist $i \in\{1, \ldots, k\}$ and a set $R \in \mathcal{Q}_i$ such that $x,y \in R$?

• Unlikely for $n \gt 2$. Pick a point that is in the interior of all of the sets R to which it belongs, and pick a point distance 1 away from that point. By the bounded diameter condition, these two points can't belong to the same part of any of the finitely many partitions. Gerhard "Or Is Your Question Different?" Paseman, 2015.12.01 – Gerhard Paseman Dec 1 '15 at 17:45
• An alternative question that might be asked is if any two points $x$ and $y$ of distance strictly less than 1 are contained in a single element of one of the partitions. I think the answer to that is no for similar reasons to those given by Gerhard Paseman. If, on the other hand, you ask that for a fixed $a<1$, that any two points $x$ and $y$ with $d(x,y)\le a$ belong to a single element of one of the partitions, the answer should be yes. – Anthony Quas Dec 1 '15 at 20:28
• what am i missing? - $s_1$ points being $(0,x),(1,x)$ – JMP Dec 1 '15 at 22:08

## 1 Answer

More generally, replace $S_n$ by $D$, a union of a collection of closed balls of nonzero radius, and suppose $D$ has diameter greater than 1. Consider partitions of $D$ which are bounded, so each set in a partition has diameter at most 1. Let us further assume that $D$ contains two open balls with centers $x$ and $y$ of distance exactly 1 from one another.

Consider the unit vector $v$ which is the difference of $x$ and $y$. Then the points $tv + x$ and $tv+y$ are also distance 1 apart. Let $R_t$ be the partition part which contains these two points. Then $R_t$ is different from $R_s$ when $t$ and $s$ are distinct real numbers sufficiently small. Thus continuum-many partition parts of diameter 1 are needed to cover just these pairs of points. In particular, more than countably many parts are needed, so finitely many partitions each with a finite number of parts is not enough. Thus we can't find a finite set of simple partitions for the poster even in the case of the unit square.

Gerhard "It's About Cardinality, Not Topology" Paseman, 2015.12.02

• Indeed, $D$ can be pretty woolly as long as it contains $x$ and $y$ at distance 1 and enough points $tv +x$ and $tv+y$, and something like Pythagorean Theorem holds to force $R_s$ distinct from $R_t$ by the boundedness condition. I'll leave the work of answering Anthony's version this way to others. Gerhard "Likes Reducing Proofs To Counting" Paseman, 2015.12.02 – Gerhard Paseman Dec 2 '15 at 21:11