0236 豪华礼盒
* * * *
拉格朗日计划
* * * *
豪华礼盒

供应商A和B为提供以下数量的商品:

                商品        A       B 
                鲟鱼子酱    5248    640 
                圣诞蛋糕    1312    1888 
                猪肉火腿    2624    3776 
                典藏波特    5760    3776 
                香槟松露    3936    5664 
              
尽管供应商十分努力地使商品保持良好状态,但损耗(比如变质)总是不可避免的。

供应商用两种不同的统计量来比较他们的表现:

商品损耗率是每种商品的变质数量除以每种商品的供应量。

总损耗率是所有商品的变质数量除以所有商品的总供应量。

令人惊讶的是,若就五种商品各自的损耗率而言,则B的表现都比A差(损耗率更高),且B的损耗率都是A的m倍($m>1$),但若计算总损耗率,A的表现却更差,且其总损耗率也是B的m倍。

共有35个不同的、满足上述情况的m,其中最小的是$1476/1475$。求其中最大的m,并将答案写成$u/v$的最简分数形式。

本题难度:



解答

相当无聊的问题,数字繁琐而无明显规律。

设$a_1,\ldots, a_5$和$b_1,\ldots,b_5$是A、B这五种商品各自的损耗量,则有 $$\frac{41b_1}{5a_1}=\frac{41b_2}{59a_2}=\frac{41b_3}{59a_3}=\frac{90b_4}{59a_4}=\frac{41b_5}{59a_5}=\frac{u}{v}=m, $$ 显然,只需确定一组$a_i,b_i$,就可以确定$u,v$,从而可以根据$u,v$确定其它$a_j/b_j$的值,然后通过枚举$\gcd(a_j,b_j)$依次尝试$a_j,b_j$可能的取值,其中只要有值满足总损耗率条件 $$\frac{a_1+\ldots+a_5}{b_1+\ldots+b_5}=\frac{295u}{246v}$$ 就说明$u,v$是一组可取的值。

似乎$a_1,b_1$上限的乘积累最小,因此选择枚举$a_1,b_1$,对每一组$a_1,b_1$的数据及其所确定的$(u,v)$有 $$a_j=41vk_j/d, \quad b_j=59uk_j/d, \quad j=2,3,5$$ 其中$d=\gcd(41v,59u)$以及 $$a_4=90vk_4/d', \quad b_4=59uk_4/d', $$ 其中$d'=\gcd(90v,59u)$,因此 $$a_1+\ldots+a_5=a_1+(41k_2+41k_3+41k_5)v/d+90vk_4/d' ,\quad b_1+\ldots+b_5=b_1+(59k_2+59k_3+59k_5)u/d+59k_4u/d' $$ 若记$d'=d_2+d_3+d_5$,就有 $$295u(b_1+(59k_2+59k_3+59k_5)u/d+59k_4u/d')=246v(a_1+(41k_2+41k_3+41k_5)v/d+90vk_4/d' )$$ 只要$a_2,\ldots, a_5$和$b_2,\ldots, b_5$不超过各自的商品总数,就检查上式,直到收集完35组m为止。最终结果是$123/59$。

import fractions
s=set()

a=1
while a < 5249 and len(s) < 35:
    b=1
    while b < 641 and len(s) < 35:
        if 41*b>5*a:
            d=fractions.gcd(5*a,41*b)
            u,v=41*b/d,5*a/d
            if (u,v) not in s:
                d1=fractions.gcd(41*v,59*u)
                d4=fractions.gcd(90*v,59*u)
                k1=3
                found=False
                while not found and 41*v*(k1-2)/d1 <= 3936 and 59*u*(k1-2)/d1 <= 5664:
                    k4=1
                    while not found and 90*v*k4/d4 <= 5760 and 59*u*k4/d4 <= 3776:
                        if 295*u*(b+59*k1*u/d1+59*k4*u/d4)==246*v*(a+41*k1*v/d1+90*v*k4/d4):
                            found=True
                        k4+=1    
                    k1+=1
                if found:
                    s.add((u,v))
                    print "current size:", len(s), "current max:", max([fractions.Fraction(u,v) for u,v in s])
        b+=1
    a+=1

print max([fractions.Fraction(u,v) for u,v in s])