2. The official currency for the small island nation of Fabricatia is the yuat.

Question

2. The official currency for the small island nation of Fabricatia is the yuat. Fabricatia is a somewhat isolated nation - perhaps you've never even heard of it! - and hence has a rather underdeveloped economic system. Fabricatia's money comes in only three denominations: a 6-yuat coin, a 9-yuat coin, and a 28-yuat bill You decide to visit Fabricatia over the winter break. On your last night there, you dine out at the ritziest restaurant on the island, and order the finest dishes on the menu. Your bill comes to a total of 59 yuats (which translates into approximately 80.27 US) (a) Prove that it's impossible to pay exactly 59 yuats. (Since the Fabricatians consider it rude to ask for change, this means you'll have to leave a tip.) (Hint # 1: consider several cases, based on how many of the 28-yuat bills ou could use. Hint #2: As a warm-up, it might help to try proving that it's impossible to pay exactly 26 yuats. There is a very, very short proof. Write down all the amounts you can pay using just the coins; can you see a pattern?) (b) Prove that it is possible to pay exactly n yuats whenever n 2 60. (Hence, you can leave as small or as large a tip as you wish.) (c) Fabricatia's government decides to start minting 5-yuat coins. Now what's the largest amount for which it's impossible to make exact change? (You don't need to formally prove your answer.)

Explanation / Answer

a)

Lets say for 59 yuats consider the case when

1. Two 28-yuat bill are used. In this case it is easy to see that it is impossible to pay remaining 3 yuats using 6 and 9 yuat denominations.

2. One 28-yuat bill is used. The remaining amount to pay is 31 yuat. Now since 6 and 9 are both multiple of 3 the amount that can be paid using 6 and 9 yuat must also be a multiple of 3. Since 31 is not multiple of 3, hence 31 yuats can't be paid using 6 and 9 yuats.

3. Zero 28- yuat bill is used. Using the same argument as above 59 is not a multiple of 3, hence 59 yuat can not be paid using 6 and 9 yuat bill.

b) To prove that n yuats for n >= 60 can be paid exactly we will prove that 60, 61, 62, 63, 64, 65 yuats can be paid exactly. For any n >= 65 yuats, we can write it as n = a + 6*m. where a = 60 or 61 or 62 or 63 or 64 or 65. and m is positive integer.

1. For n = 60 yuats, one solution is paying 10 bills of 6 yuats.

2. For n = 61 yuats, one solution is paying 1 bill of 28 yauts, 1 bill of 9 yuats and 4 bills of 6 yauts.

3. For n = 62 yuats, one solution is paying 2 bills of 28 yuats and 1 bill of 6 yuats.

4. For n = 63 yuats, one solution is paying 1 bill of 9 yuats and 9 bills of 6 yuats.

5. For n = 64 yuats, one solution is paying 1 bill of 28 yuats and 6 bills of 6 yuats.

6. For n = 65 yuats, one solution is paying 2 bills of 28 yauts and 1 bill of 9 yuats.

c) The largest amount for which it is impossible to make exact changes would be 17.

Related Questions

Navigate

• Browse (All)
• Browse 2
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.