Welcome to our community

Be a part of something great, join today!

Find Smallest Positive Integer

  • Thread starter
  • Admin
  • #1

anemone

MHB POTW Director
Staff member
Feb 14, 2012
3,756
Find the smallest positive integer $n$ such that for every integer $m$ with $0<m<1993$, there exists an integer $k$ for which \(\displaystyle \frac{m}{1993}<\frac{k}{n}<\frac{m+1}{1994}\).
 

Wilmer

In Memoriam
Mar 19, 2012
376
Find the smallest positive integer $n$ such that for every integer $m$ with $0<m<1993$, there exists an integer $k$ for which \(\displaystyle \frac{m}{1993}<\frac{k}{n}<\frac{m+1}{1994}\).
Terrific puzzle, Anemone!

Smallest n = 3987

Example using low m (1) and high m (1992):

(m + 1) / 1994 > k / n > m / 1993

m = 1:
2 / 1994 > 3 / 3987 > 1 / 1993

m = 1992:
1993 / 1994 > 3985 / 3987 > 1992 / 1993

Unfortunately, got no exotic formula for you (Bandit)
 
  • Thread starter
  • Admin
  • #3

anemone

MHB POTW Director
Staff member
Feb 14, 2012
3,756
Terrific puzzle, Anemone!

Smallest n = 3987

Example using low m (1) and high m (1992):

(m + 1) / 1994 > k / n > m / 1993

m = 1:
2 / 1994 > 3 / 3987 > 1 / 1993

m = 1992:
1993 / 1994 > 3985 / 3987 > 1992 / 1993
Hi Wilmer,

Thanks for participating and thanks for the compliment to this problem as well.:)

Yes, 3987 is the answer to this problem but...

Unfortunately, got no exotic formula for you(Bandit)
30 minutes in the corner, please...(Tongueout)

 

Wilmer

In Memoriam
Mar 19, 2012
376
30 minutes in the corner, please...(Tongueout)
No fair! You only asked: "Find the smallest positive integer [FONT=MathJax_Math-italic]n" (Punch)[/FONT]
 
  • Thread starter
  • Admin
  • #5

anemone

MHB POTW Director
Staff member
Feb 14, 2012
3,756
I'll post the solution in full later because I think there might be others who still want to attempt it!
 

Albert

Well-known member
Jan 25, 2013
1,225
Find the smallest positive integer $n$ such that for every integer $m$ with $0<m<1993$, there exists an integer $k$ for which \(\displaystyle \frac{m}{1993}<\frac{k}{n}<\frac{m+1}{1994}\).
we know $0<\dfrac {k}{n}<1$
using $0<\dfrac {1}{2}<\dfrac {2}{3}<\dfrac {3}{4}<--<\dfrac {3985}{3986}<\dfrac {3986}{3987}<\dfrac {3987}{3988}<1$
$2\times \dfrac {m}{3986}<\dfrac {k_0}{n_0}<2\times \dfrac{m+1}{3988}<1$
take $n=n_0 ,\,\, and \,\, k=k_0$
now it is easy to see that the smallese value of n =3987
 
Last edited:
  • Thread starter
  • Admin
  • #7

anemone

MHB POTW Director
Staff member
Feb 14, 2012
3,756
we know $0<\dfrac {k}{n}<1$
using $0<\dfrac {1}{2}<\dfrac {2}{3}<\dfrac {3}{4}<--<\dfrac {3995}{3996}<\dfrac {3996}{3997}<\dfrac {3997}{3998}<1$
$2\times \dfrac {m}{3996}<\dfrac {k_0}{n_0}<2\times \dfrac{m+1}{3998}<1$
take $n=n_0 ,\,\, and \,\, k=k_0$
now it is easy to see that the smallese value of n =3997
Hi Albert,

Thanks for participating and I assume you meant \(\displaystyle \dfrac {3985}{3986}<\dfrac {3986}{3987}<\dfrac {3987}{3988}\) rather than \(\displaystyle \dfrac {3995}{3996}<\dfrac {3996}{3997}<\dfrac {3997}{3998}\), is that true?


