Page 1 of 1

### Three Water Tanks

Posted: Wed Mar 09, 2016 8:57 pm UTC
There are three perfectly identical water tanks arranged so that each tank is equidistant from the other two. The tanks are interconnected with a pipe system, and each tank is filled to its maximum capacity with water. Your goal is to figure out the maximum capacity.

You know the volume of each tank is an integer number of liters. Based on the external size of each tank you are certain the capacity cannot exceed 200 Liters. However, there could be internal padding that reduces the capacity. Fortunately, each tank is equipped with a dispenser machine. You can input any (non-negative) integer number of liters and the machine may or may not drain the specified volume of water from the tank.
The dispenser machines follow these rules:
(Let the tank you are querying be Tank A. The other two are Tank B and C)

1. If you request more water than the maximum capacity, the dispenser will indicate "ERROR" and no water will be drained.
2. If there is enough water in Tank A to fulfill the request, the exact amount will be drained and the dispenser will indicate "SUCCESS".
3a. If the request is valid but Tank A does not have enough water, water will be pumped in, at equal rates, from B and C. Water will only stop pumping if A is completely filled or if B and C are both completely empty.
3b. Only after all pumping has stopped will the machine attempt to fulfill the request. If the request still cannot be fulfilled, the dispenser will indicate "ERROR" and no water will be drained. Otherwise, the request is fulfilled and the dispenser will indicate "SUCCESS".

The pumps are highly efficient. All pumping activities can be finished in the 5 minutes it takes you to move from one tank to the other. You also have no way of sensing any transfer of water in or out of each tank and rely on the dispenser machines to report the results of each operation.

Each machine is programmed to become unresponsive for 1 hour after every request. The machine will not display the result of the request until it "wakes up". How much time would you need to deduce the maximum capacity of each water tank?

Here is an abstracted version of the problem to clear up any confusion with wording:
Spoiler:
You have three bins. Each bin initially contains the same integer N, where N is in the range [0,200]. (Although it would be fun to see how solutions would change if N were different for different bins).
You can pick any single bin and request to have some positive integer, d, subtracted from the value of that bin. Let x be the current value in the bin you are trying to subtract from. Let y and z be the current value in each of the other two bins.

This algorithm is then executed:

If d > N:
Wait 1 hour, then return false
If x < d <= N:
Case 1: z >= (N-x)/2 && y >= (N-x)/2
set x = N,
set y = y-(N-x)/2
set z = z-(N-x)/2
Case 2: z < (N-x)/2 && y > (N-x-z)
set x = N
set y = y-(N-x-z)
set z = 0
Case 3: y < (N-x)/2 && z > (N-x-y)
set x = N
set y = 0
set z = z-(N-x-y)
Case 4 (default):
set x = x+y+z
set y = 0
set z = 0
If x >= d:
set x = x-d
Wait 1 hour, then return true
Else:
Wait 1 hour, then return false

As the user, you only have access to returned values. However, queries made to different bins can run in parallel. The CPU is super fast so there's no chance of collision when they are accessing the same resources.

### Re: Three Water Tanks

