3

In a bag I have:

  • Five 10c coins
  • Two 25c coins

If I pick out three coins from the bag. What are all the possible amounts of money I could have.

The answer is:

  • 30c (3x10c coins),
  • 45c (1x25c coins, 2x10c coins)
  • 60c (2x25c coins, 1x10c coins)

I am looking for a formula that I can generalise to any number of coins in the bag, or coins picked out of it.

I know that I can work out combinations with $$nCr=\frac{n!}{k!(n-k)!}$$ However I am not sure how I can use this with duplicate items. (eg. more than one 10c coin)

Alec Hewitt
  • 131
  • 1
  • 1
    The number of distinct outcomes can be found using techniques like that and accounting for upper bound conditions like this with inclusion-exclusion. This won't however work out what sums are possible. For example, with enough 5c, 10c, and 25c coins, the outcomes (5,5,5,25) and (10,10,10,10) would by my proposed method count as different despite their sum being the same – JMoravitz Jun 24 '16 at 00:23
  • For a large number of coins, you can typically get any multiple of the gcd up to the amount in the bag. But there may be a few early gaps. For example, the gcd of 10,25 is 5, but however many coins you have you cannot get 5 or 15. There will be matching gaps at the top end - you will not be able to get 5 less than the total or 15 less than the total. – almagest Jun 24 '16 at 12:05

0 Answers0