Examkin

Question

Difficulty: HardPermutations and Linear Arrangements

A security system generates unique 7-digit access codes using each of the digits 1,2,3,4,5,6,1, 2, 3, 4, 5, 6, and 77 exactly once. How many such codes can be formed in which all odd digits appear in strictly ascending order from left to right and the digit 22 appears somewhere to the left of the digit 44?

Answer: 105

Answer

The total number of valid 7-digit security access codes is 105.
Out of the total 7!=5,0407! = 5,040 unrestricted linear arrangements of the 7 distinct digits, the 4 odd digits can be ordered in 4!=244! = 24 ways, but only 1 of these orderings satisfies the strictly ascending condition. Furthermore, the digits 2 and 4 can be ordered in 2!=22! = 2 ways, with digit 2 appearing to the left of digit 4 in exactly 1 of those orderings. Therefore, the number of valid arrangements is given by 7!4!×2!=5,04024×2=5,04048=105\frac{7!}{4! \times 2!} = \frac{5,040}{24 \times 2} = \frac{5,040}{48} = 105.

Step-by-Step Solution

1
Calculate slot selections for the odd digits
35 ways
From 7 positions, selecting 4 positions for the odd digits {1, 3, 5, 7} can be done in (74)=7×6×53×2×1=35\binom{7}{4} = \frac{7 \times 6 \times 5}{3 \times 2 \times 1} = 35 ways. Since the odd digits must be ordered in strictly ascending order (1, then 3, then 5, then 7), there is only 1 valid relative order for any selection of 4 slots.
2
Determine valid arrangements for the even digits
3 ways
The remaining 3 slots are occupied by the even digits {2, 4, 6}. The total number of linear arrangements of 3 distinct digits is 3!=63! = 6. By symmetry, in exactly half of these arrangements, digit 2 appears to the left of digit 4, yielding 62=3\frac{6}{2} = 3 valid ways.
3
Multiply independent choices to find the total arrangements
105 codes
Applying the Fundamental Counting Principle, 35 (slot choices for odd digits)×1 (ordering of odd digits)×3 (arrangements of even digits)=10535 \text{ (slot choices for odd digits)} \times 1 \text{ (ordering of odd digits)} \times 3 \text{ (arrangements of even digits)} = 105.

Key Concept

Permutations with Relative Order Restrictions
Estimated Time:2m 0s
Rate this question

Topics

Permutations and Linear Arrangements

More questions from this topic