Local students, Mckenna and Spencer shared a video (shown to the left, or click here) that does an excellent job describing an algorithm to generate all possible measurement given jugs of n and m gallons. 

An important observation that they include is that we will only be able generate multiples of the greatest common factor of the size of the jugs. 

To explore this problem, I created an interactive Desmos graph where you can change the jug sizes and play around with pouring the water between these two. 

Using this visual, I demonstrate the solution for generating 4 gallons with 3 & 5 gallon jugs, and apply the algorithm Mckenna and Spencer shared to the 4 & 9, and 4 & 10 gallon jug problems, and discuss what is happening there.

In this video, I demonstrate a general argument for why we are only able to generate the mutliples of the greatest common factor of the sizes of the two jugs. 

Matthew, another local student, explored this problem and shared this hypothesis: "That if a puzzle is solvable, it can be put in the form: am + bn = x, where m and n are the cup sizes, x is the number you are trying to reach, and a and b are integers."

In the video to the left, I describe how equations like the one he described can be solved with our jugs of water!

This type of equation is called a Linear Diophantine Equation (in two variables, note: a, b, and x would all be constants when we apply the equation). Solving these types of equations has been studied for over a thousand years. These equations were first systematically solved by Hindu mathematicians around 500 AD (read more about these equations on Britannica) 

Not only is Matthew correct that this problem is solvable only if there is a solution to the equation am + bn = x as he described, but there is a Lemma called Bézout's Lemma, which states that this equation only has solutions if x, is a multiple of the greatest common factor of a and b, which is what we found earlier! 

In this video, I discuss a fun connection to this problem and modular arithmetic. While this doesn't necessarily help us to solve the problem at hand, it is a neat connection!

If you are interested in computer science, this problem also has some neat connections in that realm.  

By now,  we can easily identify if there is a solution to the question, "Can I measure X gallons of water with jugs of size M and N?" All we need to know is:

• Is X a multiple of the gcf of M and N?

• Is X less than or equal to M+N?

If the answer to both of those is yes, then a solution can be found!

But what is the solution? How would I actually have to fill and pour the jugs? We can answer this question using a State Space Representation (in other words, we need to represent the state of the two jugs -- how much was is in each?) and then searching the possible states to find how to get to our desired number. There are multiple search algorithms that can be used for this. 

If you're interest in how you could solve this problem via programming, consider reading this article by GeeksforGeeks.