0
$\begingroup$

The Problem goes as follows:

There are 3 water containers of different sizes: 10 liters, 7 liters, and 3 liters.

If we start by having 10 liters of water in the 10 liters container, and

  • There is only 10 liters of water, you can’t spill it and you can’t get anymore water.
  • The only allowed operation is: fill water from one container to the other until the first one is empty or the other one is full

What is the minimum number of times you have to pour in order to get 5 liters of water in one container.

Apparently the answer is 8 times:

(x,y,z) = (water in 10 liters container, 7 liters, 3 liters)

starting with (10,0,0)

  1. (3,7,0)
  2. (3,4,3)
  3. (6,4,0)
  4. (6,1,3)
  5. (9,1,0)
  6. (9,0,1)
  7. (2,7,1)
  8. (2,5,3)

The Question is: Is there an algorithm that a human can do in order to find the optimal answer, i.e. like this how not to die hard with math video.

$\endgroup$
0
$\begingroup$

I would go about it by working backward, relying on the following two principles:

1) Every transition involves exactly two containers. At least one of the two involved containers must end either empty or full, and at least one of the three containers must begin the transition either empty or full.

2) In the fastest possible algorithm, no container can be ignored by two consecutive transitions, as those transitions either cancel each other out or can be combined into a single transition.

5L can be attained by pouring 1L into a container with 4L, pouring 2L into a container with 3L, pouring 3L into a container with 2L, pouring 4L into a container with 1L, pouring 1L from a container with 6L, pouring 2L from a container with 7L, pouring 3L from a container with 8L, pouring 4L from a container with 9L or pouring 5L from a container with 10L. It is trivial to rule out the possibilities of 10-5 and 9-4, as well as some of the sub-possibilities of 8-3, 7-2, and 6-1 as requiring more than 10L of water. It is also trivial to rule out reaching 5L via adding two smaller amounts, as it would require already having isolated 5L in the third container. This means that the final step must be pouring from one of the two larger containers into the smallest container. So the last step must begin as (listing the containers in order from largest to smallest) [2,5+x,3-x] or [5+x,2,3-x] and end as [2,5,3] or [5,2,3] respectively.

We then must consider how we can reach a setup of either [2,5+x,3-x] or [5+x,2,3-x]. In each step, we stop pouring only when the pitcher is empty or the receiver is full. Our penultimate step must end in one of these setups with a full and/or an empty container. If the penultimate step ended with an empty pitcher, than it must be the smallest pitcher which was empty and x=3. This means that the penultimate step involved one of the following transitions: [2-y,8,y]->[2,8,0] or [8,2-y,y]->[8,2,0]. This first of these possibilities is obviously impossible, as it would involve having 8L in a 7L container. The second of these possibilities is incorrect as well, as it would need to have a preceding infinite loop of transitions of [8,2,0]->[8,0,2]->[8,2,0]. (No other distribution of water can lead into this state other than the impossible situation of [8,1,1] which has neither an empty nor a full container). Therefore we can conclude that our penultimate step ends with a full pitcher. In order for the first pitcher to be full the full pitcher, we would need more than 10L of water. Therefore, our final step is [2,7,1]->[2,5,3].

Our penultimate step must involve filling the 7L pitcher. It has (repeating the use of x for convenience, although it may a different value from above) a transition of [2+x,7-x,1]. In order to for this to begin with a full or an empty container, x must be 7 or 8. x=8 is impossible because it would involve having a negative quantity of water in the medium container, so the last two steps are [9,0,1]->[2,7,1]->[2,5,3].

We then consider the previous transition. It cannot involve pouring between the largest and smallest containers, as that would necessitate ending in a [7,0,3] or [10,0,0] arrangement, and not the [9,0,1]. Therefore, the previous transition involved emptying the medium container into one of the two other containers. As the next transition involves pouring from the largest into the medium container, this transition must involve the smallest container, and will be [9,1,0]->[9,0,1].

We then must how to reach [9,1,0]. The next transition ignores the largest container, so this transition must involve the largest container. We cannot have poured from the largest container, as the transition of [10,0,0]->[9,1,0] is impossible. As such, the transition involved pouring from one of the two smaller containers into the largest container. As no container is full at the end of the step and the smallest container is the only empty container at the end of the step, the transition is [9-x,1,x]->[9,1,0]. The only possibility for x that has us beginning the transition with a full or an empty container is x=3, so our transition is [6,1,3].

Our previous step must have involved filling the smallest container and must involve the medium container, so our it is [6,1+x,3-x]->[6,1,3]. In order to begin with an empty or a full container, x=3 and the last five transitions are [6,4,0]->[6,1,3]->[9,1,0]->[9,0,1]->[2,7,1]->[2,5,3].

In a similar vein, our previous step must involve pouring 3L from the smallest container into the largest container, which must have been preceded by filling the smallest container from the medium container, transitioning from a state of [3,7,0]. This state can be achieved from our initial state, so the fastest method of measuring 5L of water is [10,0,0]->[3,7,0]->[3,4,3]->[6,4,0]->[6,1,3]->[9,1,0]->[9,0,1]->[2,7,1]->[2,5,3].

Using the same principles, one could find a solution (if one exists) for solve such a problem for any set of possible sizes for the three containers, any initial condition of water distribution, and any goal for amount of water isolated. The choice of 3,7,10 and a goal of 5 resulted in distinct solution, although changing various parameters could result in multiple methods of the same minimal number of transitions or an impossible goal.

(Multiple methods of the same minimal number of transitions requires having two possible transitions leading to a single intermediate (or final) state without violating either of the initial two principles. If such a situation arises, one must attempt each of those paths to find the shortest method, as any number of those paths can result in possible methods of reaching the end state, and different valid paths might be different lengths. An impossible goal will involve either working backwards and finding an intermediate state that has no possible preceding state or entering a loop where the only possible preceding state for some intermediate state is a state that is necessarily achieved in a later transition.)

The principles of the algorithm must be adapted to adjust for at least four containers.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.