Teenagers Alice and Bob are getting into the back of their family car on a LOOOOOONG road trip. They each brought their own cell phone to pass the time, since Mom and Dad will just be chatting with each other in the front.
Before they leave they each dig for their car-to-phone charging cable. Alice pulls one out, but to Bob's dismay he has forgotten his. It's too late to go back, because the car has started moving!
The good news is that both phones use the same type of charger, so it can be shared. Even better news: Alice and Bob get along super well and are willing to share the charger, and they're both perfect mathematicians and logicians! They want to determine the longest they can BOTH be using their phones simultaneously, subject to the following restraints:
- Both phones start fully charged.
- Both phones have a 1-hour maximum battery life, regardless of what they're being used for.
- A phone that is charging will stop all power drain from the battery and refill it at half the rate (2 minutes charging refills one minute of battery life).
- A full battery, while plugged in, will remain full.
- The power cord can be instantly switched from one device to another.
- Plugging in a device at the very instant it hits zero power will not cause it to shut down.
- They are both continuously aware of the exact power level of both devices to any desired degree of accuracy.
Because they don't want to spend the entire trip moving the cord, they impose an additional rule:
- Charging periods must be in multiples of 5 minutes.
This means that if the phones get down to where each has only 4 minutes of battery after switching, it cannot be switched again, and one phone will drain completely.
They will measure the success of a tactic by looking at the length of time until either device hits zero power but cannot be plugged back in yet.
They know that the "easiest" case is not optimal, wherein they wait until the moment a device hits 0% to switch cords. That method is presented here, also to help demonstrate the problem (let the numbers reflect the remaining battery life at each stage for each user, and the * indicates who has the plug):
Start: A* = 60, B = 60 ... Wait 60 minutes
A = 60, B* = 0 ... wait 60 minutes
A* = 0, B = 30 ... wait 30 minutes
A = 15, B* = 0 ... wait 15 minutes
A* = 0, B = 7.5 ... wait 5 minutes (7.5 is not an option per rule #8)
A = 2.5, B = 2.5 ... Actually we could have not moved the charger last time, but there are 2.5 more minutes until one phone fails.
Total time: 172.5 minutes.
What strategy do Alice and Bob employ to maximize their simultaneous screen time?
Bonus: Can this be generalized for a different "charge rate" of C other than 1/2?