Dante's Infernal Puzzle Collection -- 8. Aggruppamento

Ten packs, one thousand people in total.

We can rephrase this question as "What are the ten natural numbers with which, by summing one or more of them, we can make any integer in [1, 1000]?"

Let's approach this sequentially -- we will start with 1 and see if it must be included in our group of 10 natural numbers. Then we will think about 2, 3,..., 1000 in the same way.

First, we know that 1 has to be one of those ten numbers -- otherwise, we wouldn't be able to make 1.

We also know that 2 needs to be there as well. If we skip 2, there's no way we can make 2.

3 doesn't have to be included, because we can make 3 by adding 1 and 2.

So far, we only have 1 and 2 on our list, which means the highest number we can form is 1 + 2 = 3. This means that we need to include 4 in our list. Thus the list becomes {1, 2, 4}.

We already know that 1, 2, and 3 can be formed with {1, 2}. Adding these to 4, we know that we can create any number in [1, 7] with {1, 2, 4}. But since we can't make 8 yet, we need to add 8 to the list.

Now it's just induction. We know that any number in [1, 7] can be formed with just {1, 2, 4}. This implies that with {1, 2, 4, 8}, we can make any number in [1, 7+8], or [1, 15]. So we add 16 to the list, which now becomes {1, 2, 4, 8, 16}. Continuing this way, the final list is {1, 2, 4, 8, 16, 32, 64, 128, 256, 512}. However, recall that the sum of all the 10 numbers should be 1000, which means we should have 1000 - 1 - 2 - 4 - 8 - 16 - 32 - 64 - 128 - 256 = 489 instead of 512.

Notice that Virgil says that four of those numbers are needed to form 300. Those four numbers would be 4, 8, 32, and 256.

Answer: 1, 2, 4, 8, 16, 32, 64, 128, 256, 489