Try it on paper first. A hint, the key idea and the worked solution are here when you need them.
A shop accepts payment in coins of two kinds only, worth and rupees. A coin of each kind may be used any number of times, but change is never given. An amount is payable when it equals for some whole numbers .
Have you tried it?
Work it out on paper first. It is fine to get stuck or make a mistake: that is how we learn. When you are ready, go through the solution one step at a time, and check each step against your own.
Plan. Use the rule for two coprime coin values, and for the other parts solve directly.
(a) For coprime the greatest amount not payable is .
(b) Exactly half of the integers are payable, which gives amounts that are not payable.
(c) Two ways and for one amount need , so divides and divides . The smallest change is up by and down by , which needs at least rupees. The amount itself is paid as coins of or as coins of . So the least is .
(d) Use as many rupee coins as possible. Since must be a multiple of , take : then , a total of coins. Using fewer rupee coins needs more coins, because a rupee coin does more work than a rupee coin.
(e) From and , we get . The values of are up to at most . The last one is , so there are ways.
Check. Trying every number of rupee coins confirms the amounts in (a) to (c) up to , and the minimum and the number of ways for and .
Log in to join the discussion.
Loading…