Should be Bézout's identity

Logic Level 3

You are given 3 tiny empty unmarked volumetric flasks of capacities 11 ml, 14 ml, and 18 ml. Because they are unmarked, you can only pour water from one flask to another. Until the initial flask is empty or the other is full. What is the minimum number of moves to fill up 16 ml of water into the 18 ml flask?

Details and Assumptions

What is a "move"?

Filling a flask,
Emptying a flask,
Pouring water from one flask to another.

13 14 9 12 10 11

6 solutions

Pi Han Goh
May 20, 2014

$\begin{aligned} 0 \space, & 0 & , \space 0 \\ 11 \space, & 0 & , \space 0 \\ 0 \space, & 11 & , \space 0 \\ 11 \space, & 11 & , \space 0 \\ 8 \space, & 14 & , \space 0 \\ 0 \space, & 14 & , \space 8 \\ 11 \space, & 3 & , \space 8 \\ 11 \space, & 0 & , \space 8 \\ 0 \space, & 11 & , \space 8 \\ 0 \space, & 14 & , \space 5 \\ 11 \space, & 3 & , \space 5 \\ 0 \space, & 3 & , \space 16 \\ \end{aligned}$

How would you justify that is the minimum number of steps?

Calvin Lin Staff - 7 years ago

Short answer : I don't know. I was hoping for someone to post a mathematical solution.

Long answer : I basically branch out all possible few initial steps and eliminate all "circular" branches. I read somewhere (I forgot the source) that this type of problem can be solved using Bézout's identity. I didn't understand most of what they are talking about. If I were to try to explain the math behind it: the "gaps" between the three numbers $\{ 11,14,18 \}$ are $\{ 3,4,7 \}$ . And I find the gaps between these six numbers are $\{ 4,7,8,11,14,15,18 \}$ . Repeat the process until I get the element $\{ 16 \}$ in the set. Then I work backwards to get the answer. My working appears flimsy at best so I refrained from justifying a mathematical solution.

Pi Han Goh - 7 years ago

This is not the minimum step i can prove that :- (1)0,0,18
(2)11,7,0 (3)4,14,0 (4)4,0,14 (5)4,14,14 (6)4,12,18 (7)4,12,0 (8)0,0,16

Sanatan Samkalp - 6 years, 12 months ago

@Sanatan Samkalp – Your math looks wrong from step 5 to 6. How does the 14ml beaker lose 2ml while the 18ml beaker gains 4ml?

Kevin Luddy - 6 years, 10 months ago

@Kevin Luddy – Does step 2, pouring into two different beakers, constitute just a single move?

If so I can do it in 10!

Step 6 is incorrect. It does not balance, as Kevin mentioned.

Amanda Hulme - 6 years, 10 months ago

18- 11 = 7 this is 2 steps

14-11 = 3, 7 + 3 =10 this is 3 steps

14-11 = 3, 10 + 3 = 13 this is 3 more steps

14-11 = 3, 13 + 6 = 16 this is 3 more steps.

Total steps, 11

Luis H - 5 years, 1 month ago

A spin off, i vote that repitition is far easier (11,0,0) (0,11,0) (11,11,0) (8,14,0) (0,14,8) (0,0,8) (11,0,8) (0,11,8) (11,11,8) (8,14,8) (0,14,16)

Christoffer Iversen - 4 years, 9 months ago

Very nice!!

Pi Han Goh - 4 years, 9 months ago

where does 13 come from in last two count.

Shyam Singh - 7 years ago

Whoops. I meant 3.

Pi Han Goh - 7 years ago

Wow grt (y)

Ankit Wasankar - 7 years ago

What happened after step 7 ?

Manmeswar Patnaik - 7 years ago

I empty the $14 \mathrm{m} \ell$ beaker.

Pi Han Goh - 7 years ago

He emptied both of the smaller flasks into the last one.

S Pal - 6 years, 10 months ago

nice one pi.

Shyam Singh - 7 years ago

01) 00-00-11 02) 00-11-11 03) 00-11-11 04) 00-14-08 05) 08-14-00 06) 08-00-00 07) 08-00-11 08) 08-11-00 09) 08-11-11 10) 08-14-08 11) 16-14-00 Hit and trial

Shubham Kumar Singh Rajput - 7 years ago

After u got 8 in the 18 flask if u do the same steps again u will get 16 in the 18 flask faster (less than that by 1 step)

Omar Sakr - 7 years ago

