# Positive integers $d_1$, $d_2$, $\ldots$, $d_n$ divide $1995$. Prove that, for some $i,j$, the numerator of $\dfrac{d_i}{d_j}$ is at least $n$.

(Probably Correct Statement) Distinct positive integers $d_1$, $d_2$, $\ldots$, $d_n$ divide $1995$. Prove that, for some indices $i,j\in\{1,2,\ldots,n\}$, the numerator of the reduced fraction $\dfrac{d_i}{d_j}$ is at least $n$.

Well, the 16 divisors of 1995 are 1 3 5 7 15 19 21 35 57 95 105 133 285 399 665 1995. So, everything starting from 19/1(or, if you want quotient to be greater than 1, from 95/3) suits. But how to make it more general?

• What did you try? – Parcly Taxel Aug 25 '17 at 17:35
• I just rolled back an edit because I saw no conceivable justification for the changes that were made. The included image is clear about what the statement of the question is. – David K Aug 25 '17 at 17:40
• Remarks: (1) The notation $d_1\mid d_2\mid \ldots \mid d_n\mid 1995$ means $d_1\mid d_2$, $d_2\mid d_3$, $\ldots$, $d_{n-1}\mid d_n$, and $d_n\mid 1995$. (2) The problem is not clear. If the $d_i$'s are allowed to be the same, then the statement is definitely false. It is perhaps the case that the $d_i$'s must be pairwise distinct (which should have been clearly stated in the problem). – Batominovski Aug 25 '17 at 17:40
• @Famke Your conclusion is true but your assumptions are much stronger than the olympiad problem allowed. You're dealing with a different question. – David K Aug 25 '17 at 17:52
• @Piquito The quotient is less than $2$, but the numerator of the quotient is either $15$ or $19$, both of which are greater than $2$. – Batominovski Aug 25 '17 at 18:55

Claim: If $p_1,p_2,\dots,p_m$ are distinct primes with $p_i\geq 2^{i}-1$, then for any set of distinct divisors $d_1<d_2<\dots<d_n$ of $N=p_1p_2\cdots p_m$, there is some fraction $\frac{d_i}{d_j}$ with reduced numerator $\geq n$.

This gives your result since $1995=3\cdot 5\cdot 7\cdot 19$.

Proof:

We will prove by induction on $m$.

If $m=1$, then all divisors are $1,p_1$. Since $p_1\geq 2$ you are done.

If true for $m$, then take $p_1,\dots,p_{m+1}$ with $p_i\geq 2^{i}-1$.

If none of $d_1,\dots,d_n$ are divisible by $p_{m+1}$, then it reduces to the case of $m$.

If all of the $d_i$ are divisible by $p_{m+1}$, then we can take the set of distinct divisors $\frac{d_1}{p_{m+1}},\dots,\frac{d_n}{p_{m+1}}$ of $p_1\cdot p_m$, and reduce to the case of $m$.

If $d_i$ is divisible by $p_{m+1}$ and $d_j$ is not, then $\frac{d_i}{d_j}$ has $p_{m+1}$ as a factor of the numerator. So that handles the cases when $n\leq p_{m+1}$. But if $n> p_{m+1}\geq 2^{m+1}-1$, then, since there are exactly $2^{m+1}$ divisors of $N$, $n=2^{m+1}$ and $d_1,\dots,d_n$ is all of the divisors. In particular, one of the $d_i=1$ and another $d_j=N$, and since $\{d_1,\dots,d_n\}\subseteq \{1,\dots,N\}$, you have $N\geq n$.

All of the $16$ divisors of $1995$ are of the form $3^{\delta_1}5^{\delta_2}7^{\delta_3}19^{\delta_4}$ where each exponent is equal to $0$ or $1$.

There are $8$ divisors of the form $19\cdot3^{\delta_1}5^{\delta_2}7^{\delta_3}$ and $8$ divisors of the form $3^{\delta_1}5^{\delta_2}7^{\delta_3}$.

►All set of divisors containing $n\ge9$ elements should contain at least one element of each of the two forms in which case we choose as numerator a factor of $19$ and as denominator a divisor coprime with it. This end the proof for $n\ge9$ because $19\gt 16$.

It remains the proof for $n=1,2,3,4,5,6,7,8$.

► For $n=8$ if all the divisors are multiples of $19$ we choose, for example the quotient $\dfrac{19\cdot3\cdot5}{19\cdot7}$ For all other set of $8$ elements containing a multiple of $19$ and a divisor coprime with $19$ we choose as numerator the multiple of $19$ and as denominator the divisor coprime to $19$

►We can now to consider just divisors of the form $3^{\delta_1}5^{\delta_2}7^{\delta_3}$.

For $n=8$ we choose $\dfrac{d_i}{d_j}=\dfrac{7\cdot3\cdot5}{5}$ (there are other examples).

For $n=7$ one of the $8$ involved divisors must lack. If it is the largest we choose $\dfrac{d_i}{d_j}=\dfrac{7\cdot5}{3}$ and if not we choose as numerator the mentioned largest (there are other examples).

For $n=6$ two of the $8$ concerned divisors should lack. If its are the two largest we choose $\dfrac{d_i}{d_j}=\dfrac{7\cdot3}{5}$ and if not we choose $\dfrac{d_i}{d_j}=\dfrac{7\cdot3\cdot5}{5}$(there are other examples).

And so on for $n=5,4,3,2$ and the trivial case $n=1$.