PUMaC 2015 · 组合（B 组） · 第 2 题

PUMaC 2015 — Combinatorics (Division B) — Problem 2

[ 3 ] Jonathan has a magical coin machine which takes coins in amounts of 7, 8, and 9. If he puts in 7 coins, he gets 3 coins back; if he puts in 8, he gets 11 back; and if he puts in 9, he gets 4 back. The coin machine does not allow two entries of the same amount to happen consecutively. Starting with 15 coins, what is the minimum number of entries he can make to end up with 4 coins?

解析

[ 3 ] Jonathan has a magical coin machine which takes coins in amounts of 7, 8, and 9. If he puts in 7 coins, he gets 3 coins back; if he puts in 8, he gets 11 back; and if he puts in 9, he gets 4 back. The coin machine does not allow two entries of the same amount to happen consecutively. Starting with 15 coins, what is the minimum number of entries he can make to end up with 4 coins? Solution: Jonathan can put in coins in the sequence 8, 9, 7, and 9. The number of coins he will have after each step is, respectively, 18, 13, 9, and 4. To arrive at this answer, work backwards from 4, listing the possible number of coins that would allow him to arrive at 4, and work up from there. Then, the minimum possible number of entries is 4 . Author: Jonathan Lu