Let $B_0=\{\frac{a}{b}\mid a,b\in A\}$. Obviously $B_0\subset B$. Suppose $B_0=\{k_1,k_2,\ldots,k_s\}\,,\, k_1<k_2\ldots < k_s$ and $n_1,n_2,\ldots,n_s$ be their corresponding multiplicities. Thus, $n_1=n_s=1\,,\, n_1+n_2+\ldots+n_s=|A|^{2}$. Suppose: $k_{j-1} =\frac{a'_1}{b'_1}=\ldots=\frac{a'_{n_{j-1}}}{b'_{n_{j-1}}}$ , where $a'_1< a'_2<\ldots<a'_{n_{j-1}}$ $k_j =\frac{a_1}{b_1}=\ldots=\frac{a_{n_j}}{b_{n_j}}$ , where $a_1< a_2<\ldots<a_{n_j}$ $k_{j+1} =\frac{a''_1}{b''_1}=\ldots=\frac{a''_{n_{j+1}}}{b''_{n_{j+1}}}$ , where $a''_1< a''_2<\ldots<a''_{n_{j+1}}$ It can be checked that: (i) $k_{j-1}<\frac{a'_1+a_j}{b'_1+b_j}<k_j\,,\, j=1,2,\ldots,n_{j}$ (ii) $ k_{j}< \frac{a_j+a''_1}{b_j+b''_1}< k_{j+1}\,,\, j=1,2,\ldots,n_{j} $ (iii) $\frac{a'_1+a_1}{b'_1+b_1}<\frac{a'_1+a_2}{b'_1+b_2}<\ldots<\frac{a'_1+a_{n_j}}{b'_1+b_{n_j}}$ (iiii) $\frac{a'_1+a_1}{b'_1+b_1}>\frac{a'_2+a_1}{b'_2+b_1}>\ldots > \frac{a'_{n_{j-1}}+a_1}{b'_{n_{j-1}}+b_1}$ Therefore $|B|\ge n_1+2n_2+1+ 2n_3+ \ldots + 2n_{s-1}+n_s = 2|A|^2-1 $, since $n_1=n_s=1$.

Sorry for being a little bit sloppy in the details. I think, I fixed it. Comment. Let us denote $B_0 =\{a_1+a_2\mid a_1,a_2\in A\}$. It is interesting to note that $|B_0 |\ge 2|A|-1$ and it is a sharp estimate; the equality holds when $A$ is an arithmetic progression. Also, knowing nothing apriori about $B_0$, we can only claim $|\{\frac{b_1}{b_2}\mid b_1,b_2\in B_0\} | \ge 2|B_0|-1$ , since the equality holds when $\{\ln b \mid b\in B_0 \}$ is an arithmetic progression. But nevertheless, as the problem claims, $|B|=\Omega(|A|^{2})$. Roughly speaking, it is due to impossibility $A$ and $\{\ln b \mid b\in B_0 \}$ simultaneously be arithmetic progressions.

This result has been published in this rather recent paper: http://arxiv.org/pdf/1402.5775v1.pdf

dibyo_99 wrote: This result has been published in this rather recent paper: http://arxiv.org/pdf/1402.5775v1.pdf In China you do not see: http://arxiv.org/pdf/1402.5775v1.pdf

I did not mean anything bad, sorry for the misunderstanding. I just happened to come across that paper, so I put it here. I didn't question the problem's originality or something. Sorry again anyway.

I mean, you stick it out to see. Thanks.

dgrozev wrote: Let $B_0=\{\frac{a}{b}\mid a,b\in A\}$. Obviously $B_0\subset B$. i don't think it's obvious. if $a+b$ not equal to $c (a,b,c \in A) $, $B_0$ won't be a subset of $B$.

Oh, but it is obvious. The claim is $B_0 \subset B$, not $B\subset B_0$. An element of $B_0$ is of the form $\dfrac {a}{b}$, with $a,b\in A$. But then $\dfrac {a}{b} = \dfrac {a+a}{b+b} \in B$. Don't let yourself be misled by the different roles $a,b,c,d$ may play ... (and they must not necessarily be distinct).

This is a very, very beautiful problem. The idea is to consider $\frac{A}{A}$, and then relate it to $\frac{A+A}{A+A}$. Also it is convenient to draw this in a cartesian plane, and consider slopes of lines. First, let $P = A\times A$ be a set of points on the plane. Now, this set can be covered by lines passing through the origin. Say there are $k$ lines: $l_1$, ..., $l_k$, and that line $l_i$ has $c_i$ points (that is, $l_i \cap P = c_i$). Clearly $\sum_{i=1}^k c_i = |A|^2$. Now, consider $P+P= (A+A) \times (A+A)$. We want to show that we need at least $2|A|^2-1$ lines passing through the origin to cover the points of $P+P$ (since the slope of each of these lines is an element of $B$). So consider two consecutive lines $l_x$ and $l_{x+1}$. Consider the points of $P$ in $l_x$, let them be $e_1, ..., e_m$ and let the elements of $P$ in $l_{x+1}$ be $f_1, ..., f_s$, where $m$ and $s$ are some integers (actually, $m=c_x$ and $s=c_{x+1}$). I want to determine how many lines (through the origin) are needed to cover $(l_x \cap P) + (l_{x+1} \cap P)$. To do this, draw a line parallel to $l_{x+1}$ through every point in $(l_x \cap P)$, and draw a line parallel to $l_x$ through every point in $(l_{x+1} \cap P)$. The $ms$ intersections of these lines will be the elements of $(l_x \cap P) + (l_{x+1} \cap P)$. All we must do now is take a look at the line through $e_1$ and the line through $f_1$. It becomes easy to see that we need at least $m+s-1$ lines to cover the points of $(l_x \cap P) + (l_{x+1} \cap P)$. Notice that these $m+s-1$ lines lie strictly between $l_x$ and $l_{x+1}$. Also notice that if we have $X \in P$, then $2X \in P+P$, and so, the line that covers $X$ in $P$ is also necessary to cover $2X$ in $P+P$. Also notice $c_1=c_k=1$. If $a=maxA$ and $b=minA$, the line $l_1$ will correspond to $(a,b)$ and the line $l_k$ will correspond to $(b,a)$. So, we know that to cover the points of $P+P$ we need at least: $k+(c_1+c_2-1)+(c_2+c_3-1)+...+(c_{k-1}+c_k-1) = k+2|A|^2-c_1-c_k-(k-1)=2|A|^2-1$, lines, so we're done!

JuanOrtiz wrote: This is a very, very beautiful problem. The idea is to consider $\frac{A}{A}$, and then relate it to $\frac{A+A}{A+A}$. Also it is convenient to draw this in a cartesian plane, and consider slopes of lines. First, let $P = A\times A$ be a set of points on the plane. Now, this set can be covered by lines passing through the origin. Say there are $k$ lines: $l_1$, ..., $l_k$, and that line $l_i$ has $c_i$ points (that is, $l_i \cap P = c_i$). Clearly $\sum_{i=1}^k c_i = |A|^2$. Now, consider $P+P= (A+A) \times (A+A)$. We want to show that we need at least $2|A|^2-1$ lines passing through the origin to cover the points of $P+P$ (since the slope of each of these lines is an element of $B$). So consider two consecutive lines $l_x$ and $l_{x+1}$. Consider the points of $P$ in $l_x$, let them be $e_1, ..., e_m$ and let the elements of $P$ in $l_{x+1}$ be $f_1, ..., f_s$, where $m$ and $s$ are some integers (actually, $m=c_x$ and $s=c_{x+1}$). I want to determine how many lines (through the origin) are needed to cover $(l_x \cap P) + (l_{x+1} \cap P)$. To do this, draw a line parallel to $l_{x+1}$ through every point in $(l_x \cap P)$, and draw a line parallel to $l_x$ through every point in $(l_{x+1} \cap P)$. The $ms$ intersections of these lines will be the elements of $(l_x \cap P) + (l_{x+1} \cap P)$. All we must do now is take a look at the line through $e_1$ and the line through $f_1$. It becomes easy to see that we need at least $m+s-1$ lines to cover the points of $(l_x \cap P) + (l_{x+1} \cap P)$. Notice that these $m+s-1$ lines lie strictly between $l_x$ and $l_{x+1}$. Also notice that if we have $X \in P$, then $2X \in P+P$, and so, the line that covers $X$ in $P$ is also necessary to cover $2X$ in $P+P$. Also notice $c_1=c_k=1$. If $a=maxA$ and $b=minA$, the line $l_1$ will correspond to $(a,b)$ and the line $l_k$ will correspond to $(b,a)$. So, we know that to cover the points of $P+P$ we need at least: $k+(c_1+c_2-1)+(c_2+c_3-1)+...+(c_{k-1}+c_k-1) = k+2|A|^2-c_1-c_k-(k-1)=2|A|^2-1$, lines, so we're done! WAY TOO BEAUTIFUL

Very nice problem. Let $a_1, a_2, \dots, a_n$ be the elements of $A$, and consider the vectors $\mathbf v_{ij} = [a_i, a_j]$. For example, for $A = \{1, 2, 3\}$, the vectors $\mathbf v_{ij}$ are plotted in blue in the following picture: [asy][asy] size(7cm); draw((0,6)--(0,0)--(6,0)); for (int z=1; z<=6; ++z) { draw((0,z)--(6,z)); draw((z,0)--(z,6)); } for (int x=2; x<=6; ++x) { for (int y=2; y<=6; ++y) { draw((0,0)--(x,y), grey); dot((x,y)); } } for (int x=1; x<=3; ++x) { for (int y=1; y<=3; ++y) { draw((0,0)--(x,y), blue); dot((x,y)); } } [/asy][/asy] It suffices to show that there are $2n^2-1$ pairwise linearly independent (gray) vectors of the form $\mathbf v_{ij} + \mathbf v_{k\ell}$. Reindex the vectors as $\mathbf v_1, \mathbf v_2, \dots, \mathbf v_r$ with slopes in decreasing order, and let there be $k_i$ points on vector $\mathbf v_i$. Now, consider any pair of vectors $\mathbf v_i$ and $\mathbf v_{i+1}$; let $\mathbf w_i$ and $\mathbf w_{i+1}$ be the ``unit" vectors of $\mathbf v_i$ and $\mathbf v_{i+1}$; in other words, they point in the same direction to an element of $A$ with shortest possible magnitude. Then, consider the set of vectors given by $$\{\mathbf w_i + \mathbf w_{i+1}, 2\mathbf w_i + \mathbf w_{i+1}, \dots, k_i \mathbf w_i+\mathbf w_{i+1}, \mathbf w_i + 2\mathbf w_{i+1}, \dots, \mathbf w_i + k_{i+1} \mathbf w_{i+1}\}.$$Observe that because $\mathbf w_i$ and $\mathbf w_{i+1}$ are linearly independent by definition, $a\mathbf w_i + b\mathbf w_{i+1}$ and $c\mathbf w_i+d\mathbf w_{i+1}$ are linearly dependent if and only if $[a, b]$ and $[c, d]$ are also linearly dependent. In particular, all $k_i+k_{i+1} - 1$ vectors in the set must be linearly independent. In particular, we can find $$|B| \geq \sum_{i=1}^{r-1} k_i+k_{i+1} - 1 = 1 + 2(k_1+k_2+\cdots + k_r) - k_1-k_r = 2n^2 - 1$$because $k_1=k_r = 1$ and there are $n^2$ points in total, as needed.

Basically we're taking a $n \times n$ grid symmetric over $y=x$ and taking the midpoint of every pair of points along with the grid itself, then connecting all of them to the origin, then seeing how many distinct lines there are. The key lemma is that if we have two rays, and two moving points along both of them, then the median is always between the two rays, and moves in the same direction when one point is moved up as when the other point is moved down. This is done by considering the homothety at the fixed point. Now to solve the problem, draw rays from the origin to all $n^2$ points of the original grid, forming $k$ distinct rays with $a_1,a_2,\dots,a_k$ points on each ray, in order. Now between rays $i,i+1$ we may get $a_i+a_{i+1}-1$ distinct medians between them, by starting with the far point on ray $i$ and the close point on ray $i+1,$ then moving down from the far point to the closest point on ray $i,$ then moving up from the closest point to the far point on ray $i+1.$ Summing this over all $i$ gives $2(a_1+a_2+\dots+a_k)-a_1-a_k-(k-1)$ distinct median rays, and we may add back our $k$ original rays to give $2(a_1+a_2+\dots+a_k)-a_1-a_k+1.$ But now $a_1+a_2+\dots+a_k=n^2,$ and $a_1=a_k=1$ by considering extremality. Thus this gives $2n^2-1$ distinct rays, and we are done.