1 step is also used to empty the 14ml flask

Anurag Shekhar - 7 years ago

This can be solved in 8 moves

Fill 18
Dump 18 into 3 (leaving 15ml in 18)
Dump 18 into 14 (leaving 1ml in 18)
Dump 18 into 11 (leaving 1ml in 11)
Fill 18
Empty 3
Dump 18 into 3 (leaving 15ml in 18)
Dump 11 into 18 (leaving 16ml in 18)

Conner Webb - 5 years, 1 month ago

Dump 18 into 3? I don't have a flask that can measure 3ml.

Pi Han Goh - 5 years, 1 month ago

if any1 can prove me wrong :- (1)0,0,18
(2)11,7,0 (3)4,14,0 (4)4,0,14 (5)4,14,14 (6)4,12,18 (7)4,12,0 (8)0,0,16

Sanatan Samkalp - 6 years, 12 months ago

(6) is supposed to be 4,10,18. Check your math

raman rai - 6 years ago

Agnishom Chattopadhyay
May 25, 2014

Here is my attempt for a mathematical proof of why Pi Han Goh's method is optimal:

First, trying to solve the equation 11a+14b+18c= 16 for a, b and c integers: We get that the smallest possible absolute values are a=3, b=-2, c=0

I'm not sure how to show that these are the smallest coefficients, but one way is a proof by exhaustion, i.e, you prove that it is not working for values lower than that by showing each case one by one.

This is the basic algorithm:

Start by taking water in the 11l flask and start pouring towards the 14l flask whenever possible. Store the newly measured quantities in the 18l flask. Express those quantities in the form 11a+14b too. If a possible addition or subtraction operation can be achieved that will take a towards 3 and b towards -2, then it needs to be done.

Note that $a = 4$ .

I started out with something like this. However, after looking at Pi Han's solution, I realized that I didn't account for being able to pour away 'random' amounts of water. For example, in this step $11, 3, 8 \rightarrow 11, 0, 8$ , he poured away 3 liters of water. This thus screws up the assumption that we must have $11a + 14b + 18 c = 0$ .

If we make the assumption that you can only pour away full beakers, I still can't completely justify that there needs to be 11 steps. We have

4 steps for filling up the 11ml beaker 3 times.
At least 4 steps for pouring out from the 11ml beaker.
At least 1 step for emptying the 14 ml beaker. (because we can still leave 14ml behind)

This gives us 9 steps. The additional steps comes in because it can take 2 or more steps to empty out the 11ml beaker, but I'm uncertain how to quantify that a step is wasted. My process is as follows

1) 11, 0, 0
2) 0, 11, 0
3) 11, 11, 0
4) 8, 14, 0 (this is where a step is wasted)
5) 8, 0, 0
6) 0, 8, 0 7) 11, 8, 0
8) 5, 14, 0 (this is where a step is wasted)
9) 0, 14, 5
10) 11, 14, 5
11) 0, 14, 16

Calvin Lin Staff - 7 years ago

My solution was: (0, 0, 0)-(11, 0, 0)-(0, 11, 0)-(11, 11, 0)-(8, 14, 0)-(8, 0, 0)-(0, 8, 0)-(11, 8, 0)-(5, 14, 0)-(0, 14, 5)-(11, 14, 5)-(0, 14, 16), the same as yours. With the assumption you can only pour away full beakers, I can show this is optimal. That said, the solution is a computer proof. I generate a graph where each node is a possible state of the jugs. So, each of the stages above is a node, and there are clearly many more. I only include states where all but one of the jugs is either completely full or empty. Then, I add arcs to the graph, corresponding to each move (each arc has weight 1). I don't include pouring away "random" amounts of water (maybe I'll add this and get back to you). So, now, each possible move and state is on the graph. I then use Dijkstra's algorithm to find the shortest route from (0, 0, 0) to any of (0, 0, 16), (11, 0, 16), (0, 14, 16), (11, 14, 16).

Results:

