Combinatorial Analysis (Investments)

[WMDhamnekar]

I found my mistakes in the above computation of answers. Consequently, author's answers are correct.

 

[GJA]

Hi Dhamnekar Winod,

Thanks for posting this question; glad to hear you were able to sort it out. I'm adding a solution outline below in case there are MHB community members who are interested in learning about the "stars and bars" combinatorial principle that you've correctly applied (after correcting $r-1$) above.

Part (a) - Solution 1

Since we must invest in each of the 4 accounts, we know the minimum amounts of \$2000, \$2000, \$3000, and \$4000 must be deposited into accounts 1, 2, 3, and 4, respectively. Thus, \$11,000 of our \$20,000 is spent on minimum investments, leaving us with a remaining \$9000 to distribute among the 4 accounts. Letting $x_{1}$, $x_{2}$, $x_{3}$, and $x_{4}$ represent the additional amounts deposited into accounts 1, 2, 3, and 4, respectively, we have $$x_{1} + x_{2} + x_{3} + x_{4} = \$9000\text{,}\qquad\text{where}\,\, x_{1}, x_{2}, x_{3}, x_{4}\geq 0. \qquad (*)$$ Note: In this case we're using greater than or equal to because the minimum amounts on their own guarantee we're invested in each of the four accounts and there is no requirement on how the additional money -- which is what $x_{1},$ $x_{2}$, $x_{3}$, and $x_{4}$ represent -- must be placed in each of the four accounts.

The final given piece of information we must incorporate is that the investments must be made as integer multiples of \$1000. So, for example, placing an additional \$2000 into account 1 (i.e., $x_{1}$ = \$2000) would be allowed, but placing an additional \$1500 in account 1 (i.e., $x_{1}$ = \$1500) would not be.

A common approach to solving problems of the kind described above is known as the "stars and bars" method. See Wikipedia - Stars and Bars (Combinatorics). Here we are letting a star "$\star$" represent \$1000 and letting a bar "$\vert$" be the symbol we use to delineate the different accounts (Note: A bar "$\vert$" in the stars and bars method and the plus symbol $+$ in the equation $(*)$ above effectively serve the same purpose).

For example, the arrangement $$\star\star\star\,\vert\star\star\,\vert\star\vert\star\star\star$$ means we've made the additional investments $x_{1} = \$3000$, $x_{2} = \$2000$, $x_{3} = \$1000$, and $x_{4} = \$3000$.

As a second example, $$\vert\vert\star\star\star\star\star\star\star\vert\star\star$$ means we've made the additional investments $x_{1} = \$0$, $x_{2} = \$0$, $x_{3} = \$7000$, and $x_{4} = \$2000$.

A key realization to make is that delineating 4 accounts requires only 3 bars. This can also be seen in equation $(*)$ as only 3 plus symbols $+$ are needed to delineate the 4 different additional investment amounts. This is true in general as well. If there are $k$ distinct bins/containers in which to place objects, then $k-1$ bars are needed to delineate these bins/containers.

Putting this all together we have a total of 12 "slots" to which we must assign a star "$\star$" or a bar "$\vert$", 9 slots being used for stars and 3 slots being used for bars. $$\_\, \_ \, \_\, \_ \, \_\, \_ \, \_\, \_ \, \_\, \_ \, \_\, \_$$ By selecting the 3 slots for the bars, we know all 9 remaining slots will be filled with bars. Since the order we select the slots into be filled with bars is irrelevant, we use the combination/binomial coefficient to calculate this value to get $$\binom{12}{3} = \dfrac{12!}{9!3!} = 220.$$ Now, observe that there is nothing special about selecting the position of the bars. One could equivalently solve this problem by selecting the locations of the 9 stars and get the same answer. That is, we get the same answer using $$\binom{12}{9} = \dfrac{12!}{3!9!} = 220.$$

Part (a) - Solution 2

We can equivalently solve part (a) by reframing the problem slightly. In this version we subtract \$1000 from each of the minimum required investment amounts but impose a strict inequality on $x_{1}$, $x_{2}$, $x_{3}$, and $x_{4}$ in equation $(*)$ above. By imposing a strict inequality, we force at least \$1000 into each of the 4 accounts, which allows us to still meet the minimum investment requirement. In this version of the problem's solution $(*)$ becomes $$x_{1} + x_{2} + x_{3} + x_{4} = $13,000\qquad x_{1}, x_{2}, x_{3}, x_{4} >0.$$ The strict inequality forces each investment to have at least one "star" in it. For example $$\star\star\star\star\,\vert\star\star\star\star\star\,\vert\star\star\star\,\vert\,\star$$ means we've made the additional investments $x_{1} = \$4000$, $x_{2} = \$5000$, $x_{3} = \$3000$, and $x_{4} = \$1000$.

The key takeaway in the strict inequality case is that a particular investment strategy is completely determined by the location of the 3 bars between the 13 stars: $$\star\star\star\star\star\star\star\star\star\star\star\star\star$$ Notice that between 13 stars there are 12 slots in which a bar could be placed. Hence, there are $$\binom{12}{3}=\dfrac{12!}{9!3!} = 220$$ ways to invest according to the stated requirements, just as was the case above.Part (b)

One way to solve part (b) is to look at each of the 5 possible ways to invest in at least 3 of the 4 accounts. We know from part (a) that there are 220 ways to invest in all 4 accounts. The four remaining cases are: omitting account 1, omitting account 2, omitting account 3, and omitting account 4.

Omitting Account 1

We can solve this using part (a) solution method 1 as $$x_{2} + x_{3} + x_{4} = \$11,000\qquad\text{where}\,\, x_{2}, x_{3}, x_{4}\geq 0$$ or using part (a) solution method 2 as $$x_{2} + x_{3} + x_{4} = \$14,000\qquad\text{where}\,\, x_{2}, x_{3}, x_{4} > 0.$$ In either case we get $$\binom{13}{2} = \dfrac{13!}{11!2!} = 78.$$ Applying the same ideas to the remaining 3 cases will solve the problem and gives $220 + 78 + 78 + 91 + 105 = 572.$