1

Find the count of possible bank-note splits for 4 people, when you want to split \$150 for each person with bank-notes of values \$10, \$20 and \$50.

  1. What is the count of splits when each person will the amount split differently?
  2. What is the count of splits when there are no limitations?

Could someone please explain me how to solve this? I think it should be done with using basic combinatorics rules and Diophantine equation which I am a little familiar with.

Example: One of many solutions for (1) (each person has the amount in different bank-note spitls)

  • Person A - $3\cdot\$50 + 0\cdot\$20 + 0\cdot\$10$
  • Person B - $2\cdot\$50 + 2\cdot\$20 + 1\cdot\$10$
  • Person C - $2\cdot\$50 + 1\cdot\$20 + 3\cdot\$10$
  • Person D - $2\cdot\$50 + 0\cdot\$20 + 5\cdot\$10$

Example: One of many solutions for (2) (the splits can be the same for earch person)

  • Person A - $3\cdot\$50 + 0\cdot\$20 + 0\cdot\$10$
  • Person B - $3\cdot\$50 + 0\cdot\$20 + 0\cdot\$10$
  • Person C - $3\cdot\$50 + 0\cdot\$20 + 0\cdot\$10$
  • Person D - $3\cdot\$50 + 0\cdot\$20 + 0\cdot\$10$

Disclaimer: this is not a homework

rtybase
  • 16,907
zdarsky.peter
  • 325
  • 1
    It's a little bit confusing, because "you want to split $150 ... each person has $150". Could you work on an example? – rtybase Jan 13 '18 at 23:23
  • That is probably because I am not native speaker. Basically you are trying to find the count of ways how can each person have the same amount split in different ways.

    Example

    • A - 3050, 020, 0*10
    • B - 250, 220, 1*10
    • C - 250, 120, 3*20
    • D - 250, 020, 5*10

    Is one of the possible solutions

     – zdarsky.peter Jan 14 '18 at 08:01

1 Answers1

1

Using generating functions we will look at the number of ways to split \$150 for one person. Since we are allowed to use only the following denominations \$10, \$20 and \$50, the generating function for the problem (read the link I posted, it's important to understand how this technique works) becomes: $$\frac{1}{(1-x^{10})(1-x^{20})(1-x^{50})}$$ The coefficient of $x^{150}$ is the answer. I am going to cheat, the answer is $18$.

There are 4 persons involved, the answer is $18^4$.

rtybase
  • 16,907