Let us call the $\ell\_1$-product of intervals $[0,k\_1]\times...\times [0,k\_n]$ a  *brick of size*  $k\_1+...+k\_n$. Consider a tessellation $T$ of $\mathbb{R^n}$ by (shifted) bricks so that every point belongs to at most $n+1$ bricks and the $\ell\_1$-distance between any two disjoint bricks is at least 1 (thus every two bricks can share only the boundary points). Let $s(T)$ be the maximal size of a brick in that tessellation. Let $s(n)$ be the minimum of all $s(T)$. For example, $s(1)=1$ (we tessellate $\mathbb{R}$ by intervals $[i,i+1]$), $s(2)\le 3$ (we can tessellate ${\mathbb R}^2$ by $2\times 1$-bricks so that each point belongs to at most 3 bricks). It is easy to have a tessellation with $s(T) \sim 2^n$, so $s(n)$ is at most exponential.


 **Question.**  What is $s(n)$? Does $s(n)$ grow exponentially with $n$?


 **Update**  It looks like the question is completely answered when we assume that all bricks are isometric by Will (upper bound) and Eric (lower bound). What if we tile by different bricks? How about arbitrary convex regions (same properties: every point belongs to at most $n+1$ regions, every two disjoint rejions are at distance at least 1, and, of course, different regions may share only boundary points)? Can we achive livear upper bound on the diameter of a tile? Can there be a constant upper bound?



Tessellating  $\mathbb{R}^n$ by bricks.
Edit: Per Tapio's answer, $1 \times 2 \times 3 \times ... \times n$ bricks always suffice, so $s(n)\leq \left(\begin{array}{c} n+1 \\ 2 \end{array}\right)$. Consider the lattice in $\mathbb Z^n$ defined by the equations $x\_1 \equiv x\_2$ mod $2$, $x\_2 \equiv x\_3$ mod $3$, ..., $x\_{n-1} \equiv x\_n$ mod $n$. Place a $1 \times 2 \times ... \times n$ bricks with one corner at each vertex of the lattice. This covers $\mathbb R^n$ because you first round $x\_1$ down to the nearest integer, then $x\_2$ down to the nearest multiple of two plus $x\_1$, .... The second condition is clearly satisfied, since the distance between any two bricks is an integer. We only need to check the first. Equivalently, we check that there cannot be $n+2$ lattice points in a single brick of the same size. Proof: Suppose there were. Then two of them would have to have the same value of $x\_n$ mod $n+1$. Since the $x\_n$ values of those two points lie in an interval of length $n$, they must be the same. So they have the same value of $x\_{n-1}$ mod $n$. By induction, they are identical. 


Is this bound sharp? For $n=1$, this is clear. Here is a proof for $n=2$. Form a graph where the faces are bricks, the the edges are the boundaries of bricks, and the vertices are places where two bricks intersect. Suppose that no brick is a hexagon or larger. Then the number of edges in a large reason is no more than $5/2$ the number of faces, and the number of vertices is exactly $2/3$ the number of edges, so the Euler number is at least $F -5/2(1-2/3)F=F/6$ which is $O$ of the area of the region, where it should be $O$ of the boundary. Or "the graph is somewhere between a cube and a dodecahedron, but nowhere near an infinite plane"


Therefore, some face has at least 6 edges. Each edge has length and least $1$, since the two vertices can share at most two faces, so the other faces at each vertex are nonadjacent, so have distance at least $1$. Therefore the perimeter of some face is at least $6$. The perimeter of $[0,a]\times [0,b]$ is of course $2(a+b)$, so $s(2)\geq 3$. There is an explicit example with $s(T)=3$, so we are done.


Obviously parts of this argument generalize to higher dimensions, but it is not clear to me if one can patch up the other parts to make it usable.


