1
$\begingroup$

(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? enter image description here

$\endgroup$
  • 1
    $\begingroup$ What did you try? $\endgroup$ – Parcly Taxel Aug 25 '17 at 17:35
  • 1
    $\begingroup$ 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. $\endgroup$ – David K Aug 25 '17 at 17:40
  • $\begingroup$ 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). $\endgroup$ – Batominovski Aug 25 '17 at 17:40
  • 1
    $\begingroup$ @Famke Your conclusion is true but your assumptions are much stronger than the olympiad problem allowed. You're dealing with a different question. $\endgroup$ – David K Aug 25 '17 at 17:52
  • 1
    $\begingroup$ @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$. $\endgroup$ – Batominovski Aug 25 '17 at 18:55
1
$\begingroup$

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$.

$\endgroup$
0
$\begingroup$

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.