## Sunday, August 16, 2009

### KBB2 Problem 2

The country of Sikinia uses gold, silver, and bronze coins as its currency. One gold coin is worth 334 silver coins, and one silver coin is worth 208 bronze coins. One day, Ali went to the store and bought an item priced at 3 gold coins. How many ways can Ali pay the item in, assuming that he has unlimited supply of gold, silver, and bronze coins?

#### Solution

We shall generalize this problem. Let one gold coin worth $A$ silver, and one silver coin worth $B$ bronze coins. The price of the item is thus $3AB$ bronze coins. We will next consider the number of gold coins used to pay.

If Ali uses 3 gold coins, there is only one way to pay, that is, using 3 gold coins.

If Ali uses 2 gold coins, then he must use a combination of silver and bronze to pay for the remaining price that's equivalent to $AB$ bronze coins. He could use $0,1,cdots, A$ silver coins to pay for this. Once he decides the number of silver coins used, the remaining price must be paid all by bronze coins. So there are $(A+1)$ ways to pay with exacty 2 gold coins.

Similarly, there are $(2A+1)$ ways to pay with exactly 1 gold coin, and $(3A+1)$ ways to pay without any gold coins.

In total, there are $1 + (A+1) + (2A+1) + (3A+1) = 6A+1 = 2008$ ways to pay.