Abstract
A solar car needs 5 fully charged batteries to run, and it depletes those batteries in 5 hours. The batteries are rechargeable, and solar panels on the car are able to charge 3 batteries simultaneously. It takes 3 hours for the solar panels to finish charging 3 batteries. Furthermore, batteries cannot be charging and in use at the same time. If the car always starts running as soon as 5 full batteries are available, and the solar panels can only operate if 3 empty batteries are available, how many batteries are needed so that the car can eventually run without stopping? We investigate this resource optimization problem and its different variations.
Systems often have inputs and outputs that utilize the same resources, and it is a common problem to minimize the amount of resources needed to reduce costs. For example, consider the following problem about a solar car. The car needs 5 fully charged batteries to run, and it depletes those batteries in 5 hours. The batteries are rechargeable, and solar panels on the car are able to charge 3 batteries simultaneously. It takes 3 hours for the solar panels to finish charging the batteries. Furthermore, batteries cannot be charging and in use at the same time. If the car always starts running as soon as 5 full batteries are available, and the solar panels can only operate if 3 empty batteries are available, how many batteries are needed so that the car can eventually run without stopping?
As a model for this rechargeable car battery problem, we consider a system of buckets that handle a certain kind of flow (electricity in the case of batteries, but the flow could also represent water, work, etc). The size of each bucket is 1. Each bucket has an inlet and outlet, and at most one of them is active at any moment; this corresponds to the restriction that the batteries cannot be in use and also be charging at the same time. Additionally, there is an inflow and outflow in the system, which each have a constant total flow speed of 1 per time unit. In the car battery problem, the solar panels correspond to the inflow (charging the batteries), running the car corresponds to the outflow (depleting the batteries), and the time units are measured in hours.
Let I and O be two positive integers dictating how the inflow and outflow of the system operate, respectively. When a bucket inlet is active, the inflow speed to the bucket is ; and when the outlet is active, the outflow speed is . The total input flow speed is 1; hence, I buckets are needed to accommodate the inflow. Similarly, the total output flow speed is 1; hence, O buckets are needed to produce the output flow. The inflow would therefore fill up I buckets in I time units, and the outflow would deplete O buckets in O time units. The system runs as follows.
At time 0, all buckets are empty. This is the initial bucket condition.
The input flow starts filling up I empty buckets at time 0 (the inlets of these I buckets are activated). When these I buckets are filled up (after I time units), another set of I empty buckets (if available) will immediately be allocated to take the input flow. If there are not I empty buckets, then the input flow stops until there are I empty buckets again.
At some point when there are O full buckets, the output flow initiates; the outlets of these O buckets activate and the output flow continues until they become empty (after O time units). Note that the initial output flow starts after time units (when at least O full buckets become available for the first time). When these O buckets are completely emptied (at which point they can again be reused for input flow), then the output flow initiates on another set of O full buckets (if available). If there are not O full buckets, then the output flow stops until O full buckets become available again.
Definition
(Stable Flow). Given enough buckets, both the inflow and outflow will eventually run continuously, since the inflow and outflow speeds match (both are 1). We will call flow with nonstop inflow and outflow stable flow.
We would like to find , the minimal number of buckets needed in the system such that a stable flow can eventually be reached.
We consider the following problems:
The base case (as described above): given I and O, find .
The case with a threshold T for initiating the output flow. In the base case, the output flow starts as soon as there are O full buckets. For this case, the output flow only activates when there are T full buckets, where (in the base case, T = O). Given I, O, and T, find .
The case with F0 initially full buckets at time 0. In the base case, there are 0 full buckets at time 0. For this case, there are F0 full buckets at time 0, where (in the base case, ). Given I, O, and F0, find .
The case with both a threshold T and F0 initially full buckets. This is the most general case, combining the two above cases. In this case, we relax the restraint on F0 to be . Given I, O, T, and F0, find .
It will be enough to solve case 4, since the other problems are special cases of case 4.
Example
For the car battery problem, the solar panels charge 3 batteries in 3 hours, so I = 3. The car runs on 5 batteries and depletes them in 5 hours, so O = 5. The car is able to run as soon as there are 5 fully charged batteries, so T = 5. Finally, there are no initially charged batteries, so . The system progresses as follows.
At time 0: the input flow starts filling buckets 0, 1, 2.
At time 1: buckets 0, 1, 2 are filled.
At time 2: buckets 0, 1, 2 are filled.
At time 3: buckets 0, 1, 2 are completely filled; not enough full buckets are available for the output flow, while the input flow starts filling buckets 3, 4, 5.
⋮
At time 6: buckets 0, 1, 2, 3, 4, 5 are completely filled; the output flow starts draining buckets 0, 1, 2, 3, 4, while the input flow moves on to buckets 6, 7, 8.
shows the system at time 6.
Solution
It is clear that having an unlimited number of buckets would eventually allow the system to have both flows run nonstop. So, we first assume that there are an unlimited number of buckets, and then find the maximum number of the buckets that are in use at once, which would be .
Definition
(States). Given PO such that and PI such that , we represent the state of the system where F buckets are full, O buckets are full, and I buckets are full by . In such a state, the output flow has been running on its current set of O buckets for time units, and the input flow has been running on its current set of I buckets for PI time units.
According to rules described by the problem statement, the state transitions to a new state after 1 time unit as follows.
If PO = 0 and , then in the next state F decreases by O and PO becomes O – 1.
If PO = 0 and F < T, then the outward flow stops, so PO stays at 0.
If , then PO becomes .
If , then in the next state F increases by I and PI becomes 0.
If , then PI becomes . Even if PI = 0, the input flow will still be guaranteed to continue because we assume there are an unlimited number of buckets; so, there will always be enough empty buckets to accommodate the input flow.
In the case where both PO = 0 and , F would transition to .
By definition, stable flow consists of nonstop outward and inward flows. Therefore, when the stable flow first starts, the output flow must have previously been stopped, and the input flow must have just finished completely filling enough buckets to allow the output flow to activate. This corresponds to a state of the form at the beginning of the stable flow (for some positive integer n).
Definition
(Stable States). Call a state stable if using this as the initial state allows the output flow to never stop (the input flow already runs continuously because of our assumption that there are an unlimited number of empty buckets). In other words, any stable state induces stable flow.
Note that all states that appear in the stable flow would be stable. Since the outward flow never stops, then PO iterates through the numbers , while PI loops through the numbers . Consequently, the cycle of states during stable flow has length . Furthermore, for each state that follows, the sum is invariant, since the inward flow rate matches the outward flow rate, and both flows never stop.
The progression of states in the car battery problem is shown in the following tables.
In this example, the stable flow starts with at time 12, and reappears at time 27, so the stable flow has cycle length . We can see that and are stable states, but is not stable because the outward flow stops between time 11 and 12.
Throughout the rest of the proof we let .
Lemma 1.
Let x be a positive integer and k be a nonnegative integer. If the state appears after , then .
Proof.
First, we claim that both the inflow and outflow do not stop in the time between and . Although need not be a stable state, the fact that means that both inward and outward flows do not stop during the time between the 2 states. Suppose it takes t time units to get from to . As both the inflow and outflow do not stop for the time between the 2 states, then PO and PI cycle in the manner mentioned earlier, so we have
Let t = aO and , so that . We have and ; therefore , i.e., . □
Lemma 2.
is stable if and only if .
Proof.
Consider the states of the form that appear after . By Lemma 1 we have . Combined with and , we get .
If is stable, we know that the output flow never stops. Thus, at any state , we must have so that there are enough full buckets to accommodate the output flow. Conversely, if we have for all possible states that come after , then the output flow never stops so we know is stable.
If , then for all possible k, , so the state is stable.
Now assume is stable. By Bézout’s lemma [Citation1, p.7–11], there exist integers m, n such that mO + nI = d. Since , we can stipulate without loss of generality that m > 0 by repeatedly adding I to m and subtracting O from n as needed. Now we have
If we let , then and . Then the state at after is , since the inflow and outflow run continuously. By our earlier work we must have ; hence, . This concludes the proof of Lemma 2. □
Lemma 3.
If , then is eventually followed by the state , where and .
Proof.
By Lemma 2, means is not stable, so by the definition of a stable state, the output flow stops at some point. Thus, there exists a state that appears after such that . From here, the output flow ceases, so is followed by
Let . From k < I we have , and we also have . Finally, by Lemma 1, . This, combined with , yields . This completes the proof of Lemma 3. □
Lemma 4.
Let y represent the unique number such that and . Then starting from the initial state, eventually the stable state is reached.
Proof.
Let , so that the initial state is . For any nonnegative integer i, we let the next state after (in chronological order) that is of the form be . By Lemma 3, we know the sequence exists and is strictly increasing until we have some xN such that for the first time. At this point is stable by Lemma 2, so it starts the stable flow, and becomes constant. Also by Lemma 3, the sequence is constant modulo d, so . This implies y = xN, so is a stable state that is eventually reached. □
Remark.
Because , we can find where the remainder is nonnegative and less than d.
Solution to original problem
Finally, we will answer the original problem. Let y be defined as in Lemma 4. As mentioned earlier, finding is equivalent to finding the maximum number of buckets that are required for any individual state to continue in the repeating cycle induced by .
First let us suppose . At any state with , there are F full buckets, O buckets required to accommodate the outward flow, and I buckets required to accommodate the inward flow (even if PI = 0, there must be I empty buckets available for filling). Therefore, for it suffices to maximize F. Since is invariant, then we must minimize . Let the state occur t time units after . Then
Suppose and . Then , so since and , then . Since then , so . Therefore, .
We now show this maximum is achievable. By Bézout’s lemma [Citation1, p.7–11], there exist integers m, n such that mO + nI = d, so
If we let then we get PO = d and PI = 0, so and achieves the maximum possible value of F. This yields a total of buckets as the maximum amount of buckets in use at once (for the case of ). In the example presented earlier, . The state requiring the most buckets is , which uses buckets.
Now suppose PO = 0. At any state , F + I buckets are necessary to allow both flows to continue running. However, , so at most buckets are in use for all of these cases as well.
Therefore, . However, recall that . The following theorem sums up all of our work.
Theorem 1
(Minimum number of buckets required for stable flow). Let a bucket system be defined by the input flow parameter I, output flow parameter O, threshold , and initial number of full buckets , and let . The minimum number of buckets required to eventually allow the system to have both input and output flows run nonstop is
The remainder modulo d should be interpreted as nonnegative and less than d.
Using our theorem, we can simplify the expression for for the 4 proposed problems as shown in the following table (with even more simplification when d = 1).
Table
As in the theorem, all the remainders modulo d should be interpreted as nonnegative and less than d.
Going back to the car battery problem, which has and , the theorem tells us that batteries are necessary to allow the car to eventually run without stopping.
Additional information
Notes on contributors
Raymond Feng
Raymond Feng ([email protected]) is currently a second year undergraduate studying Computer Science and Mathematics at MIT. He is most interested in combinatorics, number theory, and theoretical computer science. In his free time, he enjoys playing ultimate frisbee with MIT’s Grim Beavers.
Reference
- Jones GA, Jones JM. Elementary number theory. Berlin, Germany: Springer-Verlag; 1998.