The vaccine distribution conundrum

Question

The context is that of a pandemic that is spreading wildly and requiring global vaccination of the population.

You are working in a distribution center for the vaccines.

One day you have been requested to prepare and deliver 40 boxes of vaccines to 3 vaccination centers. You have a minivan and will do a roundtrip visiting each center once.

Unfortunately you haven't been told how many boxes each vaccination center needs. You will learn the need of each center only when you arrive there. It could even be that a center didn't order any vaccine for that day. You just know the total is 40 boxes.

The problem is that the boxes need to be delivered in refrigerated sealed containers. You can't reopen any container when delivering the boxes. You must deliver the containers still sealed.

You don't have to deliver exactly one container per center. You could just put each box in its own container. But it is a lot of work to refrigerate and seal a container. And you are lazy. So you want to figure out a better way to arrange boxes in containers in such a way that you are sure, regardless of the needs of each vaccination center, that you can deliver to each one the exact number of boxes they need.

Of course, you want to minimize the number of containers you need to prepare.

So, how many containers do you prepare and how many boxes do you put in each container?

Disclaimer: The events portayed in this puzzle are fictitious. Any resemblence to real events or situations is purely coincidential.

PS: clarification: The unit is the box, which is indivisible. The number of doses per box is irrelevant. All boxes are equal. The vaccination centers ordered an integer number of boxes. You cannot return boxes. You must pack exactly 40 boxes.

Answer 1

You are looking for a partition of $40$ with the minimum number of parts that is a common refinement of all $154$ partitions of $40$ into at most $3$ parts.

You can satisfy all $154$ scenarios with

8 containers:

14, 9, 6, 4, 3, 2, 1, 1

Note that no container can contain more than 14 boxes because the centers might demand 14, 13, and 13, respectively.

---

Update: I had initially assumed that the demands for all three centers were known upon reaching the first one, but I see now that the problem wording implies uncertainty about the remaining two centers upon reaching the first center. It turns out that enforcing "nonanticipativity" over the resulting $861$ scenarios yields the same solution as above.

I used integer linear programming, and one of the decision variables is how many containers to deliver to the first center, independent of the remaining two centers. The resulting solution for the first center is as follows:

0 = 0
1 = 1
2 = 2
3 = 3
4 = 4
5 = 1 + 4
6 = 6
7 = 1 + 6
8 = 2 + 6
9 = 9
10 = 1 + 9
11 = 2 + 9
12 = 3 + 9
13 = 4 + 9
14 = 14
15 = 1 + 14
16 = 2 + 14
17 = 3 + 14
18 = 4 + 14
19 = 1 + 4 + 14
20 = 6 + 14
21 = 1 + 6 + 14
22 = 2 + 6 + 14
23 = 9 + 14
24 = 1 + 9 + 14
25 = 2 + 9 + 14
26 = 3 + 9 + 14
27 = 4 + 9 + 14
28 = 1 + 4 + 9 + 14
29 = 6 + 9 + 14
30 = 1 + 6 + 9 + 14
31 = 2 + 6 + 9 + 14
32 = 3 + 6 + 9 + 14
33 = 4 + 6 + 9 + 14
34 = 1 + 4 + 6 + 9 + 14
35 = 2 + 4 + 6 + 9 + 14
36 = 3 + 4 + 6 + 9 + 14
37 = 1 + 3 + 4 + 6 + 9 + 14
38 = 2 + 3 + 4 + 6 + 9 + 14
39 = 1 + 2 + 3 + 4 + 6 + 9 + 14
40 = 1 + 1 + 2 + 3 + 4 + 6 + 9 + 14

In hindsight, this is just a greedy allocation. Use the largest available container and repeat until the demand is satisfied. But there are also non-greedy optimal allocations to the first center.

The optimization model enforces that the demands for the remaining two centers can always be satisfied after removing these containers.

Answer 2

Let us consider the series https://oeis.org/A005428

which starts with $a_1 = 1$ and proceeds with (0) $a_{n+1} = \left \lceil \frac {1 + \sum_{i=1}^n a_i} 2 \right \rceil$. First eight terms: 1,1,2,3,4,6,9,14

