Euros in Bundles

A non trivial brainteaser for the Internship Interview at JP Morgan & Chase

You are given 100 euros. You may arrange these euros into however many stacks you want and put as many euros into each stack as you would like. Your payout would be the product of the number of euros among all of the stacks. For example, if you make three stacks of sizes 20, 20, and 60, your payout is 20 x 20 x 60 = 24000 . The optimal arrangement of the euros will give you a payout of a * b^c ,where a and b are relatively prime. Find a, b and c.

Try to solve this problem yourself before moving on to the solution below

.
.
.

.

.

.

---

Solution

We will solve it by divide and conquer method.
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 maximise our value as much as possible. A cube maximises 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. 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 * 5 = 25 to our product instead of 10. Therefore, we now have 5 stacks of 20. However, as 5 = 3 + 2 and 3 * 2 = 6 > 5, we should divide them up again. Now, we are going to try as many stacks of 3 as possible. This would yield 33 stacks of 3 and an extra euro. However, this is not optimal, as removing one of our stacks of 3 and putting it with the lone penny yields 4 * 3^{32} > 3* 3^{32} = 3^{33}. As we can't divide 4 into anything more optimal, our solution is 4 * 3^{32}, so the answer to the answer is 4, 3, 32

.

.

😃 Over to you: Were you able to solve this?

---

👉 If you liked this post, don’t forget to leave a like ❤️. It helps more people discover this newsletter on Substack and tells us that you appreciate solving these weekly questions. The button is located towards the bottom of this email.

👉 If you love reading this newsletter, feel free to share it with friends!