Study Notes – Seating Arrangement (Reasoning Ability)
Target Exam: Maharashtra PSC (Public Service Commission) – Reasoning Ability
Level: MIT‑style, first‑principles, rigorous reasoning, advanced theory, edge‑cases, and a challenging problem
1. Introduction
Seating‑arrangement puzzles test the ability to:
- Formalise positional constraints (who sits next to whom, who sits opposite, relative order, etc.).
- Translate the informal description into a mathematical model (graph, permutation, constraint‑satisfaction problem).
- Deduce a unique arrangement or count the number of possible arrangements.
These puzzles often appear in multiple‑choice or short‑answer sections. A systematic approach saves time and reduces errors.
2. Modelling the Problem
| Symbol | Meaning | Example |
|---|---|---|
| (P = {p_1, p_2, \dots, p_n}) | Set of people | (P = {\text{A,B,C,D}}) |
| (S = {s_1, s_2, \dots, s_n}) | Set of seat positions | (S = {1,2,3,4}) (row) or (S = {1,2,\dots,10}) (circular) |
| (f: P \to S) | Seating function (bijection) | (f(\text{A}) = 2) |
| (C) | Set of constraints | “A sits next to B” |
A constraint can be written as a logical predicate over (f).
E.g. “A sits next to B” → (|f(A)-f(B)| = 1) (row) or “distance (d)” → (\min(|f(A)-f(B)|, n-|f(A)-f(B)|) = d) (circular).
2.1 Types of Constraints
| Type | Formalisation | Typical wording |
|---|---|---|
| Adjacency | ( | f(x)-f(y) |
| Opposite | (\min( | f(x)-f(y) |
| Between | (f(x)) lies strictly between (f(y)) and (f(z)) | “X sits between Y and Z” |
| Left/Right | (f(x) < f(y)) (left) or (f(x) > f(y)) (right) | “X sits to the left of Y” |
| Fixed Position | (f(x) = k) | “X sits in seat 3” |
| Separation | ( | f(x)-f(y) |
| Relative order | “X sits immediately after Y” → (f(x) = f(y)+1) | “X sits after Y” (not necessarily immediate) |
3. Solving Strategies
| Step | Description | Example |
|---|---|---|
| 1. Draw a diagram | Visualise seats (linear or circular) and note fixed positions. | 4 seats in a row → ` |
| 2. List constraints | Translate each sentence into a formal predicate. | “A sits next to B” → ( |
| 3. Reduce search space | Use algebraic elimination: fix one person, use symmetry, or apply the pigeonhole principle. | Fix A at seat 1 (if symmetry allows). |
| 4. Apply deduction | Use implications: if A adjacent to B and B adjacent to C, deduce possible triples. | If A next to B and B next to C (row) → A–B–C or C–B–A. |
| 5. Backtrack | When multiple options remain, branch on a choice, propagate constraints, prune impossible branches. | Choose seat for D, then for E. |
| 6. Count arrangements | If asked to count, use combinatorial formulas (factorials, inclusion–exclusion). | Total permutations (n!) minus those violating constraints. |
| 7. Verify | Check each constraint is satisfied. | Verify adjacency, opposite, etc. |
3.1 Symmetry Breaking
- In a circular arrangement, rotations are equivalent. Fix one person’s seat to break rotational symmetry.
- In a row, mirror symmetry can be broken by fixing the leftmost person.
3.2 Graph Representation
Represent seats as vertices of a graph (G=(V,E)).
- Edge ( (i,j) \in E ) if seats (i) and (j) are adjacent (row) or opposite (circular).
- Constraints become edge constraints or vertex constraints on a vertex‑labeling problem.
This perspective allows the use of graph‑theoretic algorithms (e.g., bipart