MHB How can 16 shares be distributed among 4 people with specific constraints?

[Saitama]

Problem:
Eli, Joy, Paul and Sam want to form a company; the company will have 16 shares to split among the 4 people. The following constraints are imposed:

• Every person must get a positive integer number of shares, and all 16 shares must be given out.
• No one person can have more shares than the other three combined.

Assuming that the shares are indistinguishable, but people are distinguishable, in how many ways can the shares be given out?

Attempt:
Let $x_1,x_2,x_3 $ and $x_4$ represent the four persons, then

$$x_1+x_2+x_3+x_4=16$$

From the first constraint, $x_1,x_2,x_3,x_4\geq 1$. Let $x_i-1=X_i$ for $i=1,2,3,4$. Then the above equation can be written as:
$$X_1+X_2+X_3+X_4=12 \,\,\,(*)$$

From the second constraint,

$$x_1 \leq x_2+x_3+x_4 \Rightarrow X_1 \leq X_2+X_3+X_4+2$$

Similarly,

$$X_2 \leq X_1+X_3+X_4+2$$
$$X_3 \leq X_2+X_1+X_4+2$$
$$X_4 \leq X_2+X_3+X_1+2$$

But I don't see how to find the solutions to (*) with the imposed restrictions.

Any help is appreciated. Thanks!

 

[Opalg]

Problem:
Eli, Joy, Paul and Sam want to form a company; the company will have 16 shares to split among the 4 people. The following constraints are imposed:

• Every person must get a positive integer number of shares, and all 16 shares must be given out.
• No one person can have more shares than the other three combined.

Assuming that the shares are indistinguishable, but people are distinguishable, in how many ways can the shares be given out?

Attempt:
Let $x_1,x_2,x_3 $ and $x_4$ represent the four persons,

More accurately, $x_1,x_2,x_3 $ and $x_4$ represent the number of shares allocated to the four persons.

then

$$x_1+x_2+x_3+x_4=16$$

From the first constraint, $x_1,x_2,x_3,x_4\geq 1$. Let $x_i-1=X_i$ for $i=1,2,3,4$. Then the above equation can be written as:
$$X_1+X_2+X_3+X_4=12 \,\,\,(*)$$

From the second constraint,

$$x_1 \leq x_2+x_3+x_4 \Rightarrow X_1 \leq X_2+X_3+X_4+2$$

Similarly,

$$X_2 \leq X_1+X_3+X_4+2$$
$$X_3 \leq X_2+X_1+X_4+2$$
$$X_4 \leq X_2+X_3+X_1+2$$

But I don't see how to find the solutions to (*) with the imposed restrictions.

Any help is appreciated. Thanks!

The condition that no one person can have more shares than the other three combined is equivalent to the condition that no one person can have an absolute majority of the shares. Since there are 16 shares altogether, that is equivalent to the condition that no one person can have more than 8 shares. So you could simplify your conditions to $x_i \leqslant 8$, or $X_i \leqslant 7$, for $i=1,2,3,4.$

One way to approach the problem would be this. The total number of ways of allocating 12 shares among 4 persons is $15 \choose 3$. From that, you need to subtract all the disallowed allocations. For example, there are 4 ways to allocate all 12 shares to one person. Then you can find the number of ways to allocate 11 shares to one person and the remaining 1 share to someone else. Then do the same for one person getting 10, 9 or 8 shares. Subtract all those from $15 \choose 3$ and you have the answer.

 

[Saitama]

More accurately, $x_1,x_2,x_3 $ and $x_4$ represent the number of shares allocated to the four persons.

Oh yes. :p

The condition that no one person can have more shares than the other three combined is equivalent to the condition that no one person can have an absolute majority of the shares. Since there are 16 shares altogether, that is equivalent to the condition that no one person can have more than 8 shares. So you could simplify your conditions to $x_i \leqslant 8$, or $X_i \leqslant 7$, for $i=1,2,3,4.$

Yes, agreed. I was finding it difficult to determine the upper bound for $x_i$ or $X_i$. Thanks Opalg! :)

One way to approach the problem would be this. The total number of ways of allocating 12 shares among 4 persons is $15 \choose 3$. From that, you need to subtract all the disallowed allocations. For example, there are 4 ways to allocate all 12 shares to one person. Then you can find the number of ways to allocate 11 shares to one person and the remaining 1 share to someone else. Then do the same for one person getting 10, 9 or 8 shares. Subtract all those from $15 \choose 3$ and you have the answer.

Or use a generating function.