The Escape from Prison Puzzle is a fascinating mathematical riddle that combines logic, sequences, and strategic thinking. In this puzzle, a prisoner must climb a staircase of 100 steps to escape, but there’s a catch. A policeman is waiting at the very top, ready to catch him if he lands exactly on the 100th step.
This problem is a classic example of how combinatorics and recurrence relations can solve real-world-style puzzles. It’s a favorite in reasoning exams, coding interviews, and math contests because it challenges your ability to recognize patterns and apply the Fibonacci sequence logic cleverly.
Escape from Prison Puzzle – Setup and Objective
Let’s understand the setup:
A prisoner stands at the bottom of a staircase with 100 steps.
He can move in only two ways each night:
- Climb 1 step, or
- Climb 2 steps.
However, if the prisoner reaches exactly the 100th step, the policeman catches him. The goal is to find the number of ways the prisoner can climb without landing exactly on step 100.
Objective
Find:
How many possible sequences of 1-step and 2-step moves can the prisoner make without ever landing exactly on the 100th step.
Step-by-Step Solution for the Prisoner and Policeman Puzzle
This puzzle is deeply connected to Fibonacci-like recurrence because the number of ways to reach any step depends on the sum of ways to reach the two previous steps.
Step 1: Calculate the Total Ways to Reach the 100th Step
At any given point, the prisoner has two options:
- Move 1 step forward, or
- Move 2 steps forward.
If we define f(n) as the total number of ways to reach the n-th step, the relationship between steps can be expressed as:
f(n)=f(n−1)+f(n−2)f(n) = f(n-1) + f(n-2)f(n)=f(n−1)+f(n−2)
This is the Fibonacci recurrence relation.
Initial Conditions:
- f(1)=1f(1) = 1f(1)=1 (only one way to reach the first step — a single 1-step move)
- f(2)=2f(2) = 2f(2)=2 (either two 1-steps or one 2-step move)
Thus,
f(3)=f(2)+f(1)=3f(3) = f(2) + f(1) = 3 f(3)=f(2)+f(1)=3 f(4)=f(3)+f(2)=5f(4) = f(3) + f(2) = 5 f(4)=f(3)+f(2)=5
and so on.
Using this pattern, f(100)f(100)f(100) represents the total number of ways to reach the 100th step, including the cases where the prisoner would be caught.
Step 2: Identify the Paths That End Exactly on the 100th Step
Now, we must eliminate all the sequences that end on step 100, because that’s where the policeman is waiting.
To land on step 100, the prisoner must come from:
- Step 99, by taking a 1-step move, or
- Step 98, by taking a 2-step move.
Thus, the total number of forbidden paths (ending exactly at step 100) is:
Forbidden Paths=f(99)+f(98)\text{Forbidden Paths} = f(99) + f(98)Forbidden Paths=f(99)+f(98)
These are the sequences that must be subtracted from the total to find valid escape routes.
Step 3: Compute the Valid Paths (Final Answer)
The number of valid escape paths, those that don’t end on the 100th step is given by:
Valid Paths=f(100)−(f(99)+f(98))\text{Valid Paths} = f(100) - (f(99) + f(98))Valid Paths=f(100)−(f(99)+f(98))
This expression ensures we count only the routes where the prisoner never reaches the 100th step, effectively escaping without being caught.
Explanation with Logic
This puzzle behaves like a restricted Fibonacci sequence, where every term depends on the previous two, but we subtract the terminal cases where the prisoner fails (caught at 100th step).
Here’s what happens conceptually:
- Every step adds new possible routes based on earlier moves.
- The Fibonacci pattern accumulates all possible paths.
- The subtraction removes any sequence that lands exactly at step 100, ensuring the prisoner escapes successfully.
Representation – Step Progression
| Step (n) | Formula Used | Explanation |
|---|---|---|
| 1 | f(1) = 1 | One single-step move |
| 2 | f(2) = 2 | (1+1) or (2) |
| 3 | f(3) = f(2) + f(1) = 3 | Continue pattern |
| n | f(n) = f(n-1) + f(n-2) | Fibonacci relation |
| 100 | f(100) | Total paths to step 100 |
| Forbidden | f(99) + f(98) | Paths ending on step 100 |
| Final Answer | f(100) − (f(99)+f(98)) | Valid escape paths |
Step 4: Conceptual Visualization
Imagine the staircase as a decision tree.
Each branch represents the prisoner’s choice - 1-step or 2-steps.
As the tree grows, the number of paths increases exponentially following the Fibonacci sequence.
However, any branch that lands on the 100th step is “cut off” because the prisoner gets caught. The remaining branches (up to step 99) represent successful escapes.
Final Answer – Number of Escape Paths
By combining all steps, the formula for the prisoner’s successful escape routes is:
Valid Paths=f(100)−(f(99)+f(98))\boxed{\text{Valid Paths} = f(100) - (f(99) + f(98))}Valid Paths=f(100)−(f(99)+f(98))
where f(n)=f(n−1)+f(n−2)f(n) = f(n-1) + f(n-2)f(n)=f(n−1)+f(n−2),
and the initial conditions are f(1)=1f(1) = 1f(1)=1, f(2)=2f(2) = 2f(2)=2.
This ensures the prisoner never reaches the 100th step and thus escapes safely without being caught by the policeman.
Why This Puzzle is Popular?
The Escape from Prison Puzzle is widely used in interviews and math contests because it blends storytelling with strong mathematical reasoning. It helps test skills like:
- Pattern recognition
- Dynamic programming logic
- Sequence-based reasoning
It’s especially popular in competitive programming and algorithmic interviews at companies like Google or Microsoft, as it models real-world recursion and constraints elegantly.
Similar Logic and Math Puzzles
Here are some puzzles that use similar reasoning and mathematical logic:
1. The 100 Prisoners Hat Puzzle – Parity Logic
Setup: 100 prisoners must guess their hat color using a parity strategy.
Answer: Using even-odd parity logic, at least 99 survive, sometimes all 100.
2. The River Crossing Puzzle – Sequencing Strategy
Setup: A farmer must carry a wolf, goat, and cabbage across a river.
Answer: Carry goat → wolf → cabbage → goat to ensure all are safe.
3. The Blue Eyes Puzzle – Self-Discovery Logic
Setup: Islanders discover who has blue eyes based on others’ knowledge.
Answer: If n people have blue eyes, they all leave on the nth day.
4. The Monty Hall Problem – Probability Paradox
Setup: Choose one of three doors; one hides a car, two hide goats.
Answer: Always switch; probability rises from 1/3 to ⅔.
5. The Two Doors Riddle – Lies and Truth
Setup: Two guards, one always lies, one tells the truth.
Answer: Ask, “If I asked the other guard which door leads to freedom, what would he say?” Then choose the opposite.