3
$\begingroup$
  • 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.

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

4 Answers 4

2
$\begingroup$

\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*}

$\endgroup$
5
  • $\begingroup$ Are you referring to the floor function? $\endgroup$
    – AbVk1718
    Sep 16, 2021 at 3:31
  • $\begingroup$ Sorry, but could you please elaborate how $0.01$ came? $\endgroup$
    – AbVk1718
    Sep 16, 2021 at 3:32
  • 1
    $\begingroup$ 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. $\endgroup$
    – poetasis
    Sep 16, 2021 at 3:39
  • 1
    $\begingroup$ @poetasis: You seem to be using the condition $q > 12$ without proof. $\endgroup$ Sep 16, 2021 at 7:48
  • $\begingroup$ @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. $\endgroup$
    – poetasis
    Sep 16, 2021 at 11:49
1
$\begingroup$

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?

$\endgroup$
5
  • 1
    $\begingroup$ May I know why this answer was downvoted? $\endgroup$ Sep 14, 2021 at 11:17
  • $\begingroup$ this is something which I could find as well, can we somehow find lower limit for p or q? $\endgroup$
    – AbVk1718
    Sep 14, 2021 at 11:20
  • 1
    $\begingroup$ In particular, this answer shows that the number of solutions to the problem is finite, and may thus be determined via brute force. $\endgroup$ Sep 14, 2021 at 11:20
  • $\begingroup$ ohk 👍. thanks for your efforts $\endgroup$
    – AbVk1718
    Sep 14, 2021 at 11:21
  • 1
    $\begingroup$ 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.$$ $\endgroup$ Sep 14, 2021 at 11:23
1
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ I got the idea, thanks $\endgroup$
    – AbVk1718
    Sep 16, 2021 at 8:49
  • $\begingroup$ thanks @AbVk1718 $\endgroup$ Sep 16, 2021 at 9:32
1
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .