两个既约分数之间的分母最小的既约分数

郝酒

最近遇到了三道题
1. 数学小组中男生人数大于总人数的45%且小于50%，则此小组最少多少人？
2. 求介于$\frac{\text{147}}{\text{340}}$到$\frac{\text{29}}{\text{67}}$之间分母最小的最简分数；
3. $f(x)=\begin{cases} x, x \mbox{是无理数}\\  \frac{q+1}{p},x=\frac{q}{p},p,q\mbox{互素}\end{cases}$，求$f(x)$在$\left(\frac{7}{8},\frac{8}{9}\right)$上的最大值.

都是求两个既约分数之间的分母最小的既约分数的问题，我是按如下方法解的，感觉不严谨而且给小学生讲不清楚，想问下大大们有什么好方法。
以第一题为例
设$\frac{9}{20}<\frac{q}{p}<\frac{1}{2}$，交叉相乘得$20q>9p$,$p>2q$，要p尽可能的小，通分后的分母也尽可能的小，所以$20q-9p=1$,$p-2q=1$,解得$p=11,q=5$,得$\frac{5}{11}$.

kuing

分段函数用 cases 环境输入

郝酒

回复 2# kuing

好的，我还是用array输的：）

kuing

另外，在值与条件之间加 & 就会有对齐效果：

1. f(x)=\begin {cases}
2. x, & x \text{是无理数}\\
3. \frac{q+1}{p}, & x=\frac{q}{p},p,q\text{互素}
4. \end{cases}

Copy the Code

$f(x)=\begin {cases}
x, & x \text{是无理数}\\
\frac{q+1}{p}, & x=\frac{q}{p},p,q\text{互素}
\end{cases}$

回正题，第一题沿你的设法可以这样走：
\begin{align*}
\frac9{20}<\frac qp<\frac12&\iff 2q<p<\frac{20}9q\\
&\iff 0<p-2q<\frac29q\\
&\riff p-2q\geqslant 1\land\frac29q>1\\
&\riff q\geqslant 5\land p\geqslant 2q+1\geqslant 11,
\end{align*}最后验证一下 5/11 满足条件就OK了。

kuing

第二题：
\begin{align*}
&\frac{147}{340}<\frac qp<\frac{29}{67}\iff\frac{147}{340-2\cdot147}<\frac q{p-2q}<\frac{29}{67-2\cdot29}\\
\iff{}&\frac{147}{46}<\frac q{p-2q}<\frac{29}9\iff\frac{147-3\cdot46}{46}<\frac{q-3(p-2q)}{p-2q}<\frac{29-3\cdot9}9\\
\iff{}&\frac9{46}<\frac{7q-3p}{p-2q}<\frac29\iff\frac9{46-4\cdot9}<\frac{7q-3p}{p-2q-4(7q-3p)}<\frac2{9-4\cdot2}\\
\iff{}&\frac9{10}<\frac{7q-3p}{13p-30q}<2,
\end{align*}所以
\[\led
7q-3p&\geqslant1,\\
13p-30q&\geqslant1
\endled
\riff p\geqslant37,\]最后验证 `16/37` 满足。

上面的变形其实相当于将 `\frac{147}{340}<\frac qp<\frac{29}{67}` 变成
\[\dfrac1{2+\dfrac1{3+\dfrac1{4+\dfrac1{\dfrac9{10}}}}}<\dfrac1{2+\dfrac1{3+\dfrac1{4+\dfrac1{\dfrac{7q-3p}{13p-30q}}}}}<\dfrac1{2+\dfrac1{3+\dfrac1{4+\dfrac12}}},\]还是玩上了连分数……

isee

回复 5# kuing

难得写这么细，难道楼主是个MM或……

kuing

回复 6# isee

nonono，主要是自己这方面太弱，也是相当于写给自己。

isee

回复 7# kuing


其实具体过程就是辗转相除，解决2这种题，从何版处学来的连分数极受用。

哈哈，巧了，也有何版，，，睡觉了，，，先

kuing

回复 8# isee

可是第3题我还是不知怎么做……

把 f(x) 画了一下，挺有趣嘀，下图为 `x\in(0,1)` 的有理数且分母不超过 100 的 `f(x)` 的点集：

1. f[n_] := Table[{FareySequence[n, k], (Numerator[FareySequence[n, k]] + 1)/Denominator[FareySequence[n, k]]}, {k, 2, Length[FareySequence[n]] - 1}]
2. ListPlot[f[100]]

Copy the Code

kuing

回复 9# kuing

擦，原来是我想复杂了，其实非常简单，根本不需要上面扯的那些东西。

当 `x=q/p\in(7/8,8/9)` 时，设 `p=q+k`，则由 `7/8<q/(q+k)<8/9` 解得 `7k<q<8k`，所以必须 `k\geqslant2` 且 `7k+1\leqslant q\leqslant8k-1`，故
\[f(x)=\frac{q+1}{q+k}\leqslant\frac{8k}{9k-1}\leqslant\frac{8\cdot2}{9\cdot2-1}=\frac{16}{17},\]当 `x=15/17` 时取等。

而当 `x` 为无理数时显然 `f(x)` 小于此值，所以最大值就是 `16/17`。

郝酒

我说啦这三个题目是同一类型的: )

游客

（1）$\frac{q}{p}<\frac{8}{9} \Rightarrow 8 p>9 q$ ，记 $8 p=9 q+m$ ，则：$\frac{q+1}{p}=\frac{8}{9}+\frac{9-m}{9 p}$ ．显然，对于给定的 $p$ ，当 $m=1$ 时，$\frac{q+1}{p}$ 最大．$\Rightarrow 8 p=9 q+1$ ．当 $m=1$ 时，$p$ 越小，$\frac{q+1}{p}$ 越大，而且有：
$9 q=8 p-1=9 p-(p+1) . \Rightarrow 9 \mid(p+1)$ ．（原题 3 ）
（2）$\frac{q}{p}>\frac{7}{8} \Rightarrow 8 q>7 p$ ，记 $7 p=8 q-n$ ，则：$\frac{q-1}{p}=\frac{7}{8}+\frac{n-8}{8 p}$ ．
显然，对于给定的 $p$ ，当 $n=1$ 时，$\frac{q-1}{p}$ 最小．$\Rightarrow 8 q=7 p+1$ ．
当 $n=1$ 时，$p$ 越小，$\frac{q-1}{p}$ 越小，而且有：
$8 q=7 p+1=8 p-(p-1) . \Rightarrow 8 \mid(p-1)$ ．题3修改）

hbghlyj

kuing 发表于 2019-3-6 10:58
第二题：
\begin{align*}
&\frac{147}{340}

根据5#写成Mathematica代码

1. f[a_Rational,b_Rational]:=Block[{n=1,frac},
2. cfA = ContinuedFraction[a];
3. cfB = ContinuedFraction[b];
4. While[cfA[[n]] == cfB[[n]], n++];
5. FromContinuedFraction[Take[cfA, n]]]

Copy the Code

例如f[147/340, 29/67]输出$\frac{16}{37}$