This Is Really An Addition Problem

Define the cost of adding two numbers together as its sum. For example, adding \(1 + 2\) has cost 3. When we want to add two numbers, the cost is easy to compute, but when we want to add more numbers, there are various ways to do the additions, by choosing which two numbers to add next. While all of them will give the same sum, not all of them will give the same total cost.

For example, suppose we want to add the numbers 1, 2, 3, and 4. There are various ways to do this. As examples:

  • Add 1 and 2 together (getting 3), then add our 3 with the original 3 (getting 6), then add our 6 with the 4 (getting 10). This is represented as \((((1+2)+3)+4)\), and its cost is \(3 + 6 + 10 = 19\).
  • Add 3 and 4 together (getting 7), then add our 7 with the 2 (getting 9), then add our 9 with the 1 (getting 10). This is represented as \((((3+4)+2)+1)\), and its cost is \(7 + 9 + 10 = 26\).
  • Add 1 and 2 together (getting 3). Add the original 3 and the 4 together (getting 7). Add our 3 and our 7 (getting 10). This is represented as \(((1+2)+(3+4))\), and its cost is \(3 + 7 + 10 = 20\).

There are 18 ways to add those four numbers. Out of all of them, the minimum cost is achieved when we add \((((1+2)+3)+4)\), with cost 19.

There are approximately \(1.374 \times 10^{284}\) ways to add 100 numbers. What is the minimum total cost of adding these 100 numbers?

×

Problem Loading...

Note Loading...

Set Loading...