Question 15801 – Problem-Solving

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.

Correct Answer: A