Puzzling Asked on May 30, 2021
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.
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
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.
Correct answer by RobPratt on May 30, 2021
Let us consider the series https://oeis.org/A005428
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.
All three statements are easily verified for small $n$.
Now observe that by construction of $a_n$ the following holds:
Similarly:
Finally,
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.
Answered by loopy walt on May 30, 2021
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.
Answered by Florian F on May 30, 2021
Get help from others!
Recent Questions
Recent Answers
© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP