Logical Reasoning – BITSAT
Blood Relations & Direction Sense Test
Level: MIT‑style, first‑principles view
Format: Markdown study notes
Goal: Build a rigorous, systematic toolbox that works on every BITSAT‑style puzzle.
1. Overview
| Topic | Core Idea | Why It Matters |
|---|---|---|
| Blood Relations | People are linked by parent‑child links; the graph is a directed acyclic graph (DAG). | Every statement is a directed edge (A→B = “A is parent of B”) or an equivalence (A=B). |
| Direction Sense Test | People are points on a plane; statements are relative positional constraints. | These are essentially directed edges in a partially ordered set (poset) of directions (N, NE, E, SE, S, SW, W, NW). |
Both problems reduce to constraint satisfaction on a graph. The same algorithmic ideas (transitive closure, parity checks, cycle detection) apply.
2. Blood Relations
2.1 Formal Model
- Vertices: People (V={p_1,p_2,\dots}).
- Edges: Directed edge (p_i \rightarrow p_j) means (p_i) is a parent of (p_j).
- Constraints:
- Parenthood: One child has exactly two parents (except at the top of the chain).
- No cycles: A person cannot be an ancestor of themselves.
- Generational Parity: The generation of a person is the length of the longest path from a root.
If (g(p)) denotes generation, then (g(parent) = g(child)-1).
2.2 Graph‑Theoretic Properties
| Property | Implication |
|---|---|
| DAG | No cycles → the graph is a forest. |
| Transitive closure | From (p_i\rightarrow p_j) and (p_j\rightarrow p_k), deduce (p_i\rightarrow p_k). |
| Parity | If (p_i) is a grandparent of (p_k), then (g(p_i)-g(p_k) \equiv 2 \pmod{2}). |
| Sibling relation | (p_i) and (p_j) are siblings iff they share a common parent. |
| Cousin relation | Two persons are first cousins iff their parents are siblings. |
2.3 Solving Strategy – Step by Step
- Translate every statement into a directed edge or equivalence.
- “A is the mother of B” → (A \rightarrow B).
- “C is the brother of D” → (C \sim D) (same parents).
- Build a directed graph (adjacency list).
- Propagate parent‑child edges via transitive closure (e.g., Floyd‑Warshall or repeated DFS).
- Assign generations by topological sorting.
- Check parity: every parent–child pair must differ by 1.
- Resolve siblings: if two persons share a parent, they are siblings; check for contradictions.
- Answer each query by inspecting the graph.
- Validate: run a cycle detection algorithm; any cycle → contradiction → “no solution”.
2.4 Advanced Theory
2.4.1 Matrix Representation
Let (A) be the adjacency matrix of the DAG ( (A_{ij}=1) if (i) is parent of (j)).
- The transitive closure is (T = A + A^2 + A^3 + \dots + A^{n-1}).
- If (T_{ij}=1) then (i) is an ancestor of (j).
- Compute (T) using repeated squaring (log‑time for large graphs).
2.4.2 Parity & Generation Constraints
Define a generation vector (g).
For each edge (i \rightarrow j), enforce (g_j - g_i = 1).
This is a system of linear equations over integers; solvable via Gaussian elimination.
If a solution exists, the graph is consistent.
2.4.3 Edge Cases
| Situation | How to Handle |
|---|---|
| Missing parents | Treat as root nodes (generation 0). |
| Multiple roots | The family is a forest; queries across trees are inconclusive unless stated. |
| Contradictory statements | Detect via cycle detection or unsatisfiable linear system. |
| Ambiguous gender | Add a gender attribute to vertices; constraints like “mother” require female. |
| Half‑siblings | Not allowed in standard BITS |