Let $A$ be a finite set of positive reals, let $B = \{x/y\mid x,y\in A\}$ and let $C = \{xy\mid x,y\in A\}$. Show that $|A|\cdot|B|\le|C|^2$. (Proposed by Gerhard Woeginger, Austria)
Problem
Source: 2011 MMO Problem #2
Tags: ratio, inequalities, function, geometric sequence, combinatorics unsolved, combinatorics
24.09.2011 16:23
I'd like to prove this but I don't know how to multiply this sets.. Is there a rule or something for that? please some1 post solution or at least link for my question..
24.09.2011 16:49
ivanbart-15 wrote: I'd like to prove this but I don't know how to multiply this sets.. Is there a rule or something for that? please some1 post solution or at least link for my question.. $|A|$ means the number of elements of $A,$ so we do not multiply the sets, we multiply only their number of elements.
24.09.2011 16:55
Not that sets cannot be multiplied! The Minkowski notation for, say, sets $S,T \subseteq \mathbb{R}$ is $S\cdot T = \{st \mid s\in S, t \in T\}$; thus in Minkowski notation, in our problem we have $C = A\cdot A$.
25.09.2011 10:33
For each $b \in B$, write $n(b)$ for the number of pairs $(x,y) \in A\times A$ such that $\frac{x}{y}=b$. Now, pick an arbitrary $b \in B$. There are $n(b)$ pairs $\left(x_1,y_1\right)$, $\left(x_2,y_2\right)$, $\ldots$, $\left(x_{n(b)},y_{n(b)}\right)$ of elements in $A$ whose ratios $\frac{x_i}{y_i}$'s are all equal to $b$. Write $Y(b)$ for the set \[\big\{\left(ax_i,ay_i\right)|a \in A\text{ and }i=1,2,\ldots,n(b)\big\}\,.\] Trivially, $\big|Y(b)\big| \geq |A|$ and the $Y(b)$'s are disjoint. Ergo, using $\bigcup_{b \in B} Y(b) \subseteq C \times C$, we conclude that \begin{align*} |C|^2 = |C \times C| &\geq \left|\bigcup_{b \in B} Y(b) \right| = \sum_{b \in B} \big|Y(b)\big| \\ &\geq \sum_{b \in B} |A|= |A| \cdot |B|\,. \end{align*} The above inequality becomes an equality if and only if $|A|=1$. A stronger inequality is $|C|^2 \geq |A|\cdot|B|+2|A|^2-|A|-|B|$. The equality holds only when elements of $A$ form a geometric progression, where $|B|=|C|=2|A|-1$. To prove this inequality, we start with showing that $Y(b)$ has at least $|A|+n(b)-1$ elements. Next, we must show that $(C \times C) \setminus \left(\bigcup_{b \in B} Y(b)\right)$ contains at least $|A|^2-|A|$ elements. Finally, using $\sum_{b\in B} n(b) = |A|^2$, we arrive at the conclusion.
16.04.2013 14:18
For $b\in B$, let $b=x(b)/y(b)$ with $x(b),y(b)\in A$ be the representation of $b$ for which $x(b)$ is smallest. Construct a function $f:A\times B\to C\times C$ by defining for $(a,b)\in A\times B$ \[ f(a,b) ~=~ (a\cdot x(b),~ a\cdot y(b)). \] We show that $f$ is injective (which implies the desired inequality): Consider $(a_1,b_1)$ and $(a_2,b_2)$ in $A\times B$ with $f(a_1,b_1)=f(a_2,b_2)$. Then $a_1\cdot x(b_1)=a_2\cdot x(b_2)$ and $a_1\cdot y(b_1)=a_2\cdot y(b_2)$. Division yields $x(b_1)/y(b_1)=x(b_2)/y(b_2)$, and thus $b_1=b_2$. Then $a_1\cdot x(b_1)=a_2\cdot x(b_2)$ yields $a_1=a_2$. Hence $(a_1,b_1)=(a_2,b_2)$, and $f$ is indeed injective.