Quickest route from (0, 0, 0) to (0, 0, 16) is along arcs (0, 0, 0)-(11, 0, 0)-(0, 11, 0)-(11, 11, 0)-(8, 14, 0)-(8, 0, 0)-(0, 8, 0)-(11, 8, 0)-(5, 14, 0)-(0, 14, 5)-(11, 14, 5)-(11, 0, 5)-(0, 0, 16) with weight 12 Quickest route from (0, 0, 0) to (11, 0, 16) is along arcs (0, 0, 0)-(0, 14, 0)-(0, 0, 14)-(0, 14, 14)-(0, 10, 18)-(10, 0, 18)-(10, 0, 0)-(10, 14, 0)-(11, 13, 0)-(11, 0, 13)-(11, 14, 13)-(0, 14, 13)-(11, 14, 2)-(11, 0, 16) with weight 13 Quickest route from (0, 0, 0) to (0, 14, 16) is along arcs (0, 0, 0)-(11, 0, 0)-(0, 11, 0)-(11, 11, 0)-(8, 14, 0)-(8, 0, 0)-(0, 8, 0)-(11, 8, 0)-(5, 14, 0)-(0, 14, 5)-(11, 14, 5)-(0, 14, 16) with weight 11 Quickest route from (0, 0, 0) to (11, 14, 16) is along arcs (0, 0, 0)-(11, 0, 0)-(0, 11, 0)-(11, 11, 0)-(8, 14, 0)-(8, 0, 0)-(0, 8, 0)-(11, 8, 0)-(5, 14, 0)-(0, 14, 5)-(11, 14, 5)-(0, 14, 16)-(11, 14, 16) with weight 12

Thus, the shortest way to get to having 16ml in the 18ml beaker is in 11 moves.

Bhavik Mehta - 7 years ago

Indeed. I agree that it is essentially tedious case cracking of numerous scenarios, which is best left to a computer.

Calvin Lin Staff - 7 years ago

How do I show that this is optimal?

Agnishom Chattopadhyay - 7 years ago

solved it in 8 steps

Sanatan Samkalp - 6 years, 12 months ago

Sujay Sheth
May 25, 2014

0,0,18

0,14,4

11,3,4(mark 2nd flask with 3ml)

11,0,7

8,3,7

8,0,10

5,3,10

5,0,13

2,3,13

2,0,16

So answer is 10

YOU CAN'T MARK THE BEAKERS!

Pi Han Goh - 7 years ago

18- 11 = 7 this is 2 steps

14-11 = 3, 7 + 3 =10 this is 3 steps

14-11 = 3, 10 + 3 = 13 this is 3 more steps

14-11 = 3, 13 + 6 = 16 this is 3 more steps.

Total steps, 11

Luis H - 5 years, 1 month ago

How did you get the question right to be able to write a solution? The answer is $11.$

Trevor B. - 7 years ago

@Trevor B. you used your brain that to think that we are only able to write a solution when our answer is write, but you didn't used your brain completely as we get 3 tries and in the 1st try he might have tried 10 but got it wrong, so then in 2nd or 3 rd try he might have tried 11 to get it right by guess work or something like that............ So use your brain wisely :-)

Kunal Mandil - 7 years ago

A Brain? I do not have one. Can I buy one on ebay?

Agnishom Chattopadhyay - 7 years ago

Even so if you cannot justify your answer, your solution is wrong. @Kunal Mandil

Mardokay Mosazghi - 7 years ago

@Mardokay Mosazghi – @Mardokay Mosazghi for your kind information i haven't posted any solution so how it can be wrong...... Please let me know......

Kunal Mandil - 7 years ago

@Kunal Mandil – If you actually don't think the answer is right, report the problem.

Ashwin Padaki - 6 years ago

Buddy we dont have any pen to mark

Varun Singla - 7 years ago

i solved it in 8

Sanatan Samkalp - 6 years, 12 months ago

Amanda Hulme
Aug 1, 2014

step1) 11,0,0 step2) 0,0,11 step3) 11,0,11 step4) 0,11,11 step5) 11,11,11 step6) 8,14,11 step7) 8,0,11 step8) 0,8,11 step9) 11,8,11 step10) 5,14,11 step11) 0,14,16

If you can pour into two beakers in one step, then step 10 can be omitted.

Varun Singla
May 28, 2014

-This is my solution :) - 0.0.0

11.0.0
0.11.0
11.11.0
8.14.0
0.14.8
0.0.8
11.0.8
0.11.8
11.11.8
8.14.8
0.14.16

bro it's solved in 8

Sanatan Samkalp - 6 years, 12 months ago

Brahmam Meka
May 26, 2014

0,0,0 11,0,0 0,11,0 11,11,0 8,14,0 0,14,8 0,0,8 11;0,8 0,11,8 11,11,8 8,14,8 0,14,16

Should be Bézout's identity

6 solutions

0 pending reports