1
$\begingroup$

We have four coins

  • Coin 1: $0.10

  • Coin 2: $1.00

  • Coin 3: $1.00

  • Coin 4: $1.00

How many ways can we get $20.00 from these coins?

My attempt:

I started by counting the total number of ways for each coin to reach $20.00

  • 200 ways for coin 1

  • 20 ways for coins 2, 3, and 4.

I now have an equation, a + b + c + d + e = 200

We want to get the total number of solutions without any constraints

$\dbinom{200+5-1}{5-1} = \dbinom{204}{4}$

Then I found the number of solutions with the constraint that the coin must be $\leq$ 20. The total number of solutions with coin > 20 can be determined by purchasing 21 coins and leaving 181 at most to buy.

$\dbinom{181+5-1}{5-1} = \dbinom{185}{4}$

The final solution is:

$$\dbinom{204}{4} - 3 \times \dbinom{185}{4} $$

$\endgroup$
4
  • $\begingroup$ If only four coins, why five vars a,b,c,d,e? $\endgroup$
    – coffeemath
    Dec 6 '18 at 18:20
  • $\begingroup$ 'e' represents the difference between 200 and the number of coins purchased. $\endgroup$ Dec 6 '18 at 18:21
  • $\begingroup$ I don't understand what you mean by $200$ ways for coin 1. If the twenty dollars consists solely of coins of type 1, there will be $200$ of them, but that's only one way, isn't it? In fact the number of coins of type 1 bust be a multiply of $10$, so there are only $21$ choices for the number of coins of type 1. $\endgroup$
    – saulspatz
    Dec 6 '18 at 18:29
  • $\begingroup$ @saulspatz I thought I could solve the problem using constraints. I wanted to take the total number of options, then remove the smaller constraints from that total. $\endgroup$ Dec 6 '18 at 18:37
4
$\begingroup$

There should be a multiple of 10 number of coins of type $1$. Hence, in effect we have four types of coin of \$ $1$ and desire non-negative solutions to the equation $x_1+x_2+x_3+x_4=20$, which by the stars and bars problem is $\binom{23}{3}$.

$\endgroup$
2
  • $\begingroup$ Very neat. I went through adding up the the stars and bars answer if there are $10k$ coins of type $1$, for $k=0,1,\dots,20$ and eventually ended up with ${23\choose3},$ but it never clicked that I could shortcut all that. $\endgroup$
    – saulspatz
    Dec 6 '18 at 19:15
  • $\begingroup$ Thanks, @saulspatz. $\endgroup$
    – Anubhab
    Dec 6 '18 at 19:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.