Posted: Thu Mar 10, 2016 1:58 pm UTC
* Does "perfectly identical" mean that each tank has the same capacity? Or do they just look indistinguishable on the outside but may have different capacities? (And if the tanks may be different, what is the "maximum capacity" for the purpose of rule 1: the current tank's, or the largest tank's?)
* Is a tank's minimum capacity 0 or 1?
* 200 l capacity ceiling for the whole system or per tank?
* You specify both "pumping from both other tanks at equal rates" and "pumping until both other tanks are empty". That's a contradiction. (Presumably it's "at equal rates as long as water is available in both other tanks", but do you want to comment on this?)
* What are the result request displays for? I can see it's a success if the dispenser dispenses water. I can see it's an error if the dispenser dispenses nothing. (Or does the dispensing operation also count as a "transfer" and is undetectable? That's not exactly how I would spontaneously understand the words "dispenser" and "transfer"; but maybe it is where you were going with this.)

### Re: Three Water Tanks

Posted: Thu Mar 10, 2016 7:50 pm UTC
Sorry the wording wasn't clear. I thought a word problem would be more interesting. I have added a more abstract version to the OP.

### Re: Three Water Tanks

Posted: Thu Mar 10, 2016 10:40 pm UTC
Can there wind up being a non-integer amount of water in any given tank? For example, if the capacity was 40 liters, and first you request 15 liters from tank A, so the division is 25:40:40, and then an hour later you request 40 liters from tank A. Would it fill up so that the ratio is 40:32.5:32.5? Or does it have to stay an integer, and wind up a liter short with 39:33:33?

### Re: Three Water Tanks

Posted: Fri Mar 11, 2016 3:48 am UTC
Poker wrote:Can there wind up being a non-integer amount of water in any given tank? For example, if the capacity was 40 liters, and first you request 15 liters from tank A, so the division is 25:40:40, and then an hour later you request 40 liters from tank A. Would it fill up so that the ratio is 40:32.5:32.5? Or does it have to stay an integer, and wind up a liter short with 39:33:33?

Yes, that is possible. You are not guaranteed integer volumes at all times. However you know the maximum capacity is an integer.

### Re: Three Water Tanks

Posted: Fri Mar 11, 2016 4:35 am UTC
It can be done in 7 hours, plus a negligible amount extra that accounts for time to react to each printout as it arrives, and to move from one tank's control panel to the next.

Note that the system is guaranteed to have enough water for at least the first three drainings that are less than or equal to an individual tank's capacity, since no request for more than one third of the total capacity can ever be granted. Beyond that, there can be no guarantees unless the amounts are spaced out far enough: suppose the tanks hold the maximum capacity of 200, and you try a binary search starting with 100, 150, and 175 so that all three tests come back successful. At this point it's impossible to disambiguate anything: the next test would be for 188, but that now returns failure since only 175 remains across all three tanks combined.

Start by guessing 128 on A and 182 on B, letting the tasks run simultaneously.
Depending on which of the tests come back successful, after the first hour you know whether you are in [0,127], [128,181], or [182,200].

If [182,200]:
Two drainings have been successful, so only one more can safely be assumed without having tests fail for an overall lack of water.
Guess 200 on A, followed shortly afterwards by 199 on B and 198 on C. Keep lowering the guesses in turn as soon as they become responsive again; once you get a hit, you are done. At worst you will have to keep checking down to the 185-184-183 triplet to see if it is one of those values, or 182 (in case all three tests fail on the last triplet). This will end no later than 7+epsilon hours (in order to make sure your A, B, and C intervals are properly staggered).

If [128,181]:
One draining request has been successful. This still leaves room for one more "inquiry" request while still guaranteeing enough water left to accommodate a followup request after that.
Guess 166 on B without running any guesses in parallel with that, using up the second hour to determine either [128,165] or [166,181].

If [166,181], continue as in the [182,200] case, starting at the top end and running 3 guesses at a time until you get a hit. The search space will be exhausted no later than 7+epsilon hours again.

If [128,165], then the "inquiry request" still hasn't been used up. Guess 153 on B, using up the third hour to determine either [128,152] or [153,165]. Predictably, that upper range has been crafted such that it will be exhaustible by the seventh hour.

If [128,152], use the fourth hour to guess 143. Any hit gives enough space to be exhausted in time, while continued error messages will lead the guess lower: 136 at hour 5, and 132 at hour 6. If it gets that far, the result of that test will decide whether the seventh hour is used to guess 135-134-133 or 131-130-129, by which time all space above 128 will clearly be exhausted either way.

If [0,127]:
All three tanks are still full--essentially, we're back in the base problem with zero drainings, but with a reduced upper bound and one hour elapsed.
Use the second hour to guess 74 on A and 112 on B. If both hit, the capacity can only safely be assumed for one more draining. 5 rounds of guesses will exhaust the space above 112.

If 74 hits but not 112, follow the same kind of procedure as in the [128,181] case: use hour 3 to guess 99, then if necessary lower the guess to 89 at hour 4, 82 at hour 5, and 78 at hour 6. Hour 7 will either test 81-80-79 or 77-76-75.

If both miss, then you're again in the initial state but with 2 hours gone and an upper bound of 73. Further tests can stay within the 7-hour bound by guessing as follows:
Hour 3: 36 and 61 (if only 36 hits, follow up by guessing in the sequence 51-44-40 unless there's a hit)
Hour 4: 11 and 26 (if only 11 hits, guess 19, followed by 15 if that misses)
Hour 5: 1 and 4

### Re: Three Water Tanks

Posted: Fri Mar 11, 2016 5:46 am UTC
Two points towards curiosityspoon's solution:

Minor point:

All pumping activities can be finished in the 5 minutes it takes you to move from one tank to the other.

So there's an epsilon for you - it takes 5 minutes to move between tanks.

Major point, in response to your first paragraph:

Let's take your example of having tests 100, 150, and 175 successful. The values could be anywhere from 75, 25, and 0 (at capacity 175) to 100, 50, and 25 (at capacity 200). Now, what would happen at this point if you made a request greater than 100? All the water would gather in one tank, but that amount could be anywhere between 100 and 175 (or at least, any amount equivalent to 1 modulo 3). So if you choose your request properly (say, 137) you could certainly disambiguate between values - it's just that this time, it will fail at lower values and succeed at higher values instead of the other way around.

In other words, a binary search is still theoretically possible at that point, as long as you make the right requests.

### Re: Three Water Tanks

Posted: Fri Mar 11, 2016 8:05 am UTC
That makes a simple quaternary search possible, in fact, and enables the space to be exhausted within 4 hours.

Start by putting in requests for 150, 100, 50

-If 150 hit (so we are in [150,200]), then the other two necessarily also hit. 300 has been drained, and 150-300 may be left overall.
Use the second hour to put in requests for 188, 175, 162 in that order. Note that there cannot possibly be enough water for more than one of these to hit.

--If 188 hit (so we are in [188,200]), then 488 has been drained, and 76-112 is left.
Use the third hour to put in requests for 103, 94, 85. Again, only one of these at most will be successful.

---If 103 hit, then 591 has been drained, so the tanks must hold at least 197 to have that capacity in the first place.
Use the fourth hour to request 9, 6, 3. Whichever one was successful (if any) can be added to 591, then that figure divided by 3 will give the capacity.

---If 103 didn't hit, but 94 or 85 did, then the bounds have been reduced to just three possible numbers, either [194,196] or [191,193].
Make just two requests in the fourth hour, at 6 and 3. This will be enough to disambiguate the possibilities.

---If even 85 didn't hit, we must be in [188,190], and 76-82 is left.
Use the fourth hour to request 82 and 79. A hit on either of these reveals 190 or 189 respectively; if neither hits then the answer is 188.

--If 188 didn't hit, the other two tests will reveal whether we are in [175,187], [162,174], or [150,161]. All of these intervals have fewer than 16 possibilities, so they can be distinguished within two more rounds of tests along similar lines to the above.
---[175,187] means 475 has been drained, and 50-86 is left. Request 80, 71, 62 at hour 3, then usually 6, 3 at hour 4 (59, 56, 53 if all miss)
---[162,174] means 462 has been drained, and 24-60 is left. Request 54, 45, 36 at hour 3, then usually 6, 3 at hour 4 (33, 30, 27 if all miss)
---[150,161] means 300 has been drained, and 150-183 is left. Hour 3 is then 159 (follow-up if it hits: 24, 21), 156 (if it hits: 18, 15), 153 (if it hits: 12, 9; if it misses: 152, 151).

-If 150 didn't hit, the other two tests will reveal whether we are in [100,149], [50,99], or [0,49]. All of these intervals have fewer than 64 possibilities, so they can be distinguished within three more rounds of tests. Depending on the specific numbers encountered so far, it will be possible to select a set of quartiles based on either the total amount drained or the maximum capacity. Just checking all the remaining numbers to make sure there are no peculiarities that make it impossible to disambiguate properly:

--[100,149]: 150 drained, 150-297 left; hour 2: 137, 125, 112
--This second round actually gives us a bit more information than the [150,200] case, since it's possible for round 2 test 1 to hit while still leaving enough left for one of the other tests to hit. So there are really 6 cases now.
---If 137 and 125 both hit, then we are in [138,149] with 412 drained and 2-35 left. Hour 3: 29, 20, 11; hour 4: 6, 3 (this works even if all miss and the disambiguation is between 8, 5, 2)
---If 137 and 112 both hit, then the answer is 137. (137 can't be the only hit with these numbers.)
---If 125 and 112 both hit, then we are in [129,136] with 0-21 left. Guess 18, 12, 6 in hour 3, and no matter what the outcome of this is, it will be narrowed down to two possibilities which can be distinguished by checking for 3 alone on the fourth round.
---If 125 hit but 112 didn't, then we are in [125,128] with 100-109 left. This case can be fully discerned by hour 3, guessing 109, 106, 103.
---[112,124]: 262 drained, 74-110 left; hour 3: 104, 95, 86; hour 4: 6, 3 (or 83, 80, 77 if all miss)
---[100,111]: 150 drained, 150-183 left; hour 3: 109 (then 74, 71), 106 (then 68, 65), 103 (then 62, 59) (102, 101 if all miss)

--[50,99]: 50 drained, 100-247 left; hour 2: 87, 75, 62
---If all three numbers hit, we are in [92,99] with 274 drained and 2-23 left. Hour 3: 20, 14, 8; hour 4: a single test for 3
---If just 87 and 75 hit, we are in [87,91] with 212 drained and 49-61 left. Hour 3: 61, 58, 55; hour 4 is only necessary if all miss and can be a single test for 52
---[75,86]: 187 drained (since 62 will also hit), 38-71 left; hour 3: 65, 56, 47; hour 4: 6, 3 (or 44, 41 if all miss)
---[62,74]: 112 drained, 74-110 left; hour 3: 72 (then 38, 35), 69 (then 32, 29), 66 (then 26, 23) (65, 64, 63 if all miss)
---[50,61]: 50 drained, 100-133 left; hour 3: 59 (then 28, 25), 56 (then 15, 12), 53 (then 55, 54) (52, 51 if all miss)

--[0,49]: 0 drained; hour 2: 37, 25, 12
---[37,49]: 74 drained, 37-73 left; hour 3: 47 (then 26, 23), 44 (then 20, 17), 41 (then 14, 11) (40, 39, 38 if all miss)
---[25,37]: 37 drained, 38-74 left; hour 3: 35 (then 9, 6), 31 (then 6, 3; answer is automatically 31 if 28 didn't hit), 28 (then 25, 22) (27, 26 if all miss)
---[12,24]: 12 drained, 24-60 left; hour 3: 21 (then 6, 3; answer is automatically 21 if 15 didn't hit), 18 (then 15, 12), 15 (then 17, 16) (14, 13 if all miss)
---[0,11]: 0 drained; hour 3: 9 (then 11, 10), 6 (then 8, 7), 3 (then 5, 4) (2, 1 if all miss)