Maths Olympiad Prep

Library / /448 of 520

Number theory Difficulty 4.0 AMC 10/12 Find the answer

Let pp and qq be positive integers such that 59<pq<47\frac{5}{9} < \frac{p}{q} < \frac{4}{7}and qq is as small as possible. What is qpq-p?
(A) 7\textbf{(A) } 7(B) 11\textbf{(B) } 11(C) 13\textbf{(C) } 13(D) 17\textbf{(D) } 17(E) 19\textbf{(E) } 19

Solutions — 2

Solution 1

More generally, let a,b,c,d,p,a,b,c,d,p, and qq be positive integers such that bcad=1bc-ad=1 and \frac ab 0,$ or \[bp-aq\geq1. \hspace{15mm} (1)
From pq0,\frac pq 0, or cqdp1.(2)cq-dp\geq1. \hspace{15mm} (2)
Since bcad=1,bc-ad=1, note that:

Multiplying (1)(1) by d,d, multiplying (2)(2) by b,b, and adding the results, we get qb+d.q\geq b+d.
Multiplying (1)(1) by c,c, multiplying (2)(2) by a,a, and adding the results, we get pa+c.p\geq a+c.

To minimize q,q, we set q=b+d,q=b+d, from which p=a+c.p=a+c. Together, we can prove that \[\frac{a+c-1}{b+d}\leq\frac abk_1, \\ \frac{a+c}{b+d}&=\frac{bk_1+dk_2}{b+d}&&=k_2+\frac{bk_1-bk_2}{b+d}&&=k_2+\frac{b(k_1-k_2)}{b+d}&&<k_2. \end{alignat*}
Moreover, this part of ()(\bigstar) is independent of the precondition bcad=1.bc-ad=1.

~MRENTHUSIASM

Solution 2

To solve the problem, we need to find the smallest positive integer q q such that there exists a positive integer p p satisfying the inequality:
59<pq<47 \frac{5}{9} < \frac{p}{q} < \frac{4}{7}

1. **Express the inequalities in terms of p p and q q :**
59<pq<47 \frac{5}{9} < \frac{p}{q} < \frac{4}{7}
This can be rewritten as:
5q<9pand7p<4q 5q < 9p \quad \text{and} \quad 7p < 4q

2. **Manipulate the inequalities to find bounds for q q :**
- From 5q<9p 5q < 9p :
5q<9p    p>5q9 5q < 9p \implies p > \frac{5q}{9}
- From 7p<4q 7p < 4q :
7p<4q    p<4q7 7p < 4q \implies p < \frac{4q}{7}

3. Combine the inequalities:
5q9<p<4q7 \frac{5q}{9} < p < \frac{4q}{7}

4. **Find the smallest q q such that there exists an integer p p satisfying the combined inequality:**
- We need to find the smallest q q such that:
5q9<4q7 \left\lceil \frac{5q}{9} \right\rceil < \left\lfloor \frac{4q}{7} \right\rfloor

5. **Test values of q q starting from the smallest possible integer:**
- For q=1 q = 1 :
519=59=1,417=47=0(not valid) \left\lceil \frac{5 \cdot 1}{9} \right\rceil = \left\lceil \frac{5}{9} \right\rceil = 1, \quad \left\lfloor \frac{4 \cdot 1}{7} \right\rfloor = \left\lfloor \frac{4}{7} \right\rfloor = 0 \quad \text{(not valid)}
- For q=2 q = 2 :
529=109=2,427=87=1(not valid) \left\lceil \frac{5 \cdot 2}{9} \right\rceil = \left\lceil \frac{10}{9} \right\rceil = 2, \quad \left\lfloor \frac{4 \cdot 2}{7} \right\rfloor = \left\lfloor \frac{8}{7} \right\rfloor = 1 \quad \text{(not valid)}
- Continue this process until q=16 q = 16 :
5169=809=9,4167=647=9(valid) \left\lceil \frac{5 \cdot 16}{9} \right\rceil = \left\lceil \frac{80}{9} \right\rceil = 9, \quad \left\lfloor \frac{4 \cdot 16}{7} \right\rfloor = \left\lfloor \frac{64}{7} \right\rfloor = 9 \quad \text{(valid)}

6. **Verify the values of p p and q q :**
- For q=16 q = 16 and p=9 p = 9 :
59<916<47 \frac{5}{9} < \frac{9}{16} < \frac{4}{7}
- Check:
590.5556,916=0.5625,470.5714 \frac{5}{9} \approx 0.5556, \quad \frac{9}{16} = 0.5625, \quad \frac{4}{7} \approx 0.5714
- The inequality holds true.

7. **Calculate qp q - p :**
qp=169=7 q - p = 16 - 9 = 7

The final answer is 7\boxed{7}

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.