Two Users share One Recharge Cord

Mister B 09/19/2017. 3 answers, 1.544 views
mathematics

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:

  1. Both phones start fully charged.
  2. Both phones have a 1-hour maximum battery life, regardless of what they're being used for.
  3. 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).
  4. A full battery, while plugged in, will remain full.
  5. The power cord can be instantly switched from one device to another.
  6. Plugging in a device at the very instant it hits zero power will not cause it to shut down.
  7. 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:

  1. 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?

3 Answers


Mike Earnest 09/20/2017.

Credits to Bobson, who was the first person to answer this correctly. My solution initially had a mistake, now fixed.

Define a "unit" of charge as 2.5 minutes.

Initially, both siblings have 24 units. Depending on who has the charge cable, one sibling will lose two units and the other will gain a unit (unless they are already maxed out at 24) during each 5 minute period.

Two units are lost during the first 5 minute period, and at least one unit is lost during each subsequent period. Therefore, after 46 periods, there will be at most 48 – 2 – 45 = 1 unit of charge between the siblings. Since each sibling always has a whole number of units of charge, this means one sibling is empty after 46 periods. Thus, they can last for at most 46 • 5 = 230 minutes. Edit: At this point, they can last for at most half a period more by giving the empty sibling the cable and having the sibling with one unit run out in 2.5 minutes. Thus, they can last for at most 46½ • 5 = 232.5 minutes.

In fact, they can last for exactly that long by passing the charger back and forth every five minute period.

  • After the first round, the sibling with the charger has 24 units, and the other has 22.

  • After the second, this becomes 22 and 23.

  • Every two rounds, both siblings lose a unit, so after 44 more rounds they are at 0 and 1.

  • Edit: Finally, after half a round, they are at 0.5 and 0 units, but they cannot trade mid round, so they are done in the middle of this round.

5 comments
Bobson 09/19/2017
I appreciate your logic-based answer better than my actually sitting and trying it.
DqwertyC 09/19/2017
Had been in the process of writing essentially the same thing. My thought process was "The charger is less efficient when connected to a fully charged device, because it only cancels out charge used instead of also adding more charge to the phone. Thus the most efficient solution is the one where the charger is on a fully charged phone for the least amount of time."
1 ffao 09/19/2017
nit: they can last for longer than 230 minutes, see Bobson's answer
Mike Earnest 09/19/2017
@ffao yep, I messed up the edge case...
1 Mister B 09/20/2017
Marking this as correct because it identifies not only a high-result case, but the math showing that it must be the best case. Kudos on viewing the effect of each five-minute interval in terms of "units" of power. I know you had dropped the 2.5 minutes at first, but I still think this is the most complete response.

Steve 09/20/2017.

The explicitly stated rationale for rule 8 was that they don't want to spend the entire trip swapping the cable, implying a penalty for cable swapping... therefore an optimal solution must be the one that equals the maximum possible time whilst also minimising cable swaps.

One such solution would be to swap cables at any time when either:

A: the phone currently connected to the charger has 100% power (or will reach that level in less than 5 minutes in the general case), or

B: the phone not connected to the charger has less than 5 minutes charge remaining, and the phone currently connected has more.

i.e.

A* = 60, B = 60; wait 5 minutes (minimum time by rule 8)
A = 60, B = 55; wait 10 minutes (time taken to charge B to 100%)
A* = 50, B = 60; wait 20 minutes (time taken to charge A to 100%)
A = 60, B = 40; wait 40 minutes (time taken to charge B to 100%)
A* = 20, B = 60; wait 60 minutes (battery life of B)
A = 50, B* = 0; wait 50 minutes (battery life of A)
A* = 0, B = 25; wait 25 minutes (battery life of B)
A = 12.5, B* = 0; wait 10 minutes (by rule 8, 12.5 minutes not allowed)
A* = 2.5, B = 5; wait 5 minutes (battery life of B)
A = 5, B* = 0; wait 5 minutes (battery life of A)
A* = 0, B = 2.5; 2.5 minutes simultaneous screen time remains.

This has the same total INITIAL time (232.5) as Bobson and Mike's answers, but only has 10 cable swaps during that time.

However, the question asks for the longest they can be using their phones simultaneously... and as the trip is very long there can be more opportunities.

One strategy at this point is to keep swapping cables every 5 minutes from that point (as the other phone will always be below the battery threshold) - the sibling who receives the cable immediately turns their phone back on, and they get 2.5 minutes of simultaneous use before the battery in the other sibling's phone becomes completely drained - hardly enough time for a round of the 2 player game they're presumably playing between the two phones...

Instead, we can modify rule B so that it specifies that it only applies when the other phone is still switched on.

Thus the sequence can continue:

A* = 0, B = 2.5; wait 120 minutes (time taken to fully charge A)
A = 60, B* = 0; [Bob turns phone back on] wait 60 minutes (battery life of A)
A* = 0, B = 30; wait 30 minutes (battery life of B)
A = 15, B* = 0; wait 15 minutes (battery life of A)
A* = 0, B = 7.5; wait 120 minutes (time taken to fully charge A)

