Home › Counting and number theory

How many ways can you make 200,000 with 1, 2 and 5 coins?

Fix one coin count, then count the rest

For each fixed number $z$ of 5-unit coins, choose any integer $y$ from $0$ through $⌊(200000 - 5 z) /2 ⌋$ . The number of 1-unit coins is then determined. Each pair $(y, z)$ gives one distinct combination, so the counts can be added.

Problem

How many different combinations of 1-, 2- and 5-ruble coins make exactly 200,000 rubles? Any denomination may be used zero times, and the order of coins does not matter.

Answer

2, 000, 080, 001

combinations.

Checked by summing the even and odd values of the 5-ruble coin count separately.

Step-by-step solution

1. Write an equation

Let $x, y, z$ count 1-, 2- and 5-ruble coins. Then $x + 2 y + 5 z = 200000$ , with all three counts nonnegative integers. For a fixed $z$ , there are $⌊(200000 - 5 z) /2 ⌋ + 1$ choices for $y$ ; $x$ is then fixed. Also $0 \leq z \leq 40000$ .

2. Separate even and odd values of $z$

For $z = 2 k$ , with $0 \leq k \leq 20000$ , the number of choices is $100001 - 5 k$ . This arithmetic progression sums to

20001 \cdot 50001 = 1, 000, 070, 001.

For $z = 2 k + 1$ , with $0 \leq k \leq 19999$ , it is $99998 - 5 k$ . The first and last terms are $99998$ and $3$ , so the sum is

20000 \cdot \frac{99998 + 3}{2} = 1, 000, 010, 000.

3. Add the two cases

1, 000, 070, 001 + 1, 000, 010, 000 = 2, 000, 080, 001.

The coin order was never counted, so this is the number of combinations rather than permutations.

Add to Chrome - solve your own

Screenshot any problem on your screen and get the steps. Chrome on a computer; free.