CMI 2021 B2

Question

2. Imagine you are playing a computer game that consists of different types of coins.
You have the power to cast two magic spells s1 and s2. Each spell consumes some
number of coins of each type and produces some number of coins of each type. Spell
s1 consumes one coin of type t1 and produces two coins of type t2, written in short as
(−1 t1, +2 t2). Spell s2 is (−1 t2, +1 t1). You are allowed to cast the two spells any
number of times, but a spell cannot be cast if there aren’t enough coins present for
consumption. For example, s2 cannot be cast if there are 0 coins of type t2.
(a) Suppose you start with n coins of type t1 and 0 coins of type t2. If you repeatedly
cast spell s1 till it can no longer be cast, what is the total number of coins (of
both types) at the end?
(b) Suppose you start with n coins of type t1 and 0 coins of type t2. You are allowed
to cast both the spells s1 and s2. Give a sequence of spells that will lead you to
4n total coins. Can you extend the sequence to produce more than 4n coins?
(c) Suppose we provide you with a third type of coin t3, and you start with n coins
of type t1 and 0 coins of types t2 and t3. Come up with a new spell s3 satisfying
the following three properties:
• Spell s3 can add or remove atmost two coins of any type.
• Using spells s1 and s3 repeatedly in some order, you can reach 4n total coins.
• There is no sequence of spells using only s1 and s3 that can produce more
than 4n total coins.


## Could someone please explain part C ? I am not being abe to come up with a proper way and by the official method, I was not ale to come to proper answer…

 

I have also provide the official solution below.

Answer 1

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.