Maths Olympiad Prep

Library / /13 of 16

Combinatorics Difficulty 6.2 National Olympiad Prove it Philippines

Problem:

A musical performer has three different outfits. In how many ways can she dress up for seven different performances such that each outfit is worn at least once? (Assume that outfits can be washed and dried between performances.)

Solution

Solution:

Let the three outfits be AA, BB, and CC. For each performance, the performer can choose any of the three outfits, so there are 373^7 total ways to assign outfits to the seven performances.

However, we require that each outfit is worn at least once. We use the principle of Inclusion-Exclusion.

Let SS be the set of all assignments. For each outfit XX (AA, BB, or CC), let SXS_X be the set of assignments where outfit XX is not worn at all.

The number of assignments where at least one outfit is not worn is:

SA+SB+SCSASBSASCSBSC+SASBSC|S_A| + |S_B| + |S_C| - |S_A \cap S_B| - |S_A \cap S_C| - |S_B \cap S_C| + |S_A \cap S_B \cap S_C|

Now,
- SX|S_X|: If outfit XX is not worn, only two outfits are available for all performances, so 272^7 ways.
- SXSY|S_X \cap S_Y|: If two outfits are not worn, only one outfit is available, so 17=11^7 = 1 way.
- SASBSC|S_A \cap S_B \cap S_C|: No outfit is worn, which is impossible, so 00 ways.

There are 3 choices for XX and 3 choices for pairs X,YX, Y.

So, by Inclusion-Exclusion:

Number of ways =373×27+3×1= 3^7 - 3 \times 2^7 + 3 \times 1

Calculate:
- 37=21873^7 = 2187
- 27=1282^7 = 128
- 3×128=3843 \times 128 = 384
- 3×1=33 \times 1 = 3

So,

Number of ways =2187384+3=1806= 2187 - 384 + 3 = 1806

Final Answer: 18061806

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.