Try it on paper first. A hint, the key idea and the worked solution are here when you need them.
A vending machine takes tokens worth units and units and gives no change. Ayaan wants to pay exactly units, using any number of each kind of token, zero included. Find how many different ways he can pay. Then find the smallest number of tokens he can use, and say why the number of -unit tokens must be a multiple of .
has integer solutions exactly when . From one solution , all are
For coprime the largest that is not with is .
Check an answer or open a hint to unlock the worked solution.
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.
Given. with .
Step 1. A condition on . and are multiples of , so is too. Since , .
Step 2. List. give . The next value, , gives .
Step 3. Count. There are ways.
Step 4. Fewest tokens. The totals are . Each step down the list swaps small tokens for large ones. The fewest is .
Check. .
Answer: ways, and the fewest tokens is .
Log in to join the discussion.
Loading…