If that's true, according to your reasoning we would arrive to \(\displaystyle \dfrac {3985}{1993}<\dfrac {2(3986)}{3987}<\dfrac {3987}{1994}\) and I don't think this helps much as what the original question stated is it wants the difference between the two numerators on both fractions to be 1 but $3987-3985=2$. Hmm...What do you think, Albert?
 

Opalg

MHB Oldtimer
Staff member
Feb 7, 2012
2,725
Find the smallest positive integer $n$ such that for every integer $m$ with $0<m<1993$, there exists an integer $k$ for which \(\displaystyle \frac{m}{1993}<\frac{k}{n}<\frac{m+1}{1994}\).
If \(\displaystyle \frac ab < \frac cd\) then \(\displaystyle \frac ab < \frac{a+c}{b+d} < \frac cd\) (assuming that all those numbers are positive). Therefore \(\displaystyle \frac m{1993} < \frac {2m+1}{3987} < \frac{m+1}{1994}.\)

(But that doesn't prove that $3987$ is the smallest such number.)
 
  • Thread starter
  • Admin
  • #9

anemone

MHB POTW Director
Staff member
Feb 14, 2012
3,756
Solution:


If we have \(\displaystyle \frac{1992}{1993}<\frac{k}{n}<\frac{1993}{1994}\), then \(\displaystyle \frac{1993-1992}{1993}>\frac{n-k}{n}>\frac{1994-1993}{1994}\).

Simplifying we get

\(\displaystyle \frac{1}{1993}>\frac{n-k}{n}>\frac{1}{1994}\)

\(\displaystyle 1993<\frac{n}{n-k}<1994\)

Clearly \(\displaystyle n-k \ne 1\), so \(\displaystyle n-k \ge 2\).

Hence, \(\displaystyle n>1993(n-k) \ge 3986\) and so $n \ge 3987$.

Remark: This method of solving isn't mine, I saw it somewhere and wanted so much to share it here with MHB.
 

Albert

Well-known member
Jan 25, 2013
1,225
Hi Albert,

Thanks for participating and I assume you meant \(\displaystyle \dfrac {3985}{3986}<\dfrac {3986}{3987}<\dfrac {3987}{3988}\) rather than \(\displaystyle \dfrac {3995}{3996}<\dfrac {3996}{3997}<\dfrac {3997}{3998}\), is that true?


If that's true, according to your reasoning we would arrive to \(\displaystyle \dfrac {3985}{1993}<\dfrac {2(3986)}{3987}<\dfrac {3987}{1994}\) and I don't think this helps much as what the original question stated is it wants the difference between the two numerators on both fractions to be 1 but $3987-3985=2$. Hmm...What do you think, Albert?
sorry :eek: a mistake in calculation , now I will do this way :
$\dfrac {2m}{3986}\leq \dfrac{3984}{3986}\approx 0.999498243$
$\dfrac {2m+2}{3988}\leq \dfrac{3986}{3988}\approx 0.999498495$
for any 0<m<1993 ($m\in N$)
and we will find min(n) satisfying :
$\dfrac {3984}{3986}<\dfrac{k}{n}<\dfrac {3986}{3988}<1-----(1)$
$\dfrac {-3986}{3988}<\dfrac{-k}{n}<\dfrac {-3984}{3986}$

$\dfrac {2}{3988}<\dfrac{n-k}{n}<\dfrac {2}{3986}$

the rest is the same as the solution from anemone
in fact from (1) it is clear to see min(n)=3987
 
Last edited:

Albert

Well-known member
Jan 25, 2013
1,225
we know $0<\dfrac {k}{n}<1$
using $0<\dfrac {1}{2}<\dfrac {2}{3}<\dfrac {3}{4}<--<\dfrac {3985}{3986}<\dfrac {3986}{3987}<\dfrac {3987}{3988}<1$
$2\times \dfrac {m}{3986}<\dfrac {k_0}{n_0}<2\times \dfrac{(m+1)}{3988}<1$
take $n=n_0 ,\,\, and \,\, k=k_0$
now it is easy to see that the smallese value of n =3987
the previous post (a mistake in calculation) has been changed above