The Optimal Toaster Problem

Question

Suppose I have 3 slices of bread, say $b_1$, $b_2$, $b_3$, and I want each to be double toasted. My toaster has a capacity of 2 slices at a time. The 'perfect' way of doing this would be to toast in the following manner - $(b_1,b_2),(b_2,b_3),(b_1,b_3)$. This 'perfect' strategy ensures that during each use of the toaster, I utilize both the toasting slots.
There does not exist a perfect strategy for toasting 3 slices of bread if I want my breads single toasted using the previous toaster.
Essentially, I want to know whether there exists a perfect strategy given that I have $T$ slices of bread, $K$ toasting slots in the toaster, and the vector $vec V in mathbb{N}^T$ . Here, $vec V$ describes the desired number of toasts for each bread.
If it is not clear, by perfect strategy I mean a strategy by which I will be utilizing all the slots of the toaster every time. Therefore, it is a 'yes/no' question. Perhaps, if possible, it would be great if we can also figure out the strategy as well.
I was thinking of this problem while toasting bread during breakfast and I have no idea as such on how to proceed!

Sudix · Answer

If we have $T $ slices of bread and want the slices to be toastes $vec V$ times, then if we had a single slot toaster, we'd need $sum vec V$ turns.
Since we have $K$ slots, we'll instead need at least $frac{sum vec V}K$ turns. 
Let's say that a strategy is perfect if it allows us to toast all toasts  to  the wished toastiness in $lceilfrac{sum vec V}Krceil$ turns.
Then we can find a perfect strategy for the toasting process, if one exists, by means of network flow (and therefore just as well using linear programming):
We create the graph as follows:

We create the source vertex $S_I$ and the sink vertex $S_O$.

We create a vertex $v_i$ for every toast.

We add a vertex $t_i$ for every turn.

For all $i$, we add an edge from the source $S_I$ to $v_i$ with capacity of $V_i$.

For all $i$ we add an edge from $t_i$ to the sink $S_O$ with capacity of $K$.

For all $i,j$ we add an edge with infinite capacity from $v_i$ to $t_j$

Now we search for a maximal flow in this graph. There's two outcomes:
Either we obtain a maximal flow that maximally utilizes all edges from $S_I$ to $v_i$. Then there exists a perfect strategy, and we con reconstruct it from the flow.
Or the maximal flow doesn't utilize all these edges maximally, in which case there is no perfect strategy.

The Optimal Toaster Problem

One Answer

Add your own answers!

Ask a Question