Knots & Gaps | Quantitative for GMAT PDF Download

Introduction

Permutations are arrangements of items in a specific order, and often, there are additional conditions that affect how we arrange these items. Two common conditions are knots and gaps. 

Understanding these concepts can help in solving more complex permutation problems where specific elements need to be adjacent or separated by certain positions.

What is a Knot?

• A knot in permutations refers to a situation where two or more items must be arranged together as a single unit. 
• This restriction reduces the number of possible arrangements by treating the "knotted" items as inseparable within the arrangement.
• Key Points:
  (a) Items in a knot must stay together.
  (b) We treat the knot as a single unit for counting purposes.
  (c) The items within a knot may have an internal order or be freely arranged.
• For Example,
  You have four people, $A$A, $B$B, $C$C, and D, and you must arrange them in a row. However, B and $C$C must sit together. How many possible arrangements are there? 

Sol: This question can be resolved in the following ways.

• Create a Knot: Since $B$B and $C$C must sit together, we treat them as a single unit or "knot." Let's denote this knot as $BC$BC.
• Count Units: Now, we have three units to arrange: A, $D$D, and $BC$BC (where $B$BC is considered a single unit).
• Arrange the Units: The three units can be arranged in $3!$= 6 ways.
• Arrange within the Knot: Within the knot, $BC$BC, B, and $C$C can be arranged in $2!$=2 ways (i.e., BC or CB).
• Total Arrangements:
• $3!\times 2!=6\times 2=123!\; \backslash times\; 2!\; =\; 6\; \backslash times\; 2\; =\; 12$
• So, there are 12 possible arrangements of A, B, C, and $D$D with $B$B and C together.

What is a Gap?

• A gap is a requirement that certain items must not be adjacent or must have specific distances between them. Gaps create restrictions on where items can be placed in relation to each other, affecting the total count of valid arrangements.
• Key Points:

  (a) Gaps prevent certain items from being adjacent.

  (b) They can specify that certain items must be at a fixed distance apart.

  (c) Gap constraints reduce the number of valid permutations.

• For Example, You have five people, A, B, C, D, and E, and you need to arrange them in a row such that B and D are not adjacent. How many possible arrangements are there?

Sol: 
(a) Calculate Total Arrangements Without Restriction:
First, arrange the five people without any restrictions. This gives us:
5! = 120
(b) Calculate Arrangements Where B and D Are Together:
- Treat B and D as a "knot," making it a single unit.
- Now, we have four units to arrange: (BD), A, C, and E.
- These four units can be arranged in 4! = 24 ways.
- Within the knot, B and D can be arranged in 2! = 2 ways.
(c )Total Arrangements with B and D Together:
4! × 2 = 24 × 2 = 48
(d) Calculate Valid Arrangements Where B and D Are Not Together:
Subtract the arrangements where B and D are together from the total arrangements:
120 - 48 = 72
Final Answer: There are 72 possible arrangements where B and D are not adjacent.

Solved Example

Example 1: Eight books are placed on a shelf. Two specific books, X and Y, must always be together. How many ways can the books be arranged?

a) 5,040
b) 7,560
c) 8,640
d) 10,080

Sol: 

1. Treat X and Y as a single block, reducing the arrangement to 7 units.
2. Arrange the 7 units: 7! = 5,040 ways.
3. Within the (XY) block, X and Y can switch places in 2 ways.
Total arrangements = 7! × 2 = 5,040 × 2 = 10,080

Example 2: Nine runners are arranged in a line. If two specific runners, A and B, must always stand next to each other, how many ways can they be arranged?
a) 72,576
b) 80,640
c) 120,960
d) 161,280

Sol: 

1. Treat A and B as one "block," giving us 8 units.
2. Arrange the 8 units: 8! = 40,320 ways.
3. Within the (AB) block, A and B can switch places in 2 ways.
Total arrangements = 8! × 2 = 40,320 × 2 = 80,640

Example 3: Five colored blocks are arranged in a line: red, blue, green, yellow, and white. If the red and blue blocks must sit next to each other, how many ways can the blocks be arranged?
a) 48
b) 72
c) 96
d) 120

Sol:
1. Treat the red and blue blocks as a single unit, resulting in 4 units.
2. Arrange the 4 units: 4! = 24 ways.
3. Within the red-blue block, they can switch places in 2 ways.
Total arrangements = 4! × 2 = 24 × 2 = 48.
Answer: A) 48

Example 4: Eight people are seated around a circular table. How many ways can they be arranged if two specific people, P and Q, do not sit next to each other?
a) 3,600
b) 4,320
c) 5,040
d) 5,760

Sol: 
1. For circular arrangements of 8 people, the total number of unrestricted arrangements is given by (8 - 1)! = 7! = 5,040.
2. Calculate the arrangements where P and Q are seated next to each other by treating them as a single "block," reducing the arrangement to 7 units around the table.
3. Arrange the 7 units in a circular arrangement: (7 - 1)! = 6! = 720.
4. Within the (PQ) block, P and Q can switch places in 2 ways.
Total arrangements with P and Q together = 6! × 2 = 720 × 2 = 1,440.
5. Subtract the restricted cases from the total arrangements: 5,040 - 1,440 = 3,600.

Example 5: Six friends are seated in a row. How many arrangements are possible if two specific friends, F and H, must not sit next to each other?
a) 240
b) 360
c) 480
d) 600

Sol: 
1. Calculate the total number of unrestricted arrangements for 6 friends: 6! = 720.
2. Calculate the arrangements where F and H are together by treating F and H as a single "block," giving us 5 units to arrange.
3. Arrange the 5 units: 5! = 120 ways.
4. Within the (FH) block, F and H can switch places in 2 ways.
Total arrangements with F and H together = 5! × 2 = 120 × 2 = 240.
5. Subtract the restricted cases: 720 - 240 = 480.