0
$\begingroup$

A certain father died and left as an inheritance to his three sons $30$ glass flasks, of which $10$ were full of oil, another $10$ were half full, while another $10$ were empty. Divide the oil and flasks so that an equal share of the commodities should equally come down to the three sons, both of oil and glass

One could find the answer just by finding coefficient of $x^{10}$ in $$\frac{1}{(1-x^2)(1-x^3)(1-x^4)}.$$

So could anyone give me a reason why this generating function gives the solution to this problem.

$\endgroup$

1 Answer 1

1
$\begingroup$

EDIT: I've thought of an argument which I think conveys the idea better.

That generating function counts the partitions of $n$ into parts $2$, $3$, and $4$. I'll give a bijection between such partitions of $n$ and divisions of the inheritance. Note that among the sons, we can order them by who gets the most full flasks of oil. Call the sons $A$, $B$, and $C$ where $A$ gets the fewest half flasks and $C$ gets the most (some of them may get the same number of half flasks, but that's fine).

Say you have some way of fairly dividing the inheritance, and let $A_1, B_1$, and $C_1$ be the number of half flasks given to $A$, $B$ and $C$ respectively. Since $A$ gets the fewest half flasks, every time we give $A$ a half flask, we must give one to $B$ and $C$ as well. Thus, we can distribute some half flasks in groups of $3$, giving each son one half flask, a total of $A_1$ times. Now that we've given $A$ all of his half flasks, we turn to $B$. Observe that $A_1$, $B_1$, and $C_1$ must all have the same parity (that is, they are either all even or all odd), so $B_1-A_1$ is even. Hence, we can give $B$ the rest of his half flasks in groups of $2$, and since $C$ has at least as many half flasks as $B$, we must give $C$ the same number of half flasks. This allows us to distribute more half flasks in groups of $4$, giving $B$ and $C$ each two half flasks, a total of $(B_1-A_1)/2$ times. Finally, we give $C$ the rest of his half flasks, and since $C_1$ and $B_1$ have the same parity, we can give $C$ his in groups of $2$, a total of $(C_1-B_1)/2$ times. This is a partition of $n$ into parts $2$, $3$, and $4$.

Now we show that this correspondence is bijective by giving its inverse. Say we have a partition of $n$ into parts $2, 3,$ and $4$. Each $2$, $3$, and $4$ will tell us how to divide that many full flasks, half flasks, and empty flasks among the sons. For each $2$, give $A$ and $B$ one full flask and one empty flask each, and give $C$ two half flasks. For each $3$, give each son one full flask, one half flask, and one empty flask. For each $4$, give $A$ two full flasks and two empty flasks, and give $B$ and $C$ one full flask, two half flasks, and an empty flask. In each case, we divide the flasks and oil evenly, so this division will satisfy the desired conditions. Furthermore, this is the inverse of our original correspondence, since it distributes the half flasks using the same groups of $2$, $3$, and $4$. Hence, the number of fair divisions of $3n$ flasks is the number of partitions of $n$ into parts $2$, $3$, and $4$, so we have the desired generating function.

$\endgroup$
5
  • $\begingroup$ Could you please explain final steps . $\endgroup$ Commented Feb 10, 2021 at 17:46
  • $\begingroup$ @PiyushChoudhury What part do you not understand? $\endgroup$
    – Kevin Long
    Commented Feb 10, 2021 at 18:04
  • $\begingroup$ From corresponding partitions. In last para. $\endgroup$ Commented Feb 10, 2021 at 18:21
  • $\begingroup$ @PiyushChoudhury We want to show that given a particular division of the flasks, then the partition with $p_2, p_3, p_4$ as above will map to that division, using the map described at the beginning. Note that if know how many half flasks each son gets, then we know exactly how the flasks are distributed. If you have the partition with $p_2, p_3, p_4$, how many half flasks will $A$ get? How many will $B$ get? If you can show that $A$ will get $A_1$ half flasks and $B$ will get $B_1$ half flasks, it follows that $C$ gets $n-A_1-B_1=C_1$ half flasks, so we get the desired division of flasks. $\endgroup$
    – Kevin Long
    Commented Feb 10, 2021 at 19:02
  • $\begingroup$ I just realized that my choice of $p_2$ was missing a factor of $1/2$. I've edited my answer to make $p_2=(n-3p_3-4p_4)/2$. $\endgroup$
    – Kevin Long
    Commented Feb 11, 2021 at 20:03

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .