15
$\begingroup$

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.

  • 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$.2012-12-26
  • 0
    @ThomasAndrews that was the logic I used; I figured it worthy of a comment.2012-12-26
  • 0
    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.2012-12-26
  • 0
    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 limit2012-12-26
  • 0
    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.2012-12-26

2 Answers 2

19

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

Since $\sqrt{2}$ is irrational, we know 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$$

  • 0
    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.2012-12-26
  • 0
    Essentially, if $x$ is not an integer, then $\lceil x-1\rceil = \lfloor x\rfloor$2012-12-26
  • 0
    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.2012-12-26
0

I don't understand. Why such complexity?

Inequality: $$\frac{m}{n+1}<\sqrt{2}<\frac{m+1}{n}$$

This is equivalent to the inequality :

$$n\sqrt{2}-1

It is easy to see that one is " $n$ " - corresponds to one value " $m$ ".

Or let's different. $$\frac{m}{\sqrt{2}}-1

Set the number " $m$ " - and integer " $2n$ " - and will be the number of all possible pairs.

$$1+\sqrt{2}=2,4142$$

So the number of all possible pairs given " $m$ ". 't care. " $ 2n $ " .