(5 minutes into the final period, they are both at 2.5 minutes remaining, so no point swapping)

The SECOND period of simultaneous use (and all subsequent periods) will be 112.5 minutes, and the cycle can complete every 225 minutes. Alice never has to turn her phone off (why should she - after all SHE remembered her cable), but no charging capacity is wasted, and Bob still gets to use his phone for half the time during the remaining duration of the trip.

The above rules should work for other positive charge rates too. For charge rates of 1 or more, both phones can be used indefinitely and will be continuously maintained with at least 55 minutes of charge (giving simultaneous use of the entire duration of the trip plus at least 55 minutes)

For negative charge rates (the charging cable doesn't actually add charge to the phone it merely prevents the battery from draining as fast - a situation I've actually seen in practice with some in-car chargers!), only 1 swap is necessary - at the point when Bob's battery is at or below the remaining capacity in Alice's phone (e.g. this would be triggered when Alice has 80% and Bob has 20% for a charge rate of -1/4)

2 comments
Peter LeFanu Lumsdaine 09/20/2017
Wonderfully exhaustive answer, but one case you’ve still missed: when the charge rate is below –1, i.e. the cable makes a phone drain faster? Of course, the easy answer here is “don’t use the cable” — so let’s add a constraint that one of them must still use the cable at all times…
Steve 09/20/2017
With that extra constraint, surely it's the exact same answer as a negative charge rate above -1... except if the ideal switching point isn't on a precise 5 minute boundary, you'd need to switch at the start of the 5 minute interval containing the ideal switching point, rather than the end of it.

Bobson 09/19/2017.

As the second most straightforward answer, here's the breakdown for what happens if they switch every 5 minutes. Note that the * indicates who just received the plug.

After   5 minutes: A  = 60,   B* = 55.
After  10 minutes: A* = 55,   B  = 57.5.
After  15 minutes: A  = 57.5, B* = 52.5.
After  20 minutes: A* = 52.5, B  = 55.0.
After  25 minutes: A  = 55.0, B* = 50.0.
After  30 minutes: A* = 50.0, B  = 52.5.
After  35 minutes: A  = 52.5, B* = 47.5.
After  40 minutes: A* = 47.5, B  = 50.0.
After  45 minutes: A  = 50.0, B* = 45.0.
After  50 minutes: A* = 45.0, B  = 47.5.
After  55 minutes: A  = 47.5, B* = 42.5.
After  60 minutes: A* = 42.5, B  = 45.0.
After  65 minutes: A  = 45.0, B* = 40.0.
After  70 minutes: A* = 40.0, B  = 42.5.
After  75 minutes: A  = 42.5, B* = 37.5.
After  80 minutes: A* = 37.5, B  = 40.0.
After  85 minutes: A  = 40.0, B* = 35.0.
After  90 minutes: A* = 35.0, B  = 37.5.
After  95 minutes: A  = 37.5, B* = 32.5.
After 100 minutes: A* = 32.5, B  = 35.0.
After 105 minutes: A  = 35.0, B* = 30.0.
After 110 minutes: A* = 30.0, B  = 32.5.
After 115 minutes: A  = 32.5, B* = 27.5.
After 120 minutes: A* = 27.5, B  = 30.0.
After 125 minutes: A  = 30.0, B* = 25.0.
After 130 minutes: A* = 25.0, B  = 27.5.
After 135 minutes: A  = 27.5, B* = 22.5.
After 140 minutes: A* = 22.5, B  = 25.0.
After 145 minutes: A  = 25.0, B* = 20.0.
After 150 minutes: A* = 20.0, B  = 22.5.
After 155 minutes: A  = 22.5, B* = 17.5.
After 160 minutes: A* = 17.5, B  = 20.0.
After 165 minutes: A  = 20.0, B* = 15.0.
After 170 minutes: A* = 15.0, B  = 17.5.
After 175 minutes: A  = 17.5, B* = 12.5.
After 180 minutes: A* = 12.5, B  = 15.0.
After 185 minutes: A  = 15.0, B* = 10.0.
After 190 minutes: A* = 10.0, B  = 12.5.
After 195 minutes: A  = 12.5, B* = 7.5.
After 200 minutes: A* =  7.5, B  = 10.0.
After 205 minutes: A  = 10.0, B* =  5.0.
After 210 minutes: A* =  5.0, B  =  7.5.
After 215 minutes: A  =  7.5, B* =  2.5.
After 220 minutes: A* =  2.5, B  =  5.0.
After 225 minutes: A  =  5.0, B* =  0.0.
After 230 minutes: A* =  0.0, B  =  2.5.
After 232.5 minutes, B runs out of power.

Passing it back and forth as often as possible is likely to be the best possible strategy, because it minimizes wasted charge time. This would hold true for any charge rate and time increment.

Related questions

Hot questions

Language

Popular Tags