Assume that $C$ is a convex subset of $\mathbb R^{d}$. Suppose that $C_{1},C_{2},\dots,C_{n}$ are translations of $C$ that $C_{i}\cap C\neq\emptyset$ but $C_{i}\cap C_{j}=\emptyset$. Prove that \[n\leq 3^{d}-1\] Prove that $3^{d}-1$ is the best bound. P.S. In the exam problem was given for $n=3$.
Problem
Source: Iranian National Math Olympiad (Final exam) 2006
Tags: geometry, geometric transformation, vector, trigonometry, dilation, ratio, real analysis
14.09.2006 08:53
$C$ should be measurable and its measure should not be zero.
14.09.2006 23:44
But every convex set is measurable. I don't think measure zero is necessary, since then it will just be a lower dimensional convex set.
15.09.2006 16:29
This is just a try of partial-pseudo-proof. Call the space in which we are moving, whose elements are vectors, $S$. Let $C_{i}=C+v_{i}=\{x\in S| \exists y\in C,\; y+v_{i}=x \}$. We will change all the $C_{i}$ and $C$ by $C^{*}= \{ \frac{x-y}{2}|x,y\in C\}|$, $C^{*}_{i}=C^{*}+v_{i}$; it's easy to see that $C^{*}$ is simmetrical with respect to the origin (in fact I have seen this tecnique in "Proofs from the Book" and is called Minkowsky simmetrization, I think). $C^{*}$ is also convex, since for any $0<p,q<1$ such that $p+q=1$, for any $x,y,w,z\in C$, $p\frac{x-y}{2}+q\frac{w-z}{2}=\frac{(px+qw)-(py+qz)}{2}\in C*$, which comes from the fact that $(px+qw),(py+qz)\in C$. Furthermore $C_{i}\cap C_{j}=\emptyset \Leftrightarrow C^{*}_{i}\cap C^{*}_{j}=\emptyset$ (consider $C_{0}=C$ with $v_{0}=0$). Indeed for $x,y,z,v\in C$, $\frac{x-y}{2}+v_{i}=\frac{w-z}{2}+v_{j}\Leftrightarrow \frac{x+z}{2}+v_{i}=\frac{w+y}{2}+v_{j}$, and the convexity of $C$ implies $\frac{x+z}{2}\in C, \;\frac{w+y}{2}\in C$. So the new sets continue to satisfy the hipothesis conditions. Now for $1\leq i\leq n$, for any $\epsilon$ with $1>\epsilon>0$ we can change in the previous formula for the $C^{*}_{i}$, $v_{i}$ for a vector $v'_{i}=k_{i}v_{i}$ with $k_{i}\geq 1$ such that the resulting $C'_{i}$ has still nonempty intersection with $C^{*}$, but (V: d-volume) $V(C^{*}\cup \bigcup_{i=1}^{n}C'_{i})\geq (n+1-\epsilon)V(C^{*})$ . Of course, since the distance between the centers of any two $C'_{i},\;C_'{j}$ is greater than that between the centers of $C^{*}_{i},\;C^{*}_{j}$ as their respective distances to the origin are greater (due to cosine theorem), we will still have $C'_{i}\cap C'_{j}=\emptyset$. Now, since the sets are simmetrical, for each $v'_{i}$, ${\frac{v'_{i}}{2}}\in C^{*}$, and so for each $x\in C^{*}$, $\frac{v'_{i}+x}{3}=\frac{2}{3}\frac{v'_{i}}{2}+\frac{1}{3}x\in C^{*}$, since it belongs to one segment joining two points of $C^{*}$. This means that if we make a dilation of ratio $\frac{1}{3}$ from the origin, the union of all the resulting sets will be contained in $C^{*}$, and so: $V(C^{*})\geq (\frac{1}{3})^{d}V(C^{*}\cup (\bigcup_{i=1}^{n}C'_{i}) )=(\frac{1}{3})^{d}(n+1-\epsilon)V(C^{*})$ And by just taking $\epsilon$<1 (actully it is somehow superfluous now that I think of it) this means: $n\leq 3^{d}-1$ [Hope I wont edit it any more. ]