This is the official solution. However, I was not able to understand the solution given for C, It gave me ( 0,0, 2^n – 4 ) at the end not 4n..
(a) A configuration is given by a pair of natural numbers (i, j), where i is the number
of coins of type t1 and j, the number of coins of type t2. Starting from (n, 0) and
repeatedly casting the spell s1, we get the following sequence of configurations:
(n, 0) (n − 1, 2) (n − 2, 4) · · · (n − i, 2i) · · · (2, 2(n − 2)) (1, 2(n − 1)) (0, 2n)
At this point we can no longer cast s1, since it requires a non-zero number of coins
of type t1. So we end up with 2n coins at the end.
(b) We use (i, j) s
−→ (i′, j′) to denote that applying spell s in configuration (i, j) results
in configuration (i′, j′). Observe that we can go from (i, j) to (i, j + 4) as follows:
(i, j) s1
−→ (i − 1, j + 2) s2
−→ (i, j + 1) s1
−→ (i − 1, j + 3) s2
−→ (i, j + 2) s1
−→ (i − 1, j + 4)
Starting from (n, 0) and repeating the above sequence n times, we reach (0, 4n).
We can extend this sequence to produce more coins. For example, we can cast s2
repeatedly to reach (n, 3n) and repeat the above sequence n times to reach (0, 7n),
and so on. In fact, we can go on forever if allowed to use both rules.
(c) The new spell s3 is (−1 t2, +2 t3). If we start with configuration (i, j, k) and cast
s1 followed by s3, we arrive at (i − 1, j, k + 2). Starting from (n, 0, 0) and repeating
this n times, we get (0, 0, 4n). If we start from (i, 0, k) and apply a sequence of
spells using only s1 and s3, the number of times s3 is cast is at most the number of
times s1 is cast. (Since s3 consumes one coin of type t2 and s1 produces one coin
of type t2.) Also the number of times s1 is cast is at most i, since s1 consumes
one coin of type t1 and s3 does not add any coin of type t1. Thus, starting from
(n, 0, 0), a longest sequence consisting of s1 and s3 will have n applications of s1
and n applications of s3. We cannot end with more than 4n coins this way.