Suppose that the boxes $B_1, . . . , B_n ⊂ R^d$ pairwise touch each other, that is, any two of them are separated and have a common boundary point. Prove that $n ≤ 2^d$
I am trying to use Brunn-Minkowski inequality for brick set and the concept of volume to solve this. Like I am taking a hyperplane H that exactly divide it into two equal parts so that $B_1,. .,B_\frac{n}{2}$ lies in one plane i.e. $H^+$ and $B_\frac{n}{2},..,B_n$ lies in $H^-$ plane. But I am unable to proceed from here. Is there any other method to do so? Any help is appreciated.
Thanks in advance.
I'm gonna keep this concise, so as it might be easy to verify it's correctness.
Theorem 1. Let $\mathcal{B}$ be any finite set of boxes in $\mathbb{R}^d$ which satisfy the property that any pair of distinct boxes are separated and share boundary points. Then $ \bigcap_{B \in \mathcal{B}} \partial B \neq \varnothing$.
Proof. Use strong induction on $d$.
Induction Step: Let $s \geq 1$ . Given that any set of boxes $\mathcal{B}$ from $\mathbb{R}^t (1 \le t \le s)$ which are pairwise separated and pairwise share boundary points satisfy $ \bigcap_{B \in \mathcal{B}} \partial B \neq \varnothing$, we need to show that any set of boxes $\mathcal{B}'$ from $\mathbb{R}^{s+1} $ which are pairwise separated and pairwise share boundary points satisfy $ \bigcap_{B \in \mathcal{B}'} \partial B \neq \varnothing$
Let $n := |\mathcal{B}'|$. To prove this for $n \geq 2$, we use strong induction on $n$.
Induction Step: Let $2 \le k \le n$. Given that any $k$ set of boxes of $\mathbb{R}^{s+1}$ (call it $\mathcal{B}$) which are pairwise separated and pairwise share boundary points satisfy $ \bigcap_{B \in \mathcal{B}} \partial B \neq \varnothing$, we need to show that any $k+1$ set of boxes of $\mathbb{R}^{s+1}$ which are pairwise separated and share boundary points have a non-empty intersection of their boundaries.
Let $\mathcal{B}'$ be any $k+1$ set of boxes of $\mathbb{R}^{s+1}$ which are pairwise separated and pairwise share boundary points. Let $B_0 \in \mathcal{B}'$. Consider all $k$ sized subsets of $\mathcal{B}'$ which contains $B_0$. There are $k$ such subsets, denote them by $\mathcal{B}_1$, $\mathcal{B}_2$, .. $\mathcal{B}_k$. By the inner induction hypothesis then there exists $k$ faces $F_1$, $F_2$, ... $F_k$ of $B_0^c$ which are the least dimensional faces of $B_0^c$ containing the intersection of the boxes in $\mathcal{B}_1$, $\mathcal{B}_2$, .. $\mathcal{B}_k$ respectively.
Claim $\bigcap_{i = 1}^k F_i \neq \varnothing$
Lemma 1. For any $i \neq j$, $F_i \cap F_j \neq \varnothing$.
Proof. There exists boxes $B_1, B_2$ s.t. $B_1 \in \mathcal{B}_i \setminus \mathcal{B}_j$ and $B_2 \in \mathcal{B}_j \setminus \mathcal{B}_i$. If $F_i \cap F_j = \varnothing$, then $B_1$ and $B_2$ cannot share a boundary point (because if two boxes share a face, then there doesn't exist any other box, which shares two disjoint faces with each of these boxes i.e. $B_0$ can't exist). This is a contradiction.
Lemma 2. Let $k_0 = \min_{k} (dim F_k)$. There exists $A \subseteq \{ F_1, F_2 , ... F_k \}$ such that $F \in A \Rightarrow \dim F = k_0$ and $\bigcap_{F \in A} = \bigcap_{i=1}^k F_i$
Proof. As $F_i \cap F_j \neq \varnothing$, if $F_i$ has dimension less than $F_j$, then $F_i \subset F_j$. Hence we can remove $F_j$ from the set.
Now if $\bigcap_{F \in A} = \varnothing$, then all faces in $A$ are separable. In this case, we may use the induction hypothesis of outermost induction, to get $\bigcap_{F \in A} \neq \varnothing$, which is a contradiction. This proves the claim.
And the claim implies that induction hypothesis. Qed.
Theorem 2. Let $\mathcal{B}$ be a set of boxes in $\mathbb{R}^d$ which are separated and satisfy $ \bigcap_{B \in \mathcal{B}} \partial B \neq \varnothing$. Let $B_0 \in \mathcal{B}$ such that $n$ ($0 \le n < d$) is the minimum dimension of a face of $B_0$ which contains $ \bigcap_{B \in \mathcal{B}} \partial B$. Then $$|\mathcal{B}| \le 2^{d-n}$$ Proof (simple counting argument on the $\mathbb{R}$ intervals of the boxes, given they have a common $n$ dimensional face). Qed.
Final Proof. Use Theorem 1 and Theorem 2 to show that $\mathbb{R}^n$ cannot have $> 2^n$ boxes which are pairwise separable and pairwise share boundary points (use contradiction).