|
| |
|
|
A335756
|
|
A cup filling problem starting with 2 empty cups of sizes 3 and n, where a(n) is the number of unreachable states (see details in comments).
|
|
0
|
|
|
|
2, 0, 2, 12, 6, 8, 22, 12, 14, 32, 18, 20, 42, 24, 26, 52, 30, 32, 62, 36, 38, 72, 42, 44, 82, 48, 50, 92, 54, 56, 102, 60, 62, 112, 66, 68, 122, 72, 74, 132, 78, 80, 142, 84, 86, 152, 90, 92, 162, 96, 98, 172, 102, 104, 182, 108, 110, 192, 114, 116, 202, 120, 122, 212, 126, 128, 222
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
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.
|
|
|
LINKS
|
|
|
|
FORMULA
|
a(n) = 2*(n-1)*sign(n mod 3) + (10*floor(n/3)+2)*(1-sign(n mod 3)).
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
|
|
|
|
STATUS
|
approved
|
| |
|
|
