Advanced Study Notes – Seating Arrangements
Subject: Reasoning Ability – Teacher Eligibility Test (Mizoram TET)
Audience: University‑level (MIT‑style) students, advanced problem‑solving
1. Introduction
A seating arrangement problem asks you to place a set of people (or objects) into a set of seats subject to a list of constraints. The constraints may involve:
- Adjacency (who sits next to whom)
- Relative Position (who is left/right/front/back of whom)
- Distance (exact or at least a number of seats apart)
- Groupings (subsets that must sit together or apart)
- Seat Restrictions (specific seats or ranges that are forbidden or required)
The difficulty lies in reconciling all constraints simultaneously. This set of notes takes you from the first principles of permutation and graph theory to advanced reasoning techniques that are routinely used in competitive exams and research.
Key Idea: A seating arrangement can be modelled as a constraint‑satisfaction problem (CSP). Each seat is a variable, each person is a value, and constraints restrict the admissible assignments.
2. First Principles
2.1 Basic Definitions
| Concept | Formalisation | Example |
|---|---|---|
| Permutation | A bijection ( \pi : {1,\dots,n}\to{1,\dots,n}) | Order of 8 students in a row |
| Seat | An index (s_i) (e.g., seat 1, seat 2, …) | Seat 3 in a classroom |
| Adjacency | ( | \pi(i) - \pi(j) |
| Relative Position | ( \pi(i) < \pi(j)) (left of) or (>) (right of) | C sits to the left of D |
| Distance | ( | \pi(i) - \pi(j) |
| Group Constraint | ({p_1,\dots,p_k}) occupy consecutive seats | G,H,I must sit together |
2.2 Variables and Domains
- Variables: (X_1,\dots,X_n) where (X_k) denotes the person sitting in seat (k).
- Domain: (D(X_k)={1,\dots,n}) (person indices).
- Assignment: (X_k \mapsto p) means person (p) sits in seat (k).
A solution is a bijective assignment satisfying all constraints.
2.3 Constraint Types
| Type | Constraint | CSP Representation |
|---|---|---|
| Unary | Seat 5 must be person A | (X_5 = A) |
| Binary | A sits left of B | (X_A < X_B) |
| N‑ary | G,H,I consecutive | ( |
| Global | No two teachers sit together | For all ((p,q)) teachers, ( |
3. Graph‑Theoretic Modelling
3.1 Directed Graph of Precedence Constraints
- Vertices: People.
- Edge (p \to q): “(p) must sit strictly left of (q)”.
- No cycles: A cycle would make the constraints inconsistent (no topological ordering exists).
Theorem 1 (Topological Sort)
A set of left‑of/right‑of constraints is satisfiable iff the corresponding directed graph is acyclic.
Proof: If acyclic, a topological ordering gives a valid left‑to‑right seat order. If cyclic, no total order can respect all edges. ∎
3.2 Undirected Graph of Adjacency Constraints
- Vertices: People.
- Edge (p-q): “(p) must sit adjacent to (q)”.
This graph can be decomposed into connected components.
- Each component must occupy a contiguous block of seats.
- The relative order inside the component is constrained by additional left/right constraints.
3.3 Distance Constraints as Edge Weight Bounds
For a constraint “(p) and (q) must be exactly (d) seats apart”, encode as:
[ |X_p - X_q| = d \quad \Longleftrightarrow \quad X_q - X_p = \pm d ]
This becomes a difference constraint system, solvable by the Bellman–Ford algorithm in (O(n^3)) for (n) people.
4. Advanced Theory & Algorithms
4.1 Constraint Satisfaction Problem (CSP)
- Backtracking: Explore assignments depth‑first, prune when a constraint is violated.
- **Forward