100 枚硬币分堆最大化乘积

Penny Stack

专题: Algorithmic Programming / 算法编程
难度: L4
来源: QuantQuestion

题目详情

你有 100 枚 1 分硬币，可以任意分成若干堆，每堆放任意枚数。你的收益等于各堆硬币数的乘积。

例如分成 10、20、70 三堆，收益为 $10\cdot 20\cdot 70=14000$ 。

最优分法的收益可写为 $a\cdot b^c$ ，其中 $a,b$ 互素。求 $abc$ 。

You are given $100$ pennies. You may arrange these pennies into however many stacks you want and put as many pennies into each stack as you would like. You are paid out the product of the number of pennies among all of the stacks. For example, if you make three stacks of sizes $10, 20,$ and $70$ , your payout is $10 \cdot 20 \cdot 70 = 14000$ . The optimal arrangement of the pennies will give you a payout of $a \cdot b^c$ , where $a$ and $b$ are relatively prime. Find $abc$ .

解析

为了最大化乘积，应尽量把 100 分拆成尽可能多的 3（接近 $e$ 的整数）。

$100=3\times 33+1$ ，但留下的 1 不优；把一个 3 与 1 合并成 4，得到

4\cdot 3^{32}.

因此 $a=4,b=3,c=32$ ，所求 $abc=4\cdot 3\cdot 32=384$ 。

Original Explanation

We want to make the product as large as possible. Therefore, if we view the number of coins in each pile as a side length, we want to maximize our value as much as possible. A cube maximizes the volume here, which is the product of the side lengths, so we want to get to a cube or as close to it as possible. Let's start with $10$ stacks of $10$ , as $100 = 10 \cdot 10$ . If we divide each stack of $10$ into two stacks of $5$ , then we get a larger product, as each stack of $10$ now contributes $5 \cdot 5 = 25$ to our product instead of $10$ . Therefore, we now have $5$ stacks of $20$ . However, as $5 = 3+2$ and $3 \cdot 2 = 6 > 5$ , we should divide them up again. Now, we are going to try as many stacks of $3$ as possible. This would yields $33$ stacks of $3$ and a lone penny. However, this is not optimal, as removing one of our stacks of $3$ and putting it with the lone penny yields $4 \cdot 3^{32} > 3 \cdot 3^{32} = 3^{33}$ . As we can't divide $4$ into anything more optimal, our solution is $4 \cdot 3^{32}$ , so the answer to the answer is $4 \cdot 3 \cdot 32 = 384$ .