Let us write $A_n = \sum_{i=1}^n a_i$. First eight terms: 1,2,4,7,11,17,26,40

We will now show by induction that the following three statements are all true:

Note that wherever I say "set" below I should really have said "multi set" but that would have been tedious so I didn't.

1. For any unordered 3-partition $A_n = a^{(n)}_1 + a^{(n)}_2 + a^{(n)}_3$ there exists a 3-way (set) partition of $\{a_1,...,a_n\}$ such that the sums of the three subsets are $a^{(n)}_1,a^{(n)}_2,a^{(n)}_3$

2. For any $B<A_n$ there exists a subset S of $\{a_1,...,a_n\}$ such that for every 2-partition $B=b_1+b_2$ there exists a 2-way (set) partition of $S$ such that the sums of the two subsets are $b_1,b_2$

3. Any ordered sequence $\{b_1\le b_2\le ...\le b_n\}$ with property (1) has $b_i\le a_i$ for all $i$.

All three statements are easily verified for small $n$.

Now observe that by construction of $a_n$ the following holds:

4. Every 3-partition of $A_n$ has at least one term, $a^{(n)}_1$ say, which is $\ge a_n$.
A representation in terms of $\{a_1,...,a_{n-1}\}$ of the 3-partition $a^{(n)}_1-a_n,a^{(n)}_2,a^{(n)}_3$ of $A_{n-1}$ can therefore be made into a representation in terms of $\{a_1,...,a_n\}$ of the 3-partition $a^{(n)}_1,a^{(n)}_2,a^{(n)}_3$ of $A_n$ simply by adding $a_n$ to the first subset. This proves (1).

Similarly:

5. For every $b_1+b_2=B < A_n$ we either have $B \le A_{n-1}$ or at least one of $b_1,b_2$ is $\ge a_n$. In the second case we can proceeed essentially as above, the first case is trivial. This proves (2).

Finally,

6. Because we must always be able to cover the even split ($\pm \frac 2 3$) of $A_n$ the last and largest term $a_n$ cannot be larger than what it is assigned by the formation law (0). Assertion (3) if satisfied for $a_i,b_i$ for $i \le n$ thus implies $b_{n+1} \le \left \lceil \frac {1 + \sum_{i=1}^n b_i} 2 \right \rceil \le \left \lceil \frac {1 + \sum_{i=1}^n a_i} 2 \right \rceil = a_{n+1}$. This proves (3).

To summarize:

The series we have cited is the best solution for both the two-stage and the simultaneous partioning problems. From the proof of statement (2) we can also derive how to find the right subset in case of ambiguity.

Answer 3

When I wrote the question I had a more concrete solution in mind. The other answers given are very computational or mathematical. They don't really show how the solution is constructed imho.

So here is what I had in mind.

Since there are 40 boxes to distribute and only 3 centers, there must be at least one center that ordered 14 boxes or more. That is because if no center ordered more than 13, then the total could not exceed 39.
So we can prepare one container with 14 boxes and reserve it for the first center that requires that many boxes.

When you are done, you can see that you face the same problem again, but smaller:
You need to distribute the 26 remaining boxes without knowing in advance how many each center requires, (after deduction of the first container).
With 26 boxes total, one center needs 9 boxes or more (9 is 26/3 rounded up). So you can prepare a container with 9 boxes to be delivered to the first center that needs so many (possibly additionally to the 14-container).

An now you have 17 boxes to deliver under the same condidions...

When you repeat this process you get the sequence 14, 9, 6, 4, 3, 2, 1, 1.

This shows a solution that works and explains why it needs to be these numbers. It works without knowing the quantities in advance. When you reach a center, you fill the order by choosing first the largest containers possible. This ensures that the largest container gets delivered and the smaller ones are delivered according to the remaining needs.

Now, unfortunately, this doesn't prove optimality.
But you can see that in each iteration the container you prepare is the largest possible. For example the first container cannot have more than 14 boxes because the required amounts could be 14, 13, 13. A larger container couldn't be delivered. And there is the intuitive idea that larger containers are better, because it makes the the remaining problem smaller. This makes it plausible that the method is optimal. Or not too bad. It is not a proof, though.