OFFSET
0,1
COMMENTS
Start with 2 empty cups of sizes 3 and n and an unlimited supply of water. For each n, we start with (0,0), which means that both cups are empty, so it takes zero steps to reach that state. We can proceed to other states (i,j) by using one of the 3 operations on each step: "fill", "pour", or "transfer".
(1) To "fill (F)", choose a cup that is not completely full and fill it to its maximum capacity (there is an unlimited supply of water).
(2) To "pour (P)", choose a cup that is not completely empty and pour it all out so that the cup becomes empty.
(3) On a "transfer (T)", one cup is poured into the other. To transfer, choose a nonempty cup to pour from and a nonfull cup to fill up. The amount that is transferred is always the largest possible amount (up to the capacity of the cup being filled).
a(n) gives the number of states, (i,j) with i = 0..3, j = 0..n that cannot be obtained by these operations from (0,0).
REFERENCES
B. W. Jackson and D. Thoro, Applied Combinatorics with Problem Solving. Addison-Wesley, Reading, MA, 1990, Chap. 1, pp. 5-6.
FORMULA
a(n) = 2*(n-1)*sign(n mod 3) + (10*floor(n/3)+2)*(1-sign(n mod 3)).
Conjectures from Colin Barker, Jun 21 2020: (Start)
G.f.: 2*(1 + x^2 + 4*x^3 + 3*x^4 + 2*x^5) / ((1 - x)^2*(1 + x + x^2)^2).
a(n) = 2*a(n-3) - a(n-6) for n > 5.
(End)
EXAMPLE
a(4) = 6; for a(4) we have one cup that can hold 3 units of water and another cup that can hold n = 4 units. Starting with empty cups at (0,0), there are fourteen states that can be reached using the given operations. For example, the state (3,2) can be obtained with the sequence (0,0)->(0,4)->(3,1)->(0,1)->(1,0)->(1,4)->(3,2) by the operations F-T-P-T-F-T. However, there are six states (1,1), (2,1), (1,2), (2,2), (1,3) and (2,3) that cannot be obtained from the three operations. So a(4) = 6.
MATHEMATICA
Array[2 #2 (#1 - 1) + (10 Floor[#1/3] + 2)*(1 - #2) & @@ {#, Sign@ Mod[#, 3]} &, 67, 0] (* Michael De Vlieger, Jun 28 2020 *)
PROG
(Magma) [2*(n-1)*Sign(n mod 3)+(10*Floor(n/3)+2)*(1-Sign(n mod 3)) : n in [0..100]];
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
Wesley Ivan Hurt, Jun 20 2020
STATUS
approved