Examkin

Question

Difficulty: HardCounting with Restrictions and Repetitions

A 7-digit security passcode is to be formed using the digits 1,1,2,2,3,4,1, 1, 2, 2, 3, 4, and 55. How many distinct 7-digit passcodes can be formed such that neither the two 11 s nor the two 22 s are adjacent to each other?

  1. A
    540
  2. 660Answer
  3. C
    780
  4. D
    900
  5. E
    1,020

Answer

660 distinct passcodes can be formed.
To find the number of arrangements where neither identical pair is adjacent, we use complementary counting. First, compute total unrestricted arrangements of the digits 1,1,2,2,3,4,51,1,2,2,3,4,5, which is 7!2!2!=1,260\frac{7!}{2!2!} = 1,260. Next, by treating (11)(11) as a single block, there are 6!2!=360\frac{6!}{2!} = 360 arrangements with adjacent 11 s. Similarly, treating (22)(22) as a single block yields 6!2!=360\frac{6!}{2!} = 360 arrangements with adjacent 22 s. Arrangements where both pairs are adjacent treat (11)(11) and (22)(22) as two single blocks alongside 3,4,53,4,5, giving 5!=1205! = 120 arrangements. Applying Inclusion-Exclusion gives 360+360−120=600360 + 360 - 120 = 600 forbidden arrangements. Subtracting from the total gives 1,260−600=6601,260 - 600 = 660.

Step-by-Step Solution

1
Calculate the total number of distinct arrangements without any restrictions.
Total arrangements = 7!2!×2!=5,0404=1,260\frac{7!}{2! \times 2!} = \frac{5,040}{4} = 1,260.
There are 7 digits total, with the digit 1 repeated twice and the digit 2 repeated twice.
2
Calculate the number of arrangements where the two 11 s are adjacent.
N(adjacent 1s)=6!2!=7202=360N(\text{adjacent } 1\text{s}) = \frac{6!}{2!} = \frac{720}{2} = 360.
Treat the pair (11)(11) as a single unit, leaving 6 items: (11),2,2,3,4,5(11), 2, 2, 3, 4, 5 with two identical 22 s.
3
Calculate the number of arrangements where the two 22 s are adjacent.
N(adjacent 2s)=6!2!=7202=360N(\text{adjacent } 2\text{s}) = \frac{6!}{2!} = \frac{720}{2} = 360.
Treat the pair (22)(22) as a single unit, leaving 6 items: 1,1,(22),3,4,51, 1, (22), 3, 4, 5 with two identical 11 s.
4
Calculate the number of arrangements where both the two 11 s and two 22 s are simultaneously adjacent.
N(both adjacent)=5!=120N(\text{both adjacent}) = 5! = 120.
Treat (11)(11) and (22)(22) each as single distinct units, giving 5 distinct items: (11),(22),3,4,5(11), (22), 3, 4, 5.
5
Apply the Principle of Inclusion-Exclusion to find the total restricted count.
Valid passcodes = 1,260−(360+360−120)=1,260−600=6601,260 - (360 + 360 - 120) = 1,260 - 600 = 660.
Subtract the union of forbidden cases from the total arrangements: N(total)−[N(1s adj)+N(2s adj)−N(both adj)]N(\text{total}) - [N(\text{1s adj}) + N(\text{2s adj}) - N(\text{both adj})].

Key Concept

Complementary Counting with Inclusion-Exclusion Principle on Permutations of Repeated Elements
Estimated Time:2m 0s
Rate this question

Topics

Counting with Restrictions and Repetitions

More questions from this topic