"$2$ times or $3$ times" what? And, is $0$ considered to be a natural number? Also, don't post problems indiscriminately in any forum. I have moved your three posts for the Zhautykov in the corresponding forums, with the subsection being "Proposed and Own", not "Unsolved", as they were part of a competition. EDIT. The original statement has been corrected, according with the clarifications in the following post.

original statement Given 100 different positive integers. We call a pair of numbers good if the ratio of these numbers is either 2 or 3. What is the maximum number of good pairs that these 100 numbers can form ?(A number can be used in several pairs.)

mavropnevma wrote: "$2$ times or $3$ times" what? And, is $0$ considered to be a natural number? Also, don't post problems indiscriminately in any forum. I have moved your three posts for the Zhautykov in the corresponding forums, with the subsection being "Proposed and Own", not "Unsolved", as they were part of a competition. Sorry , I'm not good user so I didn't know that and thank you MUSAHON for your understanding

Wow, why 100=10^2? i think answer is 180.

Like often in Russian problems, numbers are used instead of generic values. Let us therefore denote $10 = n>1$, $2=k>1$, $3=\ell>1$, with the extra condition that both $k$ and $\ell$ are not simultaneously powers of a same number. Consider the digraph $G$ whose set of vertices $V(G)$ is made of $v=n^2$ distinct positive integers, and whose set of edges $E(G)$ is made by the pairs $(a,b) \in V(G)\times V(G)$ with $a\mid b$. For each positive integer $m$ consider now the (not induced) spanning subdigraph $G_m$ of $G$ (with $V(G_m) = V(G)$ and so $v_m = v=n^2$ vertices), and whose edges are the pairs $(a,b) \in G\times G$ with $b=ma$. Moreover, it is clear that $E(G_{m'}) \cap E(G_{m''}) = \emptyset$ for $m'\neq m''$ (since if $(a,b) \in E(G)$ then $(a,b) \in E(G_{b/a})$ only), and also $\displaystyle \bigcup_{m\geq 1} E(G_m) = E(G)$ (but that is irrelevant). Since the good pairs are precisely the edges of $G_k$ and $G_\ell$ together, we need to maximize their number $g$. A digraph $G_m$ is clearly a union of some $n_m$ disjoint (directed) paths $P_{m,i}$, with lengths $\lambda(P_{m,i}) = \lambda_{m,i}$, $0\leq \lambda_{m,i} \leq n^2-1$, such that $\displaystyle \sum_{i=1}^{n_m} (\lambda_{m,i} + 1) = n^2$, and containing $\displaystyle e_m = \sum_{i=1}^{n_m} \lambda_{m,i}$ edges ($0$-length paths, i.e. isolated vertices, are possible, allowed, and duly considered). The defect of the graph $G_m$ is taken to be $\displaystyle v - e_m = n_m$. We therefore need to maximize $g = e_k+e_\ell$, or equivalently, minimize $\delta = n_k+n_\ell$. Using the model $V(G) = V_x = \{k^{i-1}\ell^{j-1}x \mid 1\leq i,j\leq n\}$, we have $n_k = n_\ell = n$, therefore $\delta = 2n$, so $\boxed{g = 2n(n-1)}$. To prove value $2n$ is a minimum for $\delta$ is almost obvious. We have $\lambda_{k,i} \leq n_\ell - 1$ for all $1\leq i \leq n_k$ (by the condition on $k$ and $\ell$ we have $|P_{k,i}\cap P_{\ell,j}| \leq 1$ for all $1\leq i\leq n_k$ and $1\leq j\leq n_\ell$), so $\displaystyle n^2 - n_k = e_k = \sum_{i=1}^{n_k} \lambda_{k,i} \leq \sum_{i=1}^{n_k}(n_\ell-1) = n_kn_\ell - n_k$, therefore $n^2 \leq n_kn_\ell$, and so $\delta = n_k+n_\ell \geq 2\sqrt{n_kn_\ell} = 2n$. Moreover, we see equality occurs if and only if $n_k=n_\ell=n$ and $\lambda_{k,i} = \lambda_{\ell,i} = n-1$ for all $1\leq i \leq n$, thus only for the sets $V_x$ described above. Once the idea dawns on us, the problem is quite trivial, the technical details being almost "forced" upon us.

Sorry! I was wrong! That is my answer: There are 9 columns at the left of $10^{th}$ column and9 columns at the right of $10^{th}$ column. => There are $(1+2+\cdots+9)+10+(9+8+\cdots+1)=100$ numbers. There are $(2+4+\cdots+18)+(18+\cdots+4+2)=180$ lines where one line is one pair of good numbers. You can see it from picture! Answer is 180!!!

Attachments:

Can somebody solve it (mavropnevma I didn't understand your solution)? I couldn't find fully its solution.

Construction for $180$: Take all numbers in the form $2^i3^j$ for $i,j \in [0,9]$. mavropnvema is basically turning the set of numbers and the "good pair" relation into a graph, and analyzing it instead.

Since we are looking for a maximal number of pairs where $\frac{x_i}{x_j}$ equals $2$ or $3$, we will represent each number in a form $2^{a_i}*3^{b_i}*c_i$, where $c_i$ is relatively prime to both $2$ and $3$. Since $c_i$ can only make our ratio differ from $2$ and $3$, we will let all $c_i$ be equal to $1$ in order to maximize the number of the described pairs. Now, if $\frac{x_i}{x_j} = 2$ we have that $a_i=a_j+1$ and $b_i=b_j$, and if $\frac{x_i}{x_j} = 3$ we must have $a_i=a_j$ and $b_i=b_j+1$. Let us now order all $a_i$'s in an increasing sequence, having $a_1'<=a_2'<=...<=a_{100}'$. In this sequence let us have $k$ groups of equal elements. As we may have that $\frac{x_i}{x_j}=2$ if $a_i=a_j+1$, this ratio can occur only with two numbers from different groups whose difference of respective values of $a$'s is equal $1$. As it does not influence the total number of pairs with $\frac{x_i}{x_j}=3$ (since it can only occur if the respective values of $a$'s are equal) we will take that as $a$ grows from one group to other it increases by 1. Now, let the number of elements of these $k$ groups be $p_1, p_2, ... , p_k$, and we know that $p_1+p_2+...+p_k=100$ as we have $100$ numbers in total. Since $\frac{x_i}{x_j}=3$ can only occur if respective $a$'s are equal we will take that in each of our groups $b$'s increase by 1, so the maximal number of pairs with $\frac{x_i}{x_j}=3$ is $N(3)=p_1-1+p_2-1+...+p_k-1=(p_1+p_2+...+p_k)-k=100-k.$ As for the pairs with $\frac{x_i}{x_j}=2$, They must occur with numbers from the two consecutive groups of $a$'s (those whose $a$'s differ by 1), and since all given numbers are distinct we have that each number from one group can be paired with at most one number from other group, so for two consecutive groups number of pairs with $\frac{x_i}{x_j}=2$ is $min(p_i,p_{i+1})$. And now we get that the maximal number of pairs with $\frac{x_i}{x_j}=2$ is: $N(2) = min(p_1,p_2) + min(p_2,p_3) + ... + min(p_{k-1},p_{k})= \frac{p_1+p_2}{2} - |\frac{p_1-p_2}{2}| + ... + \frac{p_{k-1}+p_{k}}{2} - |\frac{p_{k-1}-p_{k}}{2}| = 100 - \frac{p_1+p_{k}}{2} - |\frac{p_1-p_2}{2}| - ... - |\frac{p_{k-1}-p_{k}}{2}| <= 100 - max(p_1,p_2,...,p_k) <= 100 - 100/k$. Now, the maximal number of pairs is: $N = N(2) + N(3) <= 100 - k + 100 - 100/k = 200 - k - 100/k <= 180$ (AG inequality). Finally we have proven that the maximal number of the described pair is not larger than $180$, and an example that it can be reached was already given by chaotic_iak.

A solution for those like me that think best with visualizations: As shown above, we can reduce the problem to the case that all numbers are a power of 2 times a power of 3. Now we can plot all the numbers on an infinite grid of unit squares, with row $i$ column $j$ corresponding to $2^i 3^j$. We want to select 100 of the unit squares and maximize the number of horizontal and vertical edges with both touching squares selected. Call such edges good. For example, the (smaller) set $\{1, 2, 3, 4, 6, 18, 72, 216\}$ would become XX.. XXX. X... ..XX with 7 good edges. Suppose there are $r$ different rows with selected numbers. For each good vertical edge, we can associate it to the number to its left, and this is one-to-one. But then the rightmost number in each row cannot have an associated edge, so we have at most $100 - r$ vertical edges as an upper bound. Similarly, if there are $c$ different columns with selected numbers, we have at most $100 - c$ horizontal edges, by associating edges with the number above. We want to maximize the number of horizontal and vertical edges, so we must maximize $200 - r - c$. All 100 numbers are contained in the intersection of $r$ rows and $c$ columns, so we have the constraint that $rc \geq 100$. By AM-GM, \[ 200 - r - c = 200 - (r+c) \geq 200 - 2\sqrt{rc} \geq 200 - 20 = 180. \] Equality in all our bounds is achievable with the simple example of a 10 by 10 square. So 180 is the answer.

The above is more in line with the official solution, transposing the problem into a configuration of latticeal points. However, if we replace $2$ and $3$ by $k$ and $\ell$, with the condition that both $k$ and $\ell$ are not simultaneously powers of a same number (like in my post), the mapping to latticeal points is debatable (a positive integer $n$ may have more than one representation $n=k^{i}\ell^{j}m$ with $k\nmid m$ and $\ell \nmid m$).

Here's a sketched solution with a different (but also natural) graph interpretation. (Hopefully me or somebody else can find a way to reduce the amount of brute-force needed for a rigorous solution.) An easy to see example with $2 \cdot 9 \cdot (9+1) = 180$ pairs is $\{2^i3^j | 0 \leq i,j \leq 9\}$. Call the given set of $100$ integers $S$ and form an directed edge between any two with ratio $2$ or $3$ (pointing from the smaller one to the larger one). We may replace each $2^i3^jx$ with just $2^i3^j$ in which case the number of pairs (edges) does not decrease - hence assume that all numbers in $S$ are of the form $2^i3^j$. Put the number $2^i3^j$ in the box with label $i+j$ if it belongs to $S$. To visualize the argument better, arrange the boxes $0$, $1$, $2, \ldots$ in a row. Suppose that exactly $n$ different boxes are non-empty, say $k_1<k_2<\ldots<k_n$ and let $a_1$, $a_2$, $\ldots$, $a_n$ be the number of elements in $S$ in them. The given condition implies $\sum_{i=1}^n a_i = 100$. Note that if two numbers are connected by an edge, then they have to be in adjacent boxes (since $2^i3^j$ is in $i+j$, $2^i3^{j+1}$ and $2^{i+1}3^j$ are in $i+j+1$) and so from each number at most $2$ edges can start and each number can be an endpoint of at most $2$ edges; also an edge starts from the box with the smaller label and ends at the box with the larger one. So the number of edges between $k_i$ and $k_{i+1}$ is $0$ if $k_{i+1} > k_i + 1$ and otherwise it is at most $2\min(a_i, a_{i+1})$ (as from $k_i$ there can be at most $2a_i$ edges and to $k_{i+1}$ there can be at most $2a_{i+1}$ edges). Hence the overall number of edges is at most $$ 2\sum_{i=1}^{n-1}\min(a_i,a_{i+1}) = \leq 2\left(\sum_{i=1}^na_i - \max(a_1,\ldots,a_n)\right) = 200 - 2\max(a_1,\ldots,a_n).$$(The last inequality could be thought of as when summing $\min(a_i,a_{i+1})$ you always use the smaller number and so you will surely not use the largest among all; a rigorous proof follows from $\min(a,b) \leq \frac{a+b + |a-b|}{2}$.) Hence if there is a box with at least $10$ numbers we already get the bound $180$. Now if there is a box with $9$ numbers but none with $10$ or more, we get the bound $182$ but we can reduce it to $180$ by noting that if $a_i = a_{i+1}$, then there are at most $2a_i - 1$ edges between $k_i$ and $k_{i+1}$; also $a_i > a_{i+1} < a_{i+2}$ is worse than $a_i < a_{i+1} < a_{i+2}$, etc. The cases of $\max = 8$ or lower are similar.

I think about this problem solution : $x,2x,6x,3x,9x,18x,27x, ........ $ $O.Y.SH.$