smc

More generally, let $a,b,c,d,p,$ and $q$ be positive integers such that $bc-ad=1$ and $$\frac{a}{b}<\frac{p}{q}<\frac{c}{d}.$$ From $\frac{a}{b}<\frac{p}{q},$ we have $bp-aq>0,$ or $$bp-aq\ge 1.(1)$$ From $\frac{p}{q}<\frac{c}{d},$ we have $cq-dp>0,$ or $$cq-dp\ge 1.(2)$$ Since $bc-ad=1,$ note that: 1. Multiplying $(1)$ by $d,$ multiplying $(2)$ by $b,$ and adding the results, we get $q\ge b+d.$ 2. Multiplying $(1)$ by $c,$ multiplying $(2)$ by $a,$ and adding the results, we get $p\ge a+c.$ To minimize $q,$ we set $q=b+d,$ from which $p=a+c.$ Together, we can prove that $$\frac{a+c-1}{b+d}\le \frac{a}{b}<\frac{a+c}{b+d}<\frac{c}{d}\le \frac{a+c+1}{b+d}.(★)$$ For this problem, we have $a=5,b=9,c=4,$ and $d=7,$ so $p=a+c=9$ and $q=b+d=16.$ The answer is $q-p=\boxed{7}.$ Remark We will prove each part of the compound inequality in $(★):$ 1. $\frac{a+c-1}{b+d}\le \frac{a}{b}$ and $\frac{c}{d}\le \frac{a+c+1}{b+d}$ Let $\frac{a}{b}=k,$ so $a=bk.$ The precondition $bc-ad=1$ becomes $bc-bdk=1,$ so $c-dk=\frac{1}{b}.$ It follows that $$\frac{a+c-1}{b+d}=\frac{bk+c-1}{b+d}=k+\frac{c-dk-1}{b+d}=k+\frac{\frac{1}{b}-1}{b+d}=k+\frac{1-b}{b(b+d)}\le k.$$ Moreover, the equality case occurs if and only if $b=1.$ We can prove $\frac{c}{d}\le \frac{a+c+1}{b+d}$ by the same process. Similarly, the equality case occurs if and only if $d=1.$ 5. $\frac{a}{b}<\frac{a+c}{b+d}<\frac{c}{d}$ Let $\frac{a}{b}=k_1$ and $\frac{c}{d}=k_2,$ so $a=b{k}_1$ and $c=d{k}_2.$ It follows that \begin{alignat}{10} \frac{a+c}{b+d}&=\frac{bk_1+dk_2}{b+d}&&=k_1+\frac{dk_2-dk_1}{b+d}&&=k_1+\frac{d(k_2-k_1)}{b+d}&&>k_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}&&} Moreover, this part of $(★)$ is independent of the precondition $bc-ad=1.$