This week the question is: Can You Pour the Water?

I have two large pitchers with known volumes: 10 liters (“pitcher A”) and 3 liters (“pitcher B”). They are both initially empty. I can do one of six things with the pitchers:

1. I can fill pitcher A to the top with water from the sink.
2. I can fill pitcher B to the top with water from the sink.
3. I can empty the contents of pitcher A into the sink.
4. I can empty the contents of pitcher B into the sink.
5. I can transfer the contents of pitcher A to pitcher B, until pitcher A is empty or pitcher B is filled to the top—whichever comes first.
6. I can transfer the contents of pitcher B to pitcher A, until pitcher B is empty or pitcher A is filled to the top—whichever comes first.

Every time I do any one of the above six, it counts as a step.

What is the fewest number of steps required until one of the pitchers (either A or B) contains precisely 5 liters of water?

And for extra credit:

Instead of 10 liters and 3 liters, suppose the volumes of the pitchers A and B are now 100 liters and 93 liters, respectively.

Further suppose that the fewest number of steps needed until one of the pitchers (either A or B) contains precisely N liters of water is f(N), where N is a whole number between 1 and 100, inclusive.

What is the maximum value of f(N), and for which value of N does this occur?

Læs mere: #ThisWeeksFiddler, 20240329

Highlight to reveal solution:

Studying the general problem, there are only 2 interesting chains of steps:

• Method 1:
  • Fill the large pitcher from the sink.
  • While the content of the large pitcher is more than can be added to the small pitcher:
    • Fill the small pitcher from the large pitcher.
    • Empty the small pitcher into the sink.
  • Empty the large pitcher into the small pitcher.
  • Repeat.
• Method 2:
  • Fill the small pitcher from the sink.
  • While the content of the small pitcher is less than can be added to the large pitcher:
    • Empty the small pitcher into the large pitcher.
    • Fill the small pitcher from the sink.
  • Fill the large pitcher from the small pitcher.
  • Empty the large pitcher into the sink.
  • Empty the small pitcher into the large pitcher.
  • Repeat.

Converted to our problem, where the goal is to reach 5 liters, it looks like this. The progression is described by noting, how many liters are in each pitcher.

A	B		A	B
0	0		0	0
10	0		0	3
7	3		3	0
7	0		3	3
4	3		6	0
4	0		6	3
1	3		9	0
1	0		9	3
0	1		10	2
10	1		0	2
8	3		2	0
8	0		2	3
5	3		5	0

Both methods need 12 steps, before a 5 occurs. So the answer is 12 steps.

And for extra credit:

The general methods developed above are still valid. Let’s look at the first few steps:

A	B		A	B
0	0		0	0
100	0		0	93
7	93		93	0
7	0		93	93
0	7		100	86
100	7		0	86
14	93		86	0
14	0		86	93
0	14		100	79
100	14		0	79
21	93		79	0
21	0		79	93
0	21		100	72

The general rules here are:

• It takes 1 step to reach either 93 or 100.
• It takes 2 steps to reach 7, 6 steps to reach 14, 10 steps to reach 21, etc.
• It takes 4 steps to reach 86, 8 steps to reach 79, 12 steps to reach 72, etc.

We can write this in another way:

• f(93) = 1
• f(100) = 1
• Left column:
  • f(7n) = 4n – 2, 1 <= n <= 14 (7 * 14 = 98)
• Right column:
  • f(93 – 7n) = 4n, 1 <= n <= 13 (93 – 7 * 13 = 2)

Next question is, what happens then?

A	B		A	B
0	91		100	2
100	91		0	2
98	93		2	0
98	0		2	93
5	93		95	0
5	0		95	93
0	5		100	88

• Left column:
  • f(98) = 54
  • f(5) = 56
  • f(7n + 5) = 4n + 56, 0 <= n <= 13 (7 * 13 + 5 = 96)
• Right column:
  • f(2) = 52
  • f(95) = 56
  • f(88) = 58
  • f(95 – 7n) = 4n + 54, 1 <= n <= 13 (95 – 7 * 13 = 4)

Continuing this way we get:

• Left column:
  • f(96) = 108
  • f(3) = 110
  • f(7n + 3) = 4n + 110, 0 <= n <= 13 (7 * 13 + 3 = 94)
• Right column:
  • f(4) = 106
  • f(97) = 110
  • f(90) = 112
  • f(97 – 7n) = 4n + 108, 1 <= n <= 13 (97 – 7 * 13 = 6)

Almost there.

• Left column:
  • f(94) = 162
  • f(1) = 164
  • f(7n + 1) = 4n + 164, 0 <= n …
• Right column:
  • f(6) = 160
  • f(99) = 164
  • f(92) = 166
  • f(99 – 7n) = 4n + 162, 1 <= n …

We’ve reached an area, where the 2 series will meet in the middle.

• Left column:
  • f(43) = 188
  • f(50) = 192
• Right column:
  • f(57) = 186
  • f(50) = 190

As 190 < 192, the solution is 190 steps. Whew!