The number of ways of giving 20 distinct oranges to 3 children such that each child gets at least one orange is ___________.

Solution

Maths sir · 4 steps

Count every way first, then use inclusion-exclusion to remove the ways that leave a child empty-handed.

1. Count everything. Each of the 20 distinct oranges can go to any of the 3 children. With no restriction, that gives 3²⁰ ways.
2. Remove empty children. Choose 1 child to get nothing in C(3, 1) ways. The oranges then go to the other 2 children in 2²⁰ ways. This subtraction removes the cases where 2 children get nothing twice, so add them back once: C(3, 2) × 1²⁰ = 3.

   N = 3²⁰ - C(3, 1)2²⁰ + C(3, 2)1²⁰

3. Put in numbers. 3²⁰ = 3486784401 and 3 × 2²⁰ = 3 × 1048576 = 3145728. So N = 3486784401 - 3145728 + 3.
4. So. N = 3483638673 + 3 = 3483638676.

The common slip: 171. Treating the oranges as identical and using C(19, 2) gives 171. The oranges are distinct, so each orange is its own choice of child, which gives powers like 3²⁰.

The idea to keep. For distinct objects to r children with nobody left out, use rⁿ - C(r, 1)(r-1)ⁿ + C(r, 2)(r-2)ⁿ - …. Do not stop after the subtraction: add back the cases you removed twice.

Answer from the NTA final answer key. Solution by PrepWiser.