MathLabs

第4题

证明并求出所有和为 19761976 的正整数之积的最大值。
第 6/6 步:利用模 33 的余数
通俗地说

模 22 的余数 33 选定了一个 22,而不是零个或两个;其余总和全部用于最高效的因子 33。

1976=3⋅658+2,f(S)=2⋅36581976=3\cdot658+2,\quad f(S)=2\cdot3^{658}
详细分析

由于 1976=3⋅658+21976=3\cdot658+2,且 22 的个数至多为两个,所以 22 的个数恰好为一个:两个 22 的贡献为 4≡1(mod3)4\equiv1\pmod3,而一个 2 的贡献为 2(mod3)2\pmod3。剩余总和为 1974=3⋅6581974=3\cdot658,故最优多重集含有一个 22 和 658658 个 33,乘积为 2⋅3658\boxed{2\cdot3^{658}}。