New Year's Countdown Day 21: Present Time!

Santa has to deliver 21 presents to 7 distinguishable children. Among the 21 presents are 7 indistinguishable action figures, 7 indistinguishable basketballs, and 7 indistinguishable construction toys. Santa must distribute these presents in such a way that all the presents are distributed and no child gets more than two of the same type of present. However, he is allowed to give no presents to a child if he so wishes.

If the number of ways that Santa can distribute the presents is equal to a 3 , a^3, where a a is a positive integer, find a . a.


This problem is part of the set New Year's Countdown 2017 .


The answer is 393.

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

1 solution

Arjen Vreugdenhil
Dec 21, 2017

Santa can distribute the three kinds of toys independently. The number of ways is therefore a 3 a^3 , where a a is the number of ways one type of toy can be distributed.

In principle, seven indistinguishable toys may be divided among seven distinguishable children in ( 7 + 6 6 ) = 1716 \binom{7+6}6 = 1716 ways. (A simple star-and-bar argument.)

However, we now have counted several ways in which three or more of the toys go to one child. Consider therefore the situations in which three of the toys are given to one particular child (7 choices here). The remaining 4 toys can be divided in ( 4 + 6 4 ) = 210 \binom{4+6}4 = 210 ways. Thus we subtract 7 × 210 = 1470 7 \times 210 = 1470 situations where one child gets too many toys.

But note that we have subtracted too much now; if two children received three or more toys, that situation has been subtracted twice. We make up for this by adding back in the situations where two children ( ( 7 2 ) = 21 \binom 7 2 = 21 choices) get three of the gift each; the remaining 1 toy can be assigned to 7 children. Thus we add back in 7 × 21 = 147 7 \times 21 = 147 ways.

The solution, then, is a = 1716 1470 + 147 = 393 . a = 1716 - 1470 + 147 = \boxed{393}.

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...