Problem 1.13 Easy Free 6 variations

Allocating Identical Units

A fund manager must allocate exactly $50 million among five labelled asset classes (equity options, commodity futures, fixed income, FX, and cryptocurrencies), in whole-million increments, with no restriction on how much (including zero) goes to each class. For example, one allocation (in millions) is $(25,15,5,5,0)$ . In how many ways can the $50 million be allocated?

Work it out, then compare with the answer.

SolutionShow the worked solution

Write $x_i\ge 0$ for the number of millions placed in class $i$ . An allocation is then a solution in non-negative integers of

x_1+x_2+x_3+x_4+x_5=50 .

Each solution matches exactly one row of $50$ stars and $4$ bars. The stars before the first bar count $x_1$ . The stars between the first and second bars count $x_2$ , and so on. Adjacent bars, or a bar at either end, give a zero allocation. The example $(25,15,5,5,0)$ is twenty-five stars, a bar, fifteen stars, a bar, five stars, a bar, five stars and a final bar.

Conversely, every row of $54$ symbols with exactly $4$ bars gives one allocation. So we only need to choose which $4$ of the $54$ positions hold bars:

\binom{54}{4}=\frac{54\cdot 53\cdot 52\cdot 51}{24}=316\,251 .

\boxed{\binom{54}{4}=316\,251}

Generalisation. $n$ identical units can be placed in $k$ labelled boxes in $\binom{n+k-1}{k-1}$ ways.

Variations

The same idea with a twist. Each solution gives only the changed step.

Variation 1.13a

A fund manager must allocate exactly $75 million among five labelled asset classes (equity options, commodity futures, fixed income, event contracts, and cryptocurrencies), in whole-million increments, with each class receiving at least $5 million. In how many ways can the $75 million be allocated?

Work it out, then compare with the answer.

Solution

First give each class its $5 million floor. That uses $25 million and leaves $50 million with no restriction. Write $y_i=x_i-5\ge 0$ , so that $y_1+\dots+y_5=50$ . This is exactly the main problem:

\boxed{\binom{54}{4}=316\,251}

Variation 1.13b

In how many ways can $25$ be written as an ordered sum of three positive integers?

Work it out, then compare with the answer.

Solution

Put $y_i=x_i-1\ge 0$ . Then $y_1+y_2+y_3=22$ , and stars and bars gives

\boxed{\binom{24}{2}=276}

Variation 1.13c

A babysitter has $12$ identical units of food to distribute among $10$ children, but decides to give food to only $4$ of them, leaving the other $6$ with none. In how many ways can she choose which $4$ children receive food and distribute the $12$ units among them so that each of those $4$ receives at least $1$ unit?

Work it out, then compare with the answer.

Solution

There are $\binom{10}{4}=210$ ways to choose the four children who are fed.

For those four, give each child one unit first. The remaining $8$ units are then distributed freely among $4$ children, in $\binom{11}{3}=165$ ways.

The two choices are independent, so the total is

\boxed{210\cdot 165=34\,650}

Variation 1.13d

How many solutions in odd non-negative integers (i.e. positive odd integers) are there to $x_1+x_2+x_3+x_4+x_5+x_6=96$ ? Writing the count as $\binom{n}{k}$ with $k<n/2$ , find $nk$ .

Work it out, then compare with the answer.

Solution

Write each odd variable as $x_i=2k_i+1$ with $k_i\ge 0$ . The equation becomes $2(k_1+\dots+k_6)+6=96$ , that is,

k_1+\dots+k_6=45 .

Stars and bars gives $\binom{50}{5}=2\,118\,760$ solutions. In this form $n=50$ and $k=5$ , which satisfies $k<n/2$ . Hence

\boxed{nk=250}

Variation 1.13e

A teacher buys $50$ chicken nuggets to split among four students, Alice, Bob, Carol, and Dave. Bob, Carol, and Dave each want at least $6$ nuggets, and Alice wants at least $18$ nuggets; separately, each student is “satisfied” with the split as long as they receive at least $5$ nuggets. The teacher partitions the $50$ nuggets into four (possibly empty before accounting for the $5$ -nugget floor) piles, one per student, with every valid partition equally likely. Given that every student receives at least $5$ nuggets, what is the probability that Bob, Carol, and Dave each have at least $6$ and Alice has at least $18$ ? Express the probability as $\binom{a}{b}/\binom{c}{d}$ and find the minimum possible value of $a+2b+c+2d$ .

Work it out, then compare with the answer.

Solution

Every ordered split $(x_A,x_B,x_C,x_D)$ of $50$ into non-negative parts is equally likely. The desired event (Alice $\ge 18$ , the others $\ge 6$ ) is contained in the conditioning event (everyone $\ge 5$ ). The conditional probability is therefore a ratio of two counts.

Everyone at least $5$ . Remove $4\cdot 5=20$ nuggets, leaving $30$ to share freely: $\binom{33}{3}=5456$ splits.
The desired event. Remove $18+3\cdot 6=36$ nuggets, leaving $14$ to share freely: $\binom{17}{3}=680$ splits.

\mathbb{P}=\frac{\binom{17}{3}}{\binom{33}{3}}=\frac{85}{682}\approx 0.125 .

Using the smaller lower index in each binomial gives $(a,b,c,d)=(17,3,33,3)$ . Then

\boxed{a+2b+c+2d=62}

Variation 1.13f

Fix an integer $N>0$ and let $X_1,X_2,X_3$ be independent, each uniform on $\{0,1,\dots,N\}$ . Let $p_N=\mathbb{P}[X_1+X_2+X_3=N]$ . Find $\lim_{N\to\infty} N p_N$ , or state that it does not exist.

Work it out, then compare with the answer.

Solution

Every non-negative solution of $x_1+x_2+x_3=N$ automatically has each $x_i\le N$ . So the favourable outcomes are all of these solutions, and there are $\binom{N+2}{2}$ of them. Out of $(N+1)^3$ equally likely triples,

p_N=\frac{(N+2)(N+1)}{2(N+1)^3}=\frac{N+2}{2(N+1)^2}.

Multiplying by $N$ ,

Np_N=\frac{N(N+2)}{2(N+1)^2}\to\frac12 .

So the limit exists and

\boxed{\lim_{N\to\infty}Np_N=\tfrac12}

Spotted an error? Email us