# No. of solutions to a integer-based inequality

• Let $$p, q$$ be positive integers such that $$q≤99$$. Find number of ordered pairs $$(p,q)$$ such that $$\frac {2}{5} \ < \frac {p}{q} \ < \ \frac {21}{50}.$$

Here's what I could do: Using the fact that if $$0 \ < \frac {a}{b} < 1 \ \Rightarrow \frac {a}{b} \ < \ \frac {a+d}{b+d}$$ where $$d>0,$$ I could find a few solutions like $$(p,q) \ = (41,99) \ (40,98) \, (39,96), \ etc.$$ But it seems like there are a lot more possible solution pairs.

What should be a proper strategy?

Any hint or help will be much appreciated. Thanks.

• Yes, I mean that. Edited Commented Sep 14, 2021 at 11:03
• Please include that information in the question. Commented Sep 14, 2021 at 11:04
• What are ordered pairs? E.g. $p=20 , q\in\left\{48,49\right\}$ do you accept these pairs? Commented Sep 14, 2021 at 11:36
• @lonestudent Yes, you are right Commented Sep 14, 2021 at 12:54
• Are you writing software? Or doing a contest? Commented Sep 16, 2021 at 4:02

\begin{align*} \frac {2}{5} \ < \frac {p}{q} \ < \ \frac {21}{50} \implies \frac{20q}{50} \lt p\lt \frac {21q}{50}\\ \\ \end{align*}

This means $$\space \dfrac{20\cdot12}{50}=4.8 \lt p\le \bigg\lfloor\dfrac{21q}{50}-0.01\bigg\rfloor=41.58-0.01, q=99\space$$ and

when $$\space0<\bigg\lfloor\dfrac{21q}{50}-0.01\bigg\rfloor- \dfrac{20q}{50}<1\space$$ there is one pair

when $$\space 1<\bigg\lfloor\dfrac{21q}{50}-0.01\bigg\rfloor- \dfrac{20q}{50}<2\space$$ there are two pairs.

There is a single pair for $$49\space q$$-values and two pairs for $$20\space q$$-values. A spreadsheet shows these $$89$$ solutions as

\begin{align*} (5,12)\quad (7,17)\quad (9,22)\quad (10,24)\quad (11,27)\quad (12,29)\\ (13,31)\quad (13,32)\quad (14,34)\quad (15,36)\quad (15,37)\quad (16,39)\\ (17,41)\quad (17,42)\quad (18,43)\quad (18,44)\quad (19,46)\quad (19,47)\\ (20,48)\quad (20,49)\quad (21,51)\quad (21,52)\quad (22,53)\quad (22,54)\\ (23,55)\quad (23,56)\quad (23,57)\quad (24,58)\quad (24,59)\quad (25,60)\\ (25,61)\quad (25,62)\quad (26,62)\quad (26,63)\quad (26,64)\quad (27,65)\\ (27,66)\quad (27,67)\quad (28,67)\quad (28,68)\quad (28,69)\quad (29,70)\\ (29,71)\quad (29,72)\quad (30,72)\quad (30,73)\quad (30,74)\quad (31,74)\\ (31,75)\quad (31,76)\quad (31,77)\quad (32,77)\quad (32,78)\quad (32,79)\\ (33,79)\quad (33,80)\quad (33,81)\quad (34,81)\quad (33,82)\quad (34,82)\\ (34,83)\quad (34,84)\quad (35,84)\quad (35,85)\quad (35,86)\quad (36,86)\\ (35,87)\quad (36,87)\quad (36,88)\quad (36,89)\quad (37,89)\quad (37,90)\\ (37,91)\quad (38,91)\quad (37,92)\quad (38,92)\quad (38,93)\quad (39,93)\\ (38,94)\quad (39,94)\quad (39,95)\quad (39,96)\quad (40,96)\quad (39,97)\\ (40,97)\quad (40,98)\quad (41,98)\quad (40,99)\quad (41,99)\\ \end{align*}

• Are you referring to the floor function? Commented Sep 16, 2021 at 3:31
• Sorry, but could you please elaborate how $0.01$ came? Commented Sep 16, 2021 at 3:32
• Yes I am referring to the floor function. The alternative was $INT()$. As for the $0.01$, it could have been $0.0000001$ or anything smaller than $0.01$ just to make $p$ be smaller than the high limit. Commented Sep 16, 2021 at 3:39
• @poetasis: You seem to be using the condition $q > 12$ without proof. Commented Sep 16, 2021 at 7:48
• @Arnie Bebita-Dris Yes I did use $\space q >12\space$ without proof but no proof was requested. Perhaps I could have shown that $\space\dfrac{20\cdot 13}{50}=5.2\not\lt p\space \le \bigg\lfloor\dfrac{21\cdot 13}{50}-0.01\bigg\rfloor=\big\lfloor5.46-0.01\big\rfloor,\space q=13\space$ but I do not know what else. I'm an amateur about $45$ years removed from academia but I'm willing to learn if you can suggest a better treatment. Commented Sep 16, 2021 at 11:49

