Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Find the number of pairs $(m, n)$ of positive integers such that $\frac{ m}{n+1} < \sqrt{2} < \frac{m+1}{n}$ Constraint: $m$ and $n$ are both less than or equal to 1000

I toiled over this problem for a bit. I tested the first few positive integers of m and found the corresponding values of $n$, but no real pattern seemed to emerge. Clearly $m \ge n$ . I believe that for each value of $m$, there were either two or one value(s) for $n$ in no clear order, which is the part that is messing me up. This is meant to be done by hand so I have not used any software on it.

share|improve this question
1  
That almost goes without saying, @RustynYazdanpour, since $m/n$ will be roughly $\sqrt{2}$, so $m\approx n\sqrt{2}$, so if $n$ is larger than $707$ than $m>1000$. –  Thomas Andrews Dec 26 '12 at 7:04
    
@ThomasAndrews that was the logic I used; I figured it worthy of a comment. –  Rustyn Dec 26 '12 at 7:14
    
This might work: make a list of the values of $m$ that result in two values of $n$, and then look that sequence up in the Online Encyclopedia of Integer Sequences. Or look up the complementary sequence. –  Gerry Myerson Dec 26 '12 at 7:19
    
FYI, the number of pairs (m,n) with $m,n \leq 1000$ is 1706 (found using Matlab). The proportion approaches $(1+\frac{1}{\sqrt{2}})$ as we increase the upper limit –  Dinesh Dec 26 '12 at 7:46
    
The answer is exactly $999+\lfloor{1001/\sqrt{2}\rfloor}$, and the pattern is followed as described in my answer below - this works in general. –  Thomas Andrews Dec 26 '12 at 8:08
add comment

2 Answers

up vote 14 down vote accepted

You can rewrite this as: $$\frac{m}{\sqrt{2}}-1<n<\frac{m+1}{\sqrt{2}}$$

Since $\sqrt{2}$ is irrational, we knwo that $\frac{m}{\sqrt{2}}-1$ is not an integer, so for an integer $n>\frac{m}{\sqrt{2}}-1$ iff $n\geq \left\lceil \frac{m}{\sqrt{2}}-1\right\rceil =\left\lfloor \frac{m}{\sqrt{2}}\right\rfloor$.

Similarly, $n<\frac{m+1}{\sqrt{2}}$ iff $n\leq \left\lfloor \frac{m+1}{\sqrt{2}}\right\rfloor$. So altogether, we are seeking $m,n$ such that $$\left\lfloor\frac{m}{\sqrt 2}\right\rfloor\leq n\leq \left\lfloor\frac{m+1}{\sqrt{2}}\right\rfloor$$

For a particular $m$, then, the number of possible $n$ is: $\left\lfloor\frac{m+1}{\sqrt{2}}\right\rfloor-\left\lfloor\frac{m}{\sqrt 2}\right\rfloor +1$. Summing over all $m$, the result is $$-1+\sum_{m=1}^{1000}\left(\left\lfloor\frac{m+1}{\sqrt{2}}\right\rfloor-\left\lfloor\frac{m}{\sqrt 2}\right\rfloor +1\right)$$

(The $-1$ is because we don't want to count $n=0$ when $m=1$.)

But this is just $999$ plus a telescoping sum, and we see that the result is:

$$999+\left\lfloor\frac{1001}{\sqrt{2}}\right\rfloor$$

Actually, even more specifically, it is:

$$1000-\lfloor\sqrt{2}\rfloor + \left\lfloor\frac{1000+1}{\sqrt{2}}\right\rfloor$$

This will work for any irrational number $\alpha>1$ and any upper bound, $M>\alpha$, yielding a total: $$M-\lfloor\alpha\rfloor + \left\lfloor\frac{M+1}{\alpha}\right\rfloor$$

which counts the pairs $(m,n)$ with $1\leq m,n\leq M$ and $$\frac{m}{n+1}<\alpha<\frac{m+1}n$$

share|improve this answer
    
I am unclear why in your second step of the edit there is no 1. Does the inequality take care of it? I understand your reasoning and this fully answers my question. –  Alex Dec 26 '12 at 8:16
    
Essentially, if $x$ is not an integer, then $\lceil x-1\rceil = \lfloor x\rfloor$ –  Thomas Andrews Dec 26 '12 at 8:18
    
So if $n$ is an integer and $x$ is not, then $n>x-1$ if and only if $n\geq \lfloor x\rfloor$. Thus, this technique definitely requires that $\sqrt{2}$ is irrational. –  Thomas Andrews Dec 26 '12 at 8:20
add comment

$\frac{m}{n+1}\lt \sqrt{2}\lt\frac{m+1}{n}$

$m \lt \sqrt{2}(n+1)$;$\sqrt{2}n-1 \lt m$

$m^2\lt 2(n+1)^2$;$(\sqrt{2}n-1)^2\lt m^2$

$m^2\lt 2n^2+4n+2$;$2n^2+1-2\sqrt{2}n \lt m^2$

$2{n^2}+1-2\sqrt{2}n<m^2<2{n^2}+2+4n$

$2{n^2}+2+4n \gt 1000,000$

${n^2}+1+2n \gt 500,000$

${n^2}+2n \gt 499,999$

$n(n+2)\gt 499,999$

$n(n+2)\gt (706)(708)$

$706\lt n\leq1000$

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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