CS5800 — AI Problem: Three Jars

Three jars hold integer quantities of water A, B, C. A pour operation picks two jars and transfers water from the larger to the smaller, exactly enough to double the smaller:

pour(X, Y) with X ≥ Y → (X − Y, 2Y)

Goal: design a sequence of pours guaranteed to reach a state where at least two jars hold equal amounts, starting from any positive integers A, B, C.

How This Works

This problem is hard to solve from scratch in a reasonable time. The intended approach is:

LLM Steps

Work through these in order. Each step is a starting point for a prompt — adapt the wording, try follow-ups, push back when the answer seems wrong.

LLM-0 Cold attempt

Give the LLM the problem statement as written. Read the answer carefully. Does it actually solve the general case, or only specific instances? Test it on inputs you pick yourself. Many first answers to this problem are wrong or incomplete — your job here is to notice that before moving on.

LLM-1 What does repeated pouring do?

Set the goal aside. Ask: if I keep pouring into jar A over and over, what happens to its value? What is the total water drawn from the source after k pours? Is there a closed form? Work one small example by hand before trusting the LLM's answer.

LLM-2 Subtracting a chosen amount from B

Now ask: can I make jar B lose exactly qA total, for an integer q I choose? What if at each step I get to pick whether to pour from B or from C into A — does that freedom help? Try constructing sequences for q = 5, 7, 13, and a large q with a small C. Ask the LLM to find the general pattern and verify it on your examples.

LLM-3 Choosing q and proving termination

You can now subtract any multiple of A from B. Which multiple should you pick so the jars are in a strictly simpler state afterward? Does this remind you of any classical algorithm? Ask the LLM to state a loop invariant and prove: (i) each round produces legal pours, (ii) something strictly decreases, (iii) termination implies the goal is reached. Check the proof on your examples — LLM termination proofs on this problem are often hand-wavy.

Deliverables

Q-1 Key ideas write yourself

A short informal explanation — half a page, no formal notation — of how the algorithm works. Imagine explaining it at a whiteboard to a sharp friend. Cover: why the goal simplifies, what repeated pouring gives you, how the third jar is used, and why the process terminates. This should be written entirely in your own words.

Q-2 Pseudocode and code LLM ok for code pseudocode yourself

Write the pseudocode yourself (not from LLM output). Then implement it in Python or Java — LLM help is fine here. Run on all four examples below and include the full pour sequence and final state for each.

Input (A, B, C)	Notes
(3, 28, 100)	Running example from class
(7, 11, 23)	Values close together
(1, 1023, 1025)	Large values; stress test
(your choice, all ≥ 500)	Pick something non-trivial

Q-3 Math writeup write yourself

Study whatever the LLM produces, but write every sentence yourself. Four sub-parts, each graded independently:

Q-3a. Prove that reaching two equal jars and reaching one empty jar are equivalent goals (up to one pour).
Q-3b. Describe one round precisely: given minimum A and second jar B, what pours are performed, and prove the total removed from B is exactly ⌊B/A⌋ · A.
Q-3c. State the loop invariant. Prove it is maintained, the minimum strictly decreases each round, and termination implies success.
Q-3d. Handle the edge cases: what if B mod A = 0? Does C always have enough water for every round, and how do you know?

Q-4 Complexity LLM ok

How many rounds does the outer loop run? How many pours per round? What is the total pour count as a tight asymptotic bound? Justify each answer.

Q-5 Comparison to BFS LLM ok

Describe the BFS approach: what are the states, what are the edges, how large is the state space in terms of A+B+C, and what is the worst-case runtime? Then compare directly to Q-4: how much better is the binary algorithm, and what structure does it exploit that BFS completely ignores?

Q-6 Office hours demo mandatory

Come to OH prepared to do three things without referring to your writeup:

Trace the algorithm by hand on an example the instructor picks.
Explain one sub-proof from Q-3 in your own words.
Answer a variant: what if the operation tripled instead of doubled? What if there were four jars? No right answer expected — these test whether you own the idea well enough to reason about it on the fly.

The demo is graded first. Q-1 through Q-5 are not fully graded until Q-6 is done.

Append your full LLM transcript to your submission. Include a sentence or two on which LLM steps needed the most back-and-forth, and which insights (if any) you feel came from you rather than the LLM.