Hint: $$q \leq 99$$ and $$\frac{p}{q} < \frac{21}{50}$$ with $$q$$ positive imply that $$p < \frac{21q}{50} \leq \frac{21 \cdot 99}{50} = 41.58$$ which further means that $$p \leq 41.$$

Can you finish?

• May I know why this answer was downvoted? Commented Sep 14, 2021 at 11:17
• this is something which I could find as well, can we somehow find lower limit for p or q? Commented Sep 14, 2021 at 11:20
• In particular, this answer shows that the number of solutions to the problem is finite, and may thus be determined via brute force. Commented Sep 14, 2021 at 11:20
• ohk 👍. thanks for your efforts Commented Sep 14, 2021 at 11:21
• Sure, $$\frac{2}{5} < \frac{p}{q} \implies p > \frac{2q}{5} \geq \frac{2}{5},$$ since $q > 0$ implies $q \geq 1$, so that the best lower bound that you will be able to find for $p$ and $q$ are $$p \geq 1$$ and $$q \geq 1.$$ Commented Sep 14, 2021 at 11:23

After rearranging you can see that $$\dfrac{2q}{5} < p < \dfrac{21q}{50}$$ so there must be an integer between

$$\dfrac{2q}{5}$$ and $$\dfrac{21q}{50}$$and also their difference $$= \dfrac{q}{50} < 2$$ so their can't be more than 2 integers.

So solve the equations \begin{align} \left\lfloor\dfrac{21q}{50} \right\rfloor - \left\lfloor\dfrac{2q}{5} \right\rfloor &= 1\\ \left\lfloor\dfrac{21q}{50} \right\rfloor - \left\lfloor\dfrac{2q}{5} \right\rfloor &= 2 \end{align}

And then you multiply by the 2 the number of solutions to the second and add that to the first

• I got the idea, thanks Commented Sep 16, 2021 at 8:49
• thanks @AbVk1718 Commented Sep 16, 2021 at 9:32

Here's another approach.

$$Z=\sum_p\sum_{1 \le q < 100} [2/5 < p/q < 21/50]$$

can be rewritten as

$$Z=\left(\sum_p\sum_{1 \le q < 100} [p < 21q/50]\right) - \left(\sum_p\sum_{1 \le q < 100} [p \le 2q/5]\right)$$

And $$p < 21q/50$$ is the same as $$p \le 21q/50$$ except when $$50|q$$, so both sums are effectively the same problem.

So generalizing (and assuming s,t coprime):

$$\begin{array}{rcl} f(s, t, n) &=& \sum_{0 \le q < nt} \sum_p[p \le sq/t] \\ &=& \sum_{0 \le q < nt} \lfloor sq/t \rfloor + 1 \\ &=& nt + \sum_{0 \le r < t} \sum_{0 \le q < n} \lfloor s(qt + r)/t \rfloor \\ &=& nt + \sum_{0 \le r < t} \sum_{0 \le q < n} sq + \lfloor sr/t \rfloor \\ &=& nt + st\frac{n^2-n}{2} + n\sum_{0 \le r < t} \lfloor sr/t \rfloor \\ &=& nt + st\frac{n^2-n}{2} + n\sum_{0 \le r < t} \frac{sr - (sr \mod t)}{t} \\ &=& nt + st\frac{n^2-n}{2} + \frac{n}{t}(s\frac{t^2-t}{2} - \frac{t^2-t}{2}) \\ &=& \frac n2 (nst + t - s + 1) \end{array}$$

That for s,t coprime $$(\sum_{0 \le r < t} {sr \mod t}) = (t^2 - t)/2$$ is exploiting the neat property that for the function $$g(r) = (sr \mod t)$$, the image of $${0 .. t-1}$$ is exactly $${0 .. t-1}$$, that is, it is a permutation.

The lowerbound for the Z sums isn't $$0\le q$$, it's $$1 \le q$$; so we need to subtract the $$q=0$$ term from the sums. So the solution is

$$Z = f(21, 50, 2) - f(2, 5, 20) - \underbrace{100/50}_\text{(a)} - \underbrace{(0 - 1)}_\text{(b)} = 89$$

(a) Correction for the $$50|q$$ terms in the first sum

(b) Correction for the $$q=0$$ case in both sums