What! Only Two Pots?

Relevant wiki Linear Diophantine Equations

---

This problem can be translated as

Find integers $x$ , $y$ such that $173x+271y=1$ and $|x|+|y|$ is minimal.

Firstly, it's important to note that a solution exists because $\gcd(173,271) | 1$ .

It is well known that once a single solution of this equation is found, infinitely many solutions can be found. In fact,

$x = x_1 + 271n \\ y = y_1 - 173n$

provide all the solutions for some integer $n$ and a solution $(x_1, y_1)$ . But finding a single solution looks like a task difficult enough because guessing gives no luck.

However, Bezout's lemma (backtracking Extended Euclidean Algorithm) provides an easy way to find the solution. On performing the process, $(x,y)=(47,-30)$ can be obtained. Now we just need to find the minimum solution. Using the previously obtained formula,

$x = 47 + 271n \\ y = -39 - 173n$

provides all the solutions. It is not hard to see that when $|n| \geq 1$ , $|x| + |y|$ increases monotonically. Hence the minimal value occurs when $n=0$ . $x=-47$ and $y=30$ is indeed the minimum, and so the answer is $|30|+|-47| = 77$ .

I just got this weird solution, by instinct. I actually wonder why it works (can someone explain, please?) We get that $173x-271y = 1$ .

Now, we get the coefficients and transform it into an ordered pair, $(173, 271)$ . We then replace the larger of the two elements of the ordered pair and replace it with its residue modulo the smaller one. i.e.

$(173, 271) \implies (173, 271 \pmod{173}) \implies (173, 98)$ .

We continue doing this until we get

$(173, 271) \implies (173, 98) \implies (75, 98) \implies (75, 23) \implies (6, 23) \implies (6,5)$

And we stop there, since $6-5 = 1$ . Again, I have no idea why this works.

Next, we start off using the fact that $(6-5 = 1)$ and use that and the ordered pairs $(173, 271) , (173, 98) , (75, 98) , (75, 23) , (6, 23) , (6,5)$

$6-5 = 1 \implies 6 - 23 + 18 = 6 - 23 + 3(6) = 1 \implies 4(6) - 23 = 1$

Can you see where I am going with this?

$4(6) - 23 = 4(75 - 69) - 23 = 4(75) - 12(23) - 23 = 4(75) - 13(23) = 1$ .

$4(75) - 13(23) = 4(75) - 13(98 - 75) = 4(75) + 13(75)- 13(98) = 17(75) - 13(98) = 1$ .

$17(75) - 13(98) = 17(173 - 98) - 13(98) = 17(173) - 13(98) - 17(98) = 17(173) - 30(98) = 1$ .

$17(173) - 30(98) = 17(173) - 30(271 - 173) = \boxed{47(173) - 30(271) = 1}$

Therefore, removing water $30$ times and adding water $47$ times will fill the pot with one liter, assuming Ron will have something to do with that liter and a large pot capable of holding a lot of water (One can actually make a problem out of this, what is the smallest possible capacity of the pot such that this insanity can be made possible). Anyways, there are a total of $30 + 47 = 77$ actions, so our answer is $\boxed{77}$ .