033. 抵消分数(digit cancelling fractions)

分数\(49/98\)是一个好奇分数,因为一个没有经验的数学家在化简它的时候可能会不正确的在分子分母同时划掉\(9\),即\(49/98=4/8\),但是结果却是正确的。我们认为像\(30/50=3/5\)这样的分数是平凡的,在这里不做考虑。只有四个非平凡的好奇分数,满足分数值小于一且分子分母都是两位数。将这四个非平凡的好奇分数相乘,并取其最简形式,求其分母的值。

分析:假设我们所求分数的分子为\(n\),分母为\(d\),由于分数值必须小于一,则有\(1\le n<d\le9\);同时假设我们想要约去的数为\(i\),则有\(1\le i\le9\)。因此该分数对应的原好奇分数有四种可能的形式:

$$ 1)\frac{10i+n}{10i+d}=\frac{n}{d}\\ 2)\frac{10n+i}{10d+i}=\frac{n}{d}\\ 3)\frac{10i+n}{10d+i}=\frac{n}{d}\\ 4)\frac{10n+i}{10i+d}=\frac{n}{d} $$

我们来看一下以上四种形式是否都可以成立。首先第一种形式:

$$ \frac{10i+n}{10i+d}=\frac{n}{d}\Leftrightarrow 10di+nd=10ni+nd \Leftrightarrow d=n $$

和题目要求相矛盾,不成立。再来看第二种形式:

$$ \frac{10n+i}{10d+i}=\frac{n}{d} \Leftrightarrow10nd+di=10nd+ni \Leftrightarrow d=n $$

和第一种形式一样,也不成立,再看第三种形式:

$$ \frac{10i+n}{10d+i}=\frac{n}{d}\Leftrightarrow10di+nd=10nd+ni\Leftrightarrow 9d(n-i)=i(d-n) $$

由于\(d>n\),所以要使得上式成立,则\(n>i\),对上式简单变换:

$$ n-i=\frac{i}{9}-\frac{in}{9d} $$

由于\(n>i\)\(n,i\in N\),则等式左边的\(n-i\)必然大于一;又由于\(i\le9\),则\(i/9\le1\),则等式右边必须要小于一,两相矛盾,则第三种形式也不成立。综上,满足题目要求的只能是第四种形式,则有:\(d(10n+i)=n(10i+d)\),对满足这一条件的进行筛选,对满足条件的分数分子分母分别相乘,并从分母中除以分子分母的最大公约数,即为所求。

from math import gcd

def main():
    nom,den = 1,1
    for i in range(1,10):
        for d in range(1,i):
            for n in range(1,d):
                if d*(10*n+i) == n*(10*i+d):
                    nom *= n
                    den *= d
    return den/gcd(nom,den)