Competition problem — Combinatorics

Library / /463 of 520

Combinatorics Difficulty 4.1 AIME Find the answer

A mathematical organization is producing a set of commemorative license plates. Each plate contains a sequence of five characters chosen from the four letters in AIME and the four digits in 2007. No character may appear in a sequence more times than it appears among the four letters in AIME or the four digits in 2007. A set of plates in which each possible sequence appears exactly once contains N license plates. Find $\frac{N}{10}$ .

Your answer

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solutions — 2

Solution 1

There are 7 different characters that can be picked, with 0 being the only number that can be repeated twice.

If $0$ appears 0 or 1 times amongst the sequence, there are $\frac{7!}{(7-5)!} = 2520$ sequences possible.
If $0$ appears twice in the sequence, there are ${5\choose2} = 10$ places to place the $0$ s. There are $\frac{6!}{(6-3)!} = 120$ ways to place the remaining three characters. In total, that gives us $10 \cdot 120 = 1200$ .
Thus, $N = 2520 + 1200 = 3720$ , and $\frac{N}{10} = \boxed{372}$ .

Solution 2

To solve this problem, we need to count the number of valid license plates that can be formed under the given constraints and then find $\frac{N}{10}$ .

1. Identify the characters available:
- Letters: A, I, M, E
- Digits: 2, 0, 0, 7

2. Determine the constraints:
- Each character can appear no more times than it appears in the set of available characters.
- We need to form sequences of 5 characters.

3. Case Analysis:
- We will consider different cases based on the number of zeros in the sequence.

### Case 1: 0 or 1 zero
- If there are 0 or 1 zeros, we need to choose 5 characters from the set {A, I, M, E, 2, 0, 7} without exceeding the available counts.

#### Subcase 1.1: 0 zeros
- We choose 5 characters from {A, I, M, E, 2, 7}.
- Number of ways to choose 5 characters from 6: $\binom{6}{5} = 6$
- Number of permutations of 5 characters: $5!$
- Total for this subcase: $6 \times 5! = 6 \times 120 = 720$

#### Subcase 1.2: 1 zero
- We choose 4 characters from {A, I, M, E, 2, 7}.
- Number of ways to choose 4 characters from 6: $\binom{6}{4} = 15$
- Number of permutations of 5 characters (including 1 zero): $\frac{5!}{1!} = 120$
- Total for this subcase: $15 \times 120 = 1800$

### Case 2: 2 zeros
- We choose 3 characters from {A, I, M, E, 2, 7}.
- Number of ways to choose 3 characters from 6: $\binom{6}{3} = 20$
- Number of permutations of 5 characters (including 2 zeros): $\frac{5!}{2!} = 60$
- Total for this case: $20 \times 60 = 1200$

### Summing the cases:
- Total number of valid sequences: $720 + 1800 + 1200 = 3720$

### Finding $\frac{N}{10}$ :
- $\frac{3720}{10} = 372$

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: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.