Obtaining the perfect volume of petrol

This graphical solution not only shows what volumes are possible, but lists, in order, the actual filling/emptying steps needed to get to any desired volume (if it is possible to do so).

This graph has dimensions 12 x 9, and is set at a 60 degree slant. Start at the bottom right (12,0), travel at a 60 degree angle up to the top (3,9) and continue with 60 degree reflections as long as you are able. The coordinates tell you what to do:

(12,0) start with the 12L can full and the 9L can empty.

(3,9) fill the 9L can from the 12L can (leaving 3L in the 12L can)

(3,0) empty the 9L can.

(0,3) transfer the 3L contents of the 12L can into the 9L can.

The red path terminates at (0,9) without ever touching on a boundary coordinate with the value 8 in it, so it is not possible to get exactly 8L in either can.

You can also start from the top left of the graph (0,9) - with the 12L can empty and the 9L can full - and go backwards over the same red path.

It takes quite a while to set up the graph, but - once you have it - the red path will tell you, step-by-step, the fill/empty operations necessary to produce any desired volume that is possible.

Since 12 and 9 are both multiples of 3, the only volumes that can be obtained exactly will also be multiples of 3.

A volume is obtainable if and only if it is a multiple of the gcd of 12 and 9 - that is a multiple of 3. But 8 is NOT divisible by 3.

Relevant wiki: Greatest Common Divisor - Problem Solving

Using the general method, we get the equation $12a + 4 = 9b$ , where $a$ and $b$ are integers

Listing out possible values of $12a + 4$ and $9b$ , there will be no integer values of $a$ and $b$ to satisfy this equation so 8 can never be obtained.

General method of solving

I'll be using this question as an example to explain.

++ means filling it to the brim

-- means emptying

--> means transfer to the right can

<-- means vice versa

You would realise that there are only ++ on the left, -- on the right and only -->,

because doing the opposite will always result in working backwards, which is counter-productive (you won't get new integers)

Whenever we transfer to the right we will get either (x, 19) or (0,y), where

0 < x < 13

0 < y < 19

(x, 19): If we empty the left, we will get (0, 19), deleting our ‘new value’ (not productive)

(0, y): If we fill the right, we will be ‘masking our new integer’ which does not help at all

Since we started with 13 and then transferred right, we cannot do otherwise but add on the left, empty the right and transfer right. This only allows us to do the same and so on.

General formula

Now, let's look at this geometrically/graphically:

This geometric representation follows the rule that we can only refill the left, transfer right and empty the right. I recommend you to study the graph and do some arithmetics to prove that it is an appropriate representation

After that, you will realise that this has something to do with modulus as the containers gets filled and emptied, just like the remainnder of $x/3$

The arrows pointing down represent the 13-litre can

The ones pointing right represent the 19-litre can

A line of gradient 1 is drawn from the origin

At (0,0), the y-value matched the tip of vector AC, meaning that the 13 is full

The x-value matched the base of vector AB, meaning that the 19 is empty

When the graph $y=x$ touches vector AB, it means that 13-litres have been transferred (isosceles right angled triangle)

The y-value corresponds to the base of vector AC and the tip of vector DB, meaning that the left can is empty and it is going to be refilled

When the graph intersects vector DB, it means that an “emptiness” of 6 litres have been transferred from 19-litre can to the 13-litre can because vector AB and DB meet with their arrows pointing towards each other rather than away

This representation follows the rule that we can only add on the left, empty the right and transfer right in order to take the minimum number of steps

From the graph, we know that the 13-litre can is going to contain our desired integer first.

Every intersection point on the graph represents two things:

• The refilling of 13-litre can
• The emptying of the 19-litre can

Each vector of gradient 1 also represents the transferring step

Since the points land on the horizontal and vertical vectors, the number of points are equal to the number of horizontal and verical vectors

Hence, if we want to get 1 litre, the number of steps is equal to 4 intersecting points + 4 vectors of gradient 1 = 2 x 4 intersecting points = 2 x (2 horizontal + 2 vertical) = 8

Notice that I ignored the last point J since it implies emptying the 19-litre so I did not draw and count the last '13' vector

We can formulate this equation from the graph

$19a=13b+12$ rather than $19a=13b-1$ since we ignored the 3rd '13' vector

Note that the $b$ in the second equation is one more that the other $b$ in the first equation.

Where a and b are integers

$a$ represents the number of ‘19’ vectors

$b$ represents the number of ‘13’ vectors

This is also asking of what is the number that is divisible by 19 and leaves a remainder of 12 when divided by 13

The number is 38 and

$a=2$ , $b=2$

This is equal to $4\times2=(a+b)\times2=8$ , which is proved correct

General method of solving:

Let $x$ and $y$ be the maximum integer volumes

Let $a$ and $b$ be integers

Let $r$ be the remaining volume you want to obtain

$ax+(x-r)=by$ for starting with x

Solve for $a$ and $b$ using the Chinese Remainder Theorem

Add $a$ and $b$ then multiply then by 2 and there you go!!

Using the method to get a remainder of 8 litres:

$13a+5=19b$

$a=4$

$b=3$

Ans: 14

We will get 46 if we started with 19

By the way, the graph can be compacted, being very similar to A lot of reflections and Law of reflection

There must be a third container that is 2L to get 8

12 and 9 litre cans can only accommodate multiples of 3 between them. It is impossible to obtain 2L from any sequence.

Guys, Exactly 8L each would ammount to 16L in total. And initially there are 17 (12+9) L, hence it would never be possible to 17=16.