Non Contradictory proof -
A general proof goes like the way, that there are 5 nos,
a1 _ a2 _ a3 _ a4 _ a5.
Now, since there are only 2 symbols available, '<' and '>', there will be repetitions of symbols. And since the question demands that the sequence should not be changed, so there will always be a 3 chain.
For all possible combinations, with minimum occurrence of each symbol = 2, a 3 chain sequence can be formed by deleting. For eg.-
1. a1 < a2 > a3 < a4 > a5 | Chain - a1 < a2 < a4 or a2 > a4 > a5
2. a1 > a2 < a3 > a4 < a5 | Chain - a1 > a3 > a4 or a2 < a4 < a5
Answering the question in the form they asked -
Part 1 -
Now we assume a1 < a2.
So, the 5 numbers would be - a1 < a2 _ a3 _ a4 _ a5.
Proof by contradiction -
For propositon, lets assume, there is no 3-chain, but a3 > a1. There arise 2 possibilities, which are -
1 - a1 < a2 < a3
2 - a1 < a3 < a2
The first case cannot be taken(It forms the 3 chain)! In the second case, when we introduce a4, there are 4 possibilities,as -
1 - a4 < a1 < a3 < a2
2 - a1 < a4 < a3 < a2
3 - a1 < a3 < a4 < a2
4 - a1 < a3 < a2 < a4
As we can see, all of them have a chain, (4,3,2),(4,3,2),(1,3,4),(1,2,4).
Thus, our assumption that a3 > a1, gave no possible combinations.
Thus our assumption was wrong!!
Part 2 -
Proof by contradiction -
From part 1, we know that a3 < a1, the possible combinations that can be made from the three numbers are -
1 - a3 < a1 < a2
We are given the equation, a3 < a4 < a2, then the proposition will be, a4 < a3 or a4 > a2. This is just converse of the given statement.
Adding a4 to the equation, we get combinations as-
1 - a4 < a3 < a1 < a2
2 - a3 < a1 < a2 < a4
As we can see, both the combinations give a 3-chain combinations as (4,3,2),(1,2,4).
Thus the assumption that a4 < a3 or a4 > a2 is false, because it is given that there is no 3 - chain to be formed!
Part 3 -
Proof by contradiction -
From previous part, and the assumptions in this part, we know that the combinations can be -
1 - a3 < a4 < a1 < a2
2 - a3 < a1 < a4 < a2
The proposition for the proof can be that, adding a5 doesn't makes any 3 chain.
Adding a5 to the equation, the possible positions can be -
1 - a5 < a3 < a4 < a1 < a2
2 - a3 < a5 < a4 < a1 < a2
3 - a3 < a4 < a5 < a1 < a2
4 - a3 < a4 < a1 < a5 < a2
5 - a3 < a4 < a1 < a2 < a5
Every possible combination has a 3 - chain. (5,3,1),(5,4,2),(3,4,5),(3,4,5),(1,2,5).
Thus the assumption for a5 can be added to the equation, is wrong!!
In similar manner, the fourth part can be proved!!
Yes, the algorithm is always optimal. The reason is that once you've decided which jug to fill first, there's nothing you can do that makes sense at any point other than what the algorithm says.
Suppose we have just poured from A to B. Then, because we stopped pouring, it must be the case that either A is empty or B is full. (Or both are true, in which case we have achieved nothing we couldn't do just by filling up B from the beginning).
If A is empty, then pouring back from B to A immediately will just put us in the state we just came from. Either emptying or filling B will erase all of our hard work, so the only sane thing to do is to fill A from the tap, and then continue pouring from A to B.
If B is full, then pouring back from B to A immediately would still be pointless (at least from the point of view of getting a shortest solution) because we could have done that instead of pouring from A to B in the first place. Either emptying or filling A would lose our work so far, so the only thing to do is to empty out B, and then continue pouring from A to B.
Thus, in an optimal sequence every pour goes in the same direction: either always from A to B or from B to A. You can compute how long it will take to reach $c$ in each case by using the extended Euclidean algorithm (as Joffan describes) rather than actually doing the simulation one pour at a time, though.
Best Answer
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.