1
$\begingroup$

I've been trying to solve a problem, but the solution I got looks extrmely unlikely to be right. Perhaps some can point where I'm wrong. The problem is the following.

We have $14$ different books. We want to distribute them to person $A$ and $B$ in a way that none of them are left with less than $3$ books. I've tried the following.

Let $L=\{1, 2, 3, ..., 14\}$ be the set of books in my possesion.

$A$ and $B$ must receive at least $3$, and the $3$ books that I'll give to any of them will be a subset of $L$. There are $\binom{14}{3}$ subsets of $3$ elements of $L$, so when I give the first $3$ books to the first person (whether its $A$ or $B$) I have $\binom{14}{3}$ different ways to do it. By the time I'll give the second person other $3$ books I will have only $11$ books remaining, cause I gave $3$ to the first person. The $3$ books I'll give to the second person will be subsets of $L'$, the set of the $11$ books remaining, so I'll have $\binom{11}{3}$ different ways of giving the second person its three books.

We have to cases:

$a)$ First person is $A$, in which case I have $\binom{14}{3}\binom{11}{3}$ possibilities, the first three books for $A$ and three books of the remaining ones for $B$.

$b)$ First person is $B$, in which case I have $\binom{14}{3}\binom{11}{3}$ possibilities, the first three books for $B$ and three more books for $A$.

Together, this adds up to $\binom{14}{3}\binom{11}{3} + \binom{14}{3}\binom{11}{3}$ possibilities.

But now that I made sure that each person gets at least $3$ books, I have $8$ remaining books, that I can give to anyone I want however I want. So my first decisition is give $1$ of $8$ books to $A$ or $B$; second is to give $1$ of $7$ books to $A$ or $B$, and so on. So I have $8!+8!$ possibilities here. At last, I have

$[\binom{14}{3}\binom{11}{3} + \binom{14}{3}\binom{11}{3}]*(8!+8!) = 2[\binom{14}{3}\binom{11}{3}]*2(8!)=9686476800$.

I'm no genius but I don't think that giant number could be the right answer.

$\endgroup$
  • 6
    $\begingroup$ Are all the books to be distributed? If so, then the collection of books that goes to $A$ determines those that go to $B$. Thus the answer is just $\sum_{i=3}^{11}\binom {14}i=16172$ $\endgroup$ – lulu Apr 15 at 17:09
  • $\begingroup$ That number is indeed too big. You should get something less than $2^{14} = 16384$. You have counted many cases multiple times $\endgroup$ – Henry Apr 15 at 17:09
  • 3
    $\begingroup$ The reason this overcounts is that the same distribution can be reached by multiple different decision paths in the above scheme. Suppose we ultimately give (a specific set of) 8 books to $A$, and the other books to $B$. Any three of those 8 are equally eligible to be called “the first three books for $A$”, so we count this one case at least $C(8.3) = 56$ times. In fact any three of $B$’s books is also eligible to be “the first three”, so we’ve counted this case at least $56*20 = 1120$ times! $\endgroup$ – Erick Wong Apr 15 at 17:24
  • $\begingroup$ @lulu Yes, all books are to be distributed. $\endgroup$ – Lafinur Apr 15 at 17:52
  • $\begingroup$ @ErickWong, you do make a point. I'll keep trying to work this out. $\endgroup$ – Lafinur Apr 15 at 17:53
1
$\begingroup$

Let A and B be the people among whom the 14 books (all different) will be distributed, with the condition that each of these people must receive at least 3 books.

Obviously, the order in which the books are distributed between A and B is indifferent.

A very easy way to visualize the process of distribution of these 14 books is to imagine that each book is affixed with a label with the letter A or B. Each book will be assigned to the person whose name matches the one of the labels and the number of different ways of performing this labeling is

$${{n}_{1}}\equiv {{2}^{14}}=16384$$

To fulfill the condition that A and B receive at least 3 books each, we must eliminate those labeled with less than 3 "A" or less than 3 "B". The number of labeled with 0, 1 or 2 "A" is the same as the number of labeled with 0, 1 or 2 "B".

  • Number of labels A in a labeled = 0, (14 B) $\Rightarrow $ Number of labeled:

$${{n}_{2}}\equiv 1.$$

  • Number of labels A in a labeled = 1, (13 B) $\Rightarrow $ Number of labeled:

$${{n}_{3}}\equiv 14.$$

  • Number of labels A in a labeled = 2, (12 B) $\Rightarrow $ Number of labeled:

$${{n}_{4}}\equiv \left( \begin{matrix} 14 \\ 2 \\ \end{matrix} \right)=91.$$

Therefore, the number of ways to make the proposed distribution is,

$$n={{n}_{1}}-2\left( {{n}_{2}}+{{n}_{3}}+{{n}_{4}} \right)=16384-2\left( 1+14+91 \right)$$

that is,

$$n=16172.$$

$\endgroup$
1
$\begingroup$

There are $2^{14} = 16\,384$ ways to distribute $14$ distinct books to $2$ distinct people, disregarding the minimal count requirement.

Of these, there are

  • $\binom{14}{0} = 1$ ways to give A no books,
  • $\binom{14}{1} = 14$ ways to give A exactly one book, and
  • $\binom{14}{2} = 91$ ways to give A exactly two books,

and identical ways to give B exactly $0$, $1$, or $2$ books, for a final count of $(1+14+91)\times2 = 212$ ways for books to be distributed in rule-breaking ways. This leaves $16\,384-212 = 16\,172$ ways to distribute the books.

$\endgroup$
0
$\begingroup$

Here the question is ambigious Are all the books identical or distinct? I assumed them to be identical Give 3 books to each A andB Now we are left with 8books to distribute let a books be given to A and b books be given to B Therefore; a+b=8
The no. Of non-negative integral solutins to above equation will be the required no. Of ways So; it is 9

$\endgroup$
  • $\begingroup$ You are right, it was ambigious. I edited it. Unfortunately, the case was $14$ different books, so this is not the solution. I apologize and thank you for your effort anyway. $\endgroup$ – Lafinur Apr 17 at 16:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.