Karnataka Police Sub‑Inspector (SI) – Reasoning Ability
Topic: Seating Arrangement
“Seating arrangement” problems are a staple of reasoning tests. They test combinatorial reasoning, logic, and often an ability to translate verbal constraints into mathematical models.”
This study note gives a MIT‑level treatment: we start from first principles, build general models, and then tackle advanced variations and edge‑cases. Finally, a challenging problem is posed, with full solution.
1. Foundations
| Concept | Definition | Why it matters in seating |
|---|---|---|
| Permutation | Ordered arrangement of n distinct objects | The basic count of ways to seat n people in n seats. |
| Combination | Selection of k objects from n, order ignored | Useful when we only care about who sits where, not the order of seats. |
| Derangement | Permutation with no fixed points | Models “no one sits in their own seat” constraints. |
| Inclusion–Exclusion Principle | Counting objects with multiple constraints | Handles overlapping restrictions (e.g., “A cannot sit next to B or C”). |
| Graph Representation | Vertices = people, edges = forbidden adjacency | Translates constraints into a graph problem (e.g., graph coloring). |
| Latin Square | n×n array with each symbol once per row/column | Generalised seating (e.g., round tables, multiple rounds). |
| Cycle / Circular Permutations | Arrangements considered the same under rotation | Applies when the table is round. |
2. Modelling a Seating Problem
-
Define the Universe
- N people
- S seats (often S = N, but not always).
- Seats may be labelled (e.g., 1…S) or unlabeled (circular).
-
Identify Variables
- Let (x_i) be the seat assigned to person i.
- All (x_i) must be distinct if seats are unique.
-
Express Constraints
- Adjacency: “A cannot sit next to B” → (|x_A - x_B| \neq 1).
- Fixed Positions: “C must sit at seat 4” → (x_C = 4).
- Group Constraints: “Group G of 3 must sit together” → consecutive seats.
- Relative Positioning: “D sits to the left of E” → (x_D < x_E).
- Circular: “No two friends sit together” → (|x_i - x_j| \neq 1 \mod S).
-
Translate to a Counting Problem
Use combinatorial formulas, inclusion–exclusion, or graph theory to count the number of valid seatings.
3. Core Counting Techniques
3.1 Basic Permutations
When seats are distinct and there are no constraints:
[ #\text{seatings} = N! . ]
3.2 Fixed Positions
If k people have fixed seats, then
[ # = (N-k)! . ]
3.3 Adjacency Constraints
Example: No two of the 4 friends A,B,C,D sit together.
- Treat friends as a block – but because no two can sit together, we use the complement: count seatings where at least one adjacent pair exists and subtract from total.
- Inclusion–Exclusion:
For each pair (AB, AC, …) define event (E_{ij}) = “i sits next to j”.
[ #\text{valid} = N! - \sum |E_{ij}| + \sum |E_{ij}\cap E_{kl}| - \dots ] - These counts involve factorials of reduced numbers (because the pair is treated as a block).
3.4 Derangements (No one sits in their own seat)
[ !N = N! \sum_{k=0}^{N} \frac{(-1)^k}{k!}. ]
Useful when e.g., “No officer sits in the seat they normally occupy”.
3.5 Circular Arrangements
If rotation is irrelevant (a round table), divide by N:
[ #_{\text{circular}} = \frac{N!}{N} = (N-1)! . ]
If reflection is also irrelevant, divide by 2.
4. Graph‑Theoretic View
- Vertices = people.
- Edge between two people if they cannot sit adjacent.
- Goal: Find a Hamiltonian path (linear seating) or cycle (circular seating) that respects adjacency constraints → a graph colouring or perfect matching problem.
4.1 Chromatic Number
If we colour vertices such that no two adjacent vertices share a seat, the chromatic number gives the minimum number of seats needed.
4.2 Edge‑Colouring for Round Tables
If we want to seat people so that no two disallowed pairs are adjacent, we can model the seating as a cycle and check for a proper edge‑colouring of the complement graph.
5. Advanced Topics
5.1 Latin Squares and Multiple Rounds
- When seating repeats over k rounds, we can use a Latin square of order N to ensure each person sits once in each seat across rounds.
5.2 Bipartite Matching
- If there are two types of seats (e.g., front/back) and each person has a preference, we solve