MHB Combinatorial Analysis (Investments)

  • Thread starter Thread starter WMDhamnekar
  • Start date Start date
  • Tags Tags
    Analysis
AI Thread Summary
The discussion focuses on solving a combinatorial investment problem using the "stars and bars" method. After correcting initial mistakes, the correct approach involves allocating a total of $20,000 across four accounts with minimum deposits, leaving $9,000 to distribute. The solution outlines two methods to calculate the distribution, both yielding 220 ways to invest while meeting the required conditions. Additionally, part (b) explores the number of ways to invest in at least three of the four accounts, leading to a total of 572 investment strategies. The discussion emphasizes the flexibility of the stars and bars technique in combinatorial analysis.
WMDhamnekar
MHB
Messages
376
Reaction score
28
1646294122287.png


I found my mistakes in the above computation of answers. Consequently, author's answers are correct.
 
Last edited:
Physics news on Phys.org
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.$
 
Last edited:
I was reading documentation about the soundness and completeness of logic formal systems. Consider the following $$\vdash_S \phi$$ where ##S## is the proof-system making part the formal system and ##\phi## is a wff (well formed formula) of the formal language. Note the blank on left of the turnstile symbol ##\vdash_S##, as far as I can tell it actually represents the empty set. So what does it mean ? I guess it actually means ##\phi## is a theorem of the formal system, i.e. there is a...

Similar threads

Replies
20
Views
4K
Replies
3
Views
2K
Replies
1
Views
1K
Replies
2
Views
2K
Replies
2
Views
2K
Replies
12
Views
6K
Replies
1
Views
2K
Back
Top