Intereting Posts

Find limit with factorial
Recurrence $a_n = \sum_{k=1}^{n-1}a^2_{k}, a_1=1$
Is this integral right?
minimizing squared distance for point to a set of lines
Multiple-choice question about the probability of a random answer to itself being correct
Probability of particular subset of balls occurring in a larger set chosen from a total?
The composition of two convex functions is convex
Derivative of function with 2 variables
Primes congruent to 1 mod 6
Is each edge interpreted like a $2$-cycle?
Function which has no fixed points
Prove: $\int_0^1 \frac{\ln x }{x-1} d x=\sum_1^\infty \frac{1}{n^2}$
Prove or disprove statements about the greatest common divisor
Arithmetic-quadratic mean and other “means by limits of means”
How do I explain the Fundamental Theorem of Calculus to my teacher?

I am reading a computer science puzzles book.

And I get the following question –

“You have a five quart jug, a three quart jug and unlimited supply of water. How would you come up with exactly four quarts of water ?”

- Big-O proof showing that t(n) is O(1)
- Is a “network topology'” a topological space?
- Is there a polynomial-time algorithm to find a prime larger than $n$?
- Combinatorics/Task Dependency
- Number of bit strings of length $n$ with no $k_1+1$ consecutive 0s and no $k_2+1$ consecutive 1s.
- What are the theorems of mathematics proved by a computer so far?

The question is pretty simple and I figured the sequence of “water transfers” to solve it.

But there was an interesting side-note that I did not know.

The side-note said that as long as the two jugs size relatively prime, it is possible to find a pour sequence for any value between one and the sum of the jug sizes.

It is true for 5 and 3.

But I want to know if it is really generally true or not ? If it is, it is really cool! What is the theorem called ? Who discovered it ?

- Prove or disprove : $a^3\mid b^2 \Rightarrow a\mid b$
- Numbers represented by a cubic form
- How to solve for multiple congruence's what aren't relatively prime.
- Looking for an identity for characteristic polynomial of a matrix to the power of n
- Is $n=1073$ a strong pseudoprime to bases $a=260, 813?$
- Halting problem on finite set of programs
- Conditional expectation of product of Bernoulli random variables
- If every $0$ digit in the expansion of $\sqrt{2}$ in base $10$ is replaced with $1$, is the resulting sequence eventually periodic?
- Efficient way to determine if a number is Perfect Square
- Can the determinant of an integer matrix with a given row be any multiple of the gcd of that row?

Let two wine glasses A and B have capacities $a$ and $b$ ounces, where $a$ and $b$ are relatively prime positive integers, and $a\lt b$. Suppose we also have a large open barrel full of wine. We will show that for any integer $w$, where $0\le w\le b$, we can measure out $w$ ounces of wine. (This means that we can measure out any integer number $y\le a+b$ of wine ounces, as long as we don’t mind the stuff being possibly in two glasses. I don’t.)

It is enough to show that for any $r$, with $0\le r\lt a$, we can measure out $r$ ounces. For $w=qa+r$ for some $r$ between $0$ and $a-1$. So if we can measure out $r$ ounces, we can put this into B, and then get to $w$ by using glass A $q$ times.

The construction goes as follows. Suppose that at a certain stage we have $x_k$ ounces of wine in cup A. Fill cup B from the barrel, top up cup A from cup B, pour the contents of A into the barrel, or better, drink it. Keep on filling A from cup B, dumping the contents of A into the barrel when A gets full. After a while, the amount left in B will be insufficient to fill A, but pour it in anyway. Call the amount that is now in A by the name $x_{k+1}$. Then

$$b=(a-x_k)+an+x_{k+1}$$

for some integer $n$. It follows that

$$x_{k+1}\equiv x_k +b\pmod{a}.$$

Start with A empty, that is, with $x_0=0$. Then $x_1\equiv b\pmod{a}$, $x_2\equiv 2b\pmod{a}$, and so on.

But since $a$ and $b$ are relatively prime, the numbers $0,b,2b.3b,\dots, (a-1)b$ form a complete residue system modulo $a$. Thus the sequence $x_0,x_1,x_2,\dots,x_{a-1}$ runs, in some order, through all the numbers from $0$ to $a-1$. This completes the proof.

Yes, it is true. From Diophantine Equations on Wikipedia

The simplest linear Diophantine equation takes the form ax + by = c,

where a, b and c are given integers. The solutions are completely

described by the following theorem: This Diophantine equation has a

solution (where x and y are integers) if and only if c is a multiple

of the greatest common divisor of a and b. Moreover, if (x, y) is a

solution, then the other solutions have the form (x + kv, y – ku),

where k is an arbitrary integer, and u and v are the quotients of a

and b (respectively) by the greatest common divisor of a and b.

Look at the Wikipedia article for more details of a proof.

To try to connect things, consider the equation: 5x+3y=4 as x could represent the number of filling or emptying of the 5 quart jug while y represents the same thing for the 3 quart jug. If there was a common factor between these, this could be factored out so that any answer would be a multiple of that integer. Given that a solution is (2,-2) to that Diophantine equation, this could imply that one fills the 5 quart jug and empties it over the 3 quart jug a couple of times to get exactly 4 quarts assuming one has another container to hold the 4 quarts.

I’ll admit that I’ve seen this problem from Die Hard 3, so I know of an alternate solution.

Consider the case where there is a common factor between the jug sizes where one has jugs of size 8 and 12. Now, the greatest common divisor of 8 and 12 is 4 and thus any combination of pourings will leave you with a multiple of 4 for an answer as 8x+12y=4(2x+3y) and thus while one can easily solve 2x+3y=1, it is a bit different to solve 4(2x+3y)=1 where x and y are integer values as no solutions exist here.

In contrast, consider that if for a given pair of jug sizes that one can get exactly 1 of the unit then this could be repeated for any Natural number greater than 1 so to get any other value is rather easy if you can get 1.

The first part of my answer covers this in a general case, but for the sake of argument let’s take $5x+3y=z$. If $z=1$ then by inspection I can notice that x=-1,y=2 is a solution. There are many solutions as one could take that solution and make the parametrized solution of $x=-1+k,y=2-k$ for k being any integer. Now, if z is some other value, I could just multiply the initial solution to get that value. Thus, if $z=4$ then $x=-4,y=8$ is a solution which works as $5*(-4)+3*8=-20+24=4$.

This last part is fairly trivial to my mind if you remember that one can take an equation and multiply both sides by a non-zero value and maintain equality.

- Demystifying modular forms
- Does $ab=1$ imply $ba=1$ in a ring?
- Galois group of $x^4-2x^2-2$
- Smooth classification of vector bundles
- A hard problem from regular $n$-gon
- Need help with this geometry problem on proving three points are collinear
- Arbitrary non-integer power of a matrix
- Solving Cubic when There are Known to be 3 Real Roots
- How to prove that this function is primitive recursive?
- Lipschitz condition on a second order nonlinear ODE?
- Proving $k \binom{n}{k} = n \binom{n-1}{k-1}$
- Closed form for improper definite integral involving trig functions and exponentials?
- Why non-measurable sets exist?
- Finding an example of a discrete-time strict local martingale.
- If a commutative ring is semiprime and its prime ideals are maximal then it is von Neumann regular (absolutely flat).