Let $\,S\,$ be a finite set of points in three-dimensional space. Let $\,S_{x},\,S_{y},\,S_{z}\,$ be the sets consisting of the orthogonal projections of the points of $\,S\,$ onto the $yz$-plane, $zx$-plane, $xy$-plane, respectively. Prove that \[ \vert S\vert^{2}\leq \vert S_{x} \vert \cdot \vert S_{y} \vert \cdot \vert S_{z} \vert, \] where $\vert A \vert$ denotes the number of elements in the finite set $A$.
HIDE: Note Note: The orthogonal projection of a point onto a plane is the foot of the perpendicular from that point to the plane.Problem
Source: IMO 1992, Day 2, Problem 5
Tags: combinatorics, combinatorial geometry, 3D geometry, projection, point set, IMO, IMO 1992
17.04.2006 15:44
Let us use a combinatorial reasoning. Let us denote by $ V_{ij}$ the set of the points of $ V$ of the form $ (x, i, j)$, that is, the set of the points of $ V$ who are projected on the plane $ yz$ at the point $ (i, j)$. We thus have : $ V = \bigcup_{(i,j) \in V_x} V_{ij}$, hence : \[ |V| \le \sum_{(i,j) \in V_x} |V_{ij}|, \] and, thanks to the Cauchy-Schwarz's inequality : \[ |V|^2 \le \sum_{(i,j) \in V_x} 1^2 \cdot \sum_{(i,j) \in V_x} |V_{ij}|^2 = |V_x| \cdot \sum_{(i,j) \in V_x} |V_{ij}|^2. \] We look for a set $ X$ such that $ |X| = \sum_{(i,j) \in V_{ij}} |V_{ij}|^2$. It is plain that the set : \[ X = \bigcup_{(i,j) \in V_x} (V_{ij} \times V_{ij}) \] does the trick. Moreover, the application $ f : X \to V_y \times V_z$ defined by : \[ f((x, i, j),(x', i, j)) = ((x, j), (x', i)) \] is one-to-one, so $ |X| \le |V_y| \cdot |V_z|$, hence the result.
26.02.2012 18:40
For reals $x,y,z$, define $a_{xy}=[(x,y,0)\in S_z]$, $b_{yz}=[(0,y,z)\in S_x]$, and $c_{zx}=[(x,0,z)\in S_y]$. Then $S\subseteq\{(x,y,z)\in\mathbb{R}^3: a_{xy}b_{yz}c_{zx}=1\}$ (and this "maximal" set can be achieved), so we need to show that \[\left(\sum_{\mathbb{R}^3}a_{xy}b_{yz}c_{zx}\right)^2\le \left(\sum_{\mathbb{R}^2}a_{xy}\right)\left(\sum_{\mathbb{R}^2}b_{yz}\right)\left(\sum_{\mathbb{R}^2}c_{zx}\right).\]But by Cauchy-Schwarz and the fact that $t=t^2$ for $t\in\{0,1\}$, \begin{align*} \left(\sum_{x,y,z}a_{xy}b_{yz}c_{zx}\right)^2 &=\left(\sum_{x,y}a_{xy}\sum_{z}b_{yz}c_{zx}\right)^2 \\ &\le\left(\sum_{x,y}a_{xy}^2\right)\left(\sum_{x,y}\left(\sum_{z}b_{yz}c_{zx}\right)^2\right) \\ &\le\left(\sum_{x,y}a_{xy}^2\right)\left(\sum_{x,y}\left(\sum_{z}b_{yz}^2\right)\left(\sum_{z}c_{zx}^2\right)\right) \\ &=\left(\sum_{x,y}a_{xy}\right)\left(\sum_{y}\left(\sum_{z}b_{yz}\right)\sum_{x}\left(\sum_{z}c_{zx}\right)\right) \\ &=\left(\sum_{x,y}a_{xy}\right)\left(\sum_{y,z}b_{yz}\right)\left(\sum_{z,x}c_{zx}\right), \end{align*}as desired. In fact, as in The Cauchy-Schwarz Master Class (by Steele), we can use the same method to prove the more general inequality \[\left(\sum_{\mathbb{R}^3}\sqrt{a_{xy}b_{yz}c_{zx}}\right)^2\le \left(\sum_{\mathbb{R}^2}a_{xy}\right)\left(\sum_{\mathbb{R}^2}b_{yz}\right)\left(\sum_{\mathbb{R}^2}c_{zx}\right),\]where $a_{xy},b_{yz},c_{zx}$ are any nonnegative reals; this is a special case of the Loomis-Whitney inequality.
13.03.2012 04:31
This can easily be extended to $n$- dimension. Problem: Let $\,S\,$ be a finite set of points in $\mathbb{R}^n$. Let $\,S_{1},\,S_{2},\, \ldots, S_{n}\,$ be the sets consisting of the orthogonal projections of the points of $\,S\,$ onto the $n$ cartesian planes respectively. Prove that $|S|^{n-1} \le \prod_{i=1}^{n} |S_i| $ Solution: We induct on number of points. For a point $a = (a_1, \ldots , a_n) \in S$, we have $(0,a_2 , \ldots , a_n) \in S_1$, $(a_1, 0,\ldots , a_n) \in S_2$ and so on. Take some $t$, and create two nonempty set $A$ and $B$ with elements of $S$ that have $a_i> t$, and with elements of $S$ have $a_i \le t $ respectively. (there exists at least one such $i$ ) So $|A| + |B| = |S|$, and $|A_j| + |B_j| = |S_j| $ , for all $j \ne i$, and obviously $|A_i|, |B_i| \le |S_i|$ By inductive hypothesis $|S|= |A| + |B| \le \prod_{i=1}^{n}|A_i|^{\frac{1}{n-1}}+ \prod_{i=1}^{n}|B_i|^{\frac{1}{n-1}}$ So $|S| \le \prod_{i=1}^{n}|A_i|^{\frac{1}{n-1}}+ \prod_{i=1}^{n}|B_i|^{\frac{1}{n-1}}$ $ \le |S_i|^{\frac{1}{n-1}} \left ( \prod_{\substack{j=1 \\ i \ne j}}^{n-1}|A_i|^{\frac{1}{n-1}}+ \prod_{\substack{j=1 \\ i \ne j}}^{n-1}|B_i|^{\frac{1}{n-1}} \right )$ $ \le |S_i|^{\frac{1}{n-1}} \cdot \prod_{\substack{j=1 \\ i \ne j}}^{n-1}\left ( |A_j| + |B_j| \right )^{\frac{1}{n-1}}$ $ = \prod_{i=1}^{n} |S_i|^{\frac{1}{n-1}} $ The last inequality follows from Hölder's inequality. So we get $|S|^{n-1}\le\prod_{i=1}^{n}|S_{i}|$, and the induction is complete.
24.05.2017 12:04
Let us bound the set $S$ between two horizontal planes (i.e. planes parallel to $xy$ plane) and begin to move down the upper one plane. Every time it meets some point/poins we denote that set of points by $S^k\,,\,k=1,2,\dots,m $, where of course $m\leq |S|$. Obviously, we have: $S_x=\sum_{i=1}^m S^i_x\,;\, S_y=\sum_{i=1}^m S^i_y\,;\, S_z\geq \max (S^i,i=1,\dots,m)\,,\, S^i \leq S^i_x\cdot S^i_y$. Here and below we may omit, for simplicity, the vertical lines $|\cdot|$ when denoting the number of elements of some set. Using it, we consecutively obtain: \begin{align*} |S_{x}|\cdot |S_{y}| \cdot |S_{z}| &\geq \sum_{i=1}^m S^i_x \cdot \sum_{i=1}^m S^i_y\cdot \max_{1\leq i\leq m} (S^i) \\ &\geq \left(\sum_{i=1}^m \sqrt{S^i_x S^i_y}\right)^2 \max (S^i) \geq \left(\sum_{i=1}^m \sqrt{S^i}\right)^2 \max (S^i) \\ &\geq \left(\sum_{i=1}^m S^i\right)^2 = |S|^2 \end{align*}(jumping from first to second line we used the Cauchy-Schwarz).
12.01.2018 04:28
There is a very nice proof of this inequality, using information-theoretic techniques, together with Han's inequality (subadditivity of entropy). Lemma: For random variables, $X,Y$, and $Z$, let, $H(X,Y,Z)$ denote their joint entropy, namely, $$ H(X,Y,Z)=\mathbb{E}\left[\log\frac{1}{P_{X,Y,Z}}\right], $$where, here, $P_{X,Y,Z}$ is treated as a random variable, taking the value, $\mathbb{P}(X=x,Y=y,Z=z)$; with probability, $P_{X,Y,Z}(x,y,z)$; and define the pairwise entropies similarly. Then, $$ H(X,Y)+H(X,Z)+H(Y,Z) \geq 2H(X,Y,Z). $$ Now, consider $n$-points in the space; a uniform probability measure (namely, each atom in the space, is charged with, $\frac{1}{n}$) on these $n$-points; and let, $(X,Y,Z)$ be the joint random variable, describing the coordinates of a single point. Using the entropy of a uniform random variable, we have, $H(X,Y,Z)=\log n$. Next, let, $n_1$, $n_2$; and $n_3$ be the cardinalities of the sets, obtained via projecting these $n$-points onto $yz$, $xz$, and $xy$-planes, respectively. Then, clearly, $H(X,Y)\leq \log n_3$, $H(X,Z)\leq \log n_2$, and, $H(Y,Z) \leq \log n_1$, since, a uniform distribution achieves the maximum entropy, subject to no constraints, and we do not know, whether we have a uniform or not. Now, observe what we have: \begin{align*} 2H(X,Y,Z) &=\log n^2 \\ & \leq H(X,Y)+H(X,Z)+H(Y,Z)\\ &\leq \log n_1 + \log n_2 + \log n_3\\ &=\log n_1n_2n_3\\ &\implies n\leq \sqrt{n_1 n_2 n_3}, \end{align*}done. $\square$
20.06.2019 06:39
Here is a funny solution which doesn't make use of Cauchy or Holder. First we will WLOG assume that all of $S$ is in the first octant, meaning that all points of $S$ have all coordinates strictly positive. Now, we will turn on gravity, which acts in the $-x$ direction. This means that all points which share $y-, z-$ coordinates will end up "stacked" on top of each other. The reason this is fine is that it preserves $|S|$ (number of points remains the same) and $|S_x|$ (number of stacks is the same), while $|S_y|$ and $|S_z|$ do not increase. Similarly, we can turn on gravity in the $-y$ and $-z$ directions. In this way, we can solve the rest of the problem under the assumption that if $(a, b, c) \in S$ for $a, b, c \in \mathbb{N}^3$ then $(a', b', c') \in S$ as well, whenever $1 \le a' \le a, 1 \le b' \le b, 1 \le c' \le c.$ Now, for each $(y,z) \in S_x$, let $x_{y,z}$ be the number of $x$ with $(x, y,z) \in S.$ Observe that from our assumption, $a \le c, b \le d$ implies that $x_{a, c} \ge x_{b, d}.$ Let $a, b \in \mathbb{N}$ be the least positive integers such that $S_x \subseteq [a] \times [b].$ This means that our inequality in question reduces to: $$(\sum_{(i, j) \in [a] \times [b]} x_{i, j})^2 \le t \cdot (\sum_{i = 1}^{a} x_{i, 1}) \cdot (\sum_{j=1}^{b} x_{1, j}),$$ of course subject to the conditions obtained via gravity, where $t$ is the number of $(i, j)$ with $x_{i, j}$ nonzero. We will prove that this inequality holds via induction on $|S|.$ Consider the effect of decreasing each of the $x_{i, j}$'s which are nonzero by one. We know by the inductive hypothesis that: $$(|S| - |S_x|)^2 \le |S_x| \cdot (|S_y| - a)(|S_z| - b).$$ Hence, if we could show that: $$|S|^2 - (|S| - |S_x|)^2 \le |S_x| (a \cdot |S_z| + b \cdot |S_y| - ab)$$ then we would be done by summing the two equations. After dividing by $|S_x|$, we wish to show that: $$2 |S| - |S_x| \le a \cdot |S_z| + b \cdot |S_y| - ab \Leftrightarrow (a \cdot |S_z| - |S|) + (b \cdot |S_y| - |S|) \ge ab - |S_x|.$$ It's immediate that $b \cdot |S_y| - |S| \ge 0$ from our prior assumption, so it suffices only to show that: $$a \cdot |S_z| - |S| \ge ab - |S_x|.$$ Note that $ab - |S_x|$ counts the number of $(i, j) \in [a] \times [b]$ with $x_{i, j} = 0.$ Hence, since we can write $a \cdot |S_z| - |S|$ as: $$\sum_{(i, j) \in [a] \times [b]} (x_{1, j} - x{i, j}),$$ we're done because it's clear that each $x_{i, j} = 0$ contributes at least one to the sum above. The induction is complete, and hence the problem is solved. $\square$
20.06.2019 17:39
Note that if there are points $(x,y,0)$, $(x,0,z)$, $(0,y,z)$ between the projections, then we may consider that $(x,y,z)\in S$. Let $T_x$ be the set of all $x$-coordinates of points in $S$, and define $T_y$, $T_z$ similarly. Consider a $3$-partite graph $G$ with parts $T_x$, $T_y$, $T_z$ and the edge between two vertices $x\in T_x$ and $y\in T_y$ iff $(x,y,0)\in S_x\cup S_y\cup S_z$, and similar condition for edges between $T_x$, $T_z$ and $T_y$, $T_z$. Note that the number of edges between $T_x$, $T_y$ equals $|S_z|$, similarly for $T_x$, $T_z$ and $T_y$, $T_z$, thus the number of triples $(e_{xy},e_{yz},e_{zx})$, where $e_{ij}$ is the number of edges between $T_i$ and $T_j$, equals $\vert S_{x} \vert \cdot \vert S_{y} \vert \cdot \vert S_{z} \vert$, and every triangle in this graph corresponds to a unique vertex in $S$. Thus, we need to prove that the square of the number of triangles in $G$ is not greater than $\vert S_{x} \vert \cdot \vert S_{y} \vert \cdot \vert S_{z} \vert$. We prove this by induction on the number of vertices in $G$. The base $|G|=1,2,3$ is trivial. Now, let the statement be proved for $|G|\le k$, and we need to prove it for $|G|=k+1$. Let $T_x=T_x'\cup{\nu}$, $G_1=G\setminus\nu$, $G_2=G\setminus T_x'$. By the induction hypothetis: \begin{align*} S_1^2&\le \vert S_{x} \vert \cdot \vert S_{y}' \vert \cdot \vert S_{z}' \vert\\ S_2^2&\le\vert S_{x} \vert \cdot \vert S_{y}'' \vert \cdot \vert S_{z}'' \vert, \end{align*}where $S_i$ is the numbet of triangles in $G_i$, $S_x$ is the number of edges between $T_y$, $T_z$ in $G_1$, $S_x'$ is the number of edges between $T_y$, $T_z$ in $G_2$, similarly for other constants (S_x=S_x'=S_x''). Then \begin{align*} S^2=(S_1+S_2)^2=|S_1|^2+|S_2|^2+2|S_1|\cdot |S_2| &\le\vert S_{x}\vert \cdot \vert S_{y}' \vert \cdot \vert S_{z}' \vert+\vert S_{x}\vert \cdot \vert S_{y}''\vert \cdot \vert S_{z}''| +|S_x|\cdot2\sqrt{ \vert S_{y}' \vert \cdot \vert S_{z}' \vert\cdot \vert S_{y}''\vert \cdot \vert S_{z}''|}\le\\ &\le \vert S_{x} \vert \cdot \vert S_{y}' \vert \cdot \vert S_{z}' \vert+\vert S_{x}'' \vert \cdot \vert S_{y}''\vert \cdot \vert S_{z}''| +|S_x|\cdot \vert S_{y}' \vert \cdot \vert S_{z}''|+|S_x|\cdot \vert S_{y}'' \vert \cdot \vert S_{z}'|=\\ &=|S_x|(|S_y|'+|S_y''|)(|S_z'|+|S_z''|)=|S_x|\cdot |S_y|\cdot |S_z|, \end{align*}what was required to be proved.
20.06.2019 18:26
I had posted the general inequality here https://artofproblemsolving.com/community/c7h1835173
05.10.2022 02:04
We use strong induction on $n$. The idea is to split $S$ into two smaller subsets $A$ and $B$ along a plane parallel to, say, the $xy$-plane. Without loss of generality let $|A_z| \geq |B_z|$. Then, we know that $|A_x| + |B_x| = |S_x|$, $|A_y| + |B_y| = |S_y|$, and $|S_z| \geq |A_z|$. Thus, using the strong inductive hypothesis on $A$ and $B$, \begin{align*} |S_x| \cdot |S_y| \cdot |S_z| &= (|A_x| + |B_x|)(|A_y| + |B_y|) |S_z| \\ &\geq |S_z|(\sqrt{|A_x||A_y|} + \sqrt{|B_x||B_y|})^2 \\ &\geq |S_z|\left(\sqrt{\frac{|A|^2}{|A_z|}} + \sqrt{\frac{|B|^2}{|B_z|}}\right)^2 \\ &\geq |A_z| \left(\frac 1{\sqrt{|A_z|}}(|A|+|B|)\right)^2 \\ &= |S_z| \cdot \frac 1{|A_z|} \cdot |S|^2 \\ &\geq |S|^2, \end{align*}which completes the induction.
06.11.2024 14:01
We proceed by strong induction on $n$. Divide the set $S$ into two disjoint sets $A, B$ by dividing it though a plane parallel to $xy$ plane (with both $A, B$ being non-empty). Note that this is possible (else all points lie in a plane parallel to $xy$ plane, contradiction). Thus: $|S| = |A|+|B|$ $$|A|^2 \le |A_x| |A_y| |A_z|$$$$|B|^2 \le |B_x| |B_y| |B_z|.$$Note that last two inequalities follows from inductive hypothesis. Thus: $$|S|^2 = (|A|+|B|)^2 \le ( \sqrt{|A_x| |A_y| |A_z|} + \sqrt{|B_x| |B_y| |B_z|})^2 $$$$\le |S_z| ( \sqrt{|A_x| |A_y| } + \sqrt{|B_x| |B_y|})^2$$$$\le |S_z| (|A_x|+|B_x|)(|A_y|+|B_y|)$$where the last step follows from Cauchy-Schwarz. Since the points are divided by a plane parallel to $xy$ plane, the projections of $A$ and $B$ into plane $xz$ or $yz$ are disjoint, which gives $|S_x| = |A_x|+|B_x|$ and $|S_y| = |A_y|+|B_y|$ and we are done