🏠 Home

🧠 Logic Puzzles Worksheet

Two classic mathematical puzzles — explore divisibility theory and probability strategy

/ 30
🚪 Part A: The 100 Doors Problem
Topics: factors, divisors, perfect squares
The Setup: There are 100 closed doors in a row, numbered 1 to 100. 100 people walk past them one by one.

Person 1 toggles every door (opens all).
Person 2 toggles every 2nd door (2, 4, 6…).
Person 3 toggles every 3rd door (3, 6, 9…).
Person n toggles every nth door.

Question: After all 100 people have walked past, which doors are open?
Key Idea: A door is toggled once for each of its divisors. Since doors start closed, a door ends open only if it is toggled an odd number of times — meaning it has an odd number of divisors.

Divisor count for selected doors:

Door Divisors Count Odd or Even? Open or Closed?
61, 2, 3, 64EvenClosed
91, 3, 93OddOpen
121, 2, 3, 4, 6, 126EvenClosed
161, 2, 4, 8, 165OddOpen
201, 2, 4, 5, 10, 206EvenClosed
251, 5, 253OddOpen

Final state of all 100 doors (green = open):

📝 Questions
1
List all the divisors of door 36. How many divisors does it have? 2 marks
2
Will door 36 be open or closed at the end? Explain why using the concept of divisors. 2 marks
3
For most numbers, divisors come in pairs. For example, door 20 has pairs (1, 20), (2, 10), (4, 5). Explain why this means door 20 ends up closed. 2 marks
4
Door 9 has divisors 1, 3, 9. The divisor 3 appears as its own pair because 3 × 3 = 9. What type of number is 9, and why does this give it an odd number of divisors? 2 marks
5
List all the doors that end up open after all 100 people have passed. 2 marks
6
Extension: How many doors would remain open if there were 200 doors and 200 people? Explain your reasoning without listing them all. 3 marks
🔢 Part B: The 100 Prisoners Problem
Topics: probability, permutations, cycles, strategy
The Setup: 100 prisoners are each assigned a unique number from 1 to 100. In a room there are 100 boxes, also labelled 1 to 100. Inside each box is a slip of paper with a random number (a secret permutation — every number appears exactly once).

Each prisoner enters the room alone, may open up to 50 boxes, then must leave without communicating with any other prisoner.

If every single prisoner finds their own number, they all go free. If even one prisoner fails, they all stay imprisoned.

Question: Can the prisoners agree on a strategy beforehand that gives them a meaningful chance of success? What is the best possible strategy?
Two Approaches:

Random guessing: Each prisoner independently opens 50 random boxes. P(one prisoner succeeds) = 1/2.
P(all 100 succeed) = (1/2)¹⁰⁰ ≈ 0.0000000000000000000000000000008%
Cycle-following strategy: Each prisoner starts at the box with their own number, opens it, reads the number inside, then opens that box next — following the chain until they either find their number or run out of turns.
P(all succeed with cycle strategy) ≈ 31.18%

Example: The cycle-following strategy

Suppose the boxes contain this arrangement (box number → slip inside):
Box 1→3, Box 2→7, Box 3→1, Box 4→6, Box 5→5, Box 6→2, Box 7→4

Prisoner 2 starts at Box 2 → reads 7 → opens Box 7 → reads 4 → opens Box 4 → reads 6 → opens Box 6 → reads 2 ✓ Found in 4 steps. This forms the cycle: 2→7→4→6→2.

Key insight: All 100 numbers form closed cycles. Every prisoner following this strategy will find their number as long as their cycle has length ≤ 50. The strategy fails only if any cycle in the arrangement has length > 50.
📝 Questions
1
A prisoner randomly opens 50 out of 100 boxes. What is the probability that they find their own number slip? Write it as a fraction and a percentage. 2 marks
2
Using random guessing independently, calculate the probability that all 100 prisoners succeed. Express your answer as a power of a fraction and explain why it is effectively zero. 3 marks
3
Using the arrangement in the hint box above, trace the path that Prisoner 4 would follow using the cycle-following strategy. What cycle do they belong to? 3 marks
4
Explain why the strategy fails if there is a single cycle of length 51 or more. Why can't prisoners in that cycle save themselves by searching randomly instead? 3 marks
5
The probability that a random arrangement of 100 numbers has no cycle longer than 50 is approximately 1 − ln(2) ≈ 31.18%. In practical terms, if 10,000 groups of 100 prisoners all used the cycle strategy, approximately how many groups would go free? 2 marks
6
Extension: The exact probability of success is 1 − (1/51 + 1/52 + ... + 1/100). Use a calculator to verify this is approximately 0.3118. Why do you think each term 1/k represents the probability of a cycle of exactly length k existing? 4 marks

Answer Key

🚪 Part A: 100 Doors

A1.Divisors of 36: 1, 2, 3, 4, 6, 9, 12, 18, 36 → 9 divisors
A2.Door 36 will be open. It has 9 divisors (odd number), so it is toggled 9 times — starting closed, it ends open. 36 is a perfect square (6²), so its square root (6) pairs with itself.
A3.Door 20 has pairs (1,20), (2,10), (4,5) — each pair produces 2 toggles (open then closed). With 3 pairs = 6 toggles total (even), the door returns to its original closed state.
A4.9 is a perfect square. Its square root (3) is its own divisor pair because 3×3=9. This "unpaired" divisor makes the total count odd (3 divisors), so the door is toggled an odd number of times and ends open.
A5.1, 4, 9, 16, 25, 36, 49, 64, 81, 100 — the perfect squares from 1² to 10².
A6.With 200 doors, the open doors are perfect squares up to 200. Since √200 ≈ 14.14, there are 14 open doors (1², 2², …, 14²). The rule is: the number of open doors = ⌊√n⌋ where n is the total number of doors.

🔢 Part B: 100 Prisoners

B1.Each prisoner opens 50 out of 100 boxes → P(success) = 50/100 = 1/2 = 50%
B2.P(all 100 succeed) = (1/2)¹⁰⁰ ≈ 7.9 × 10⁻³¹. This is effectively zero because 100 independent events each with 50% probability compound: the joint probability decreases exponentially with each additional prisoner.
B3.Prisoner 4: Box 4 → reads 6 → Box 6 → reads 2 → Box 2 → reads 7 → Box 7 → reads 4 ✓. Cycle: 4→6→2→7→4 (length 4). Found in 4 steps (well within 50).
B4.If a cycle has length 51+, all prisoners in that cycle need to traverse the full cycle to find their number — but they only have 50 turns. No prisoner in that cycle can succeed regardless of what they try. Switching to random search doesn't help because the cycle-following strategy is already optimal; random search could accidentally miss the slip even if it lands in a shorter chain.
B5.31.18% of 10,000 groups = approximately 3,118 groups would go free.
B6.Verification: 1 − Σ(1/k for k=51 to 100) ≈ 1 − 0.6882 ≈ 0.3118 ✓. Each term 1/k gives the probability that a specific element (say prisoner 1) belongs to a cycle of exactly length k — there are C(99, k−1) ways to choose the other k−1 members, but the probability a particular labelled cycle of length k exists in a random permutation of 100 is exactly 1/k. Summing over all "fatal" lengths (51–100) gives the failure probability.

Answer Key

Part A: 100 Doors

A1.1, 2, 3, 4, 6, 9, 12, 18, 36 → 9 divisors
A2.Open. 9 divisors (odd), so toggled 9 times. 36 = 6² is a perfect square.
A3.Pairs (1,20),(2,10),(4,5) → 6 toggles (even) → door returns to closed.
A4.Perfect square. Square root (3) pairs with itself → odd number of divisors → open.
A5.1, 4, 9, 16, 25, 36, 49, 64, 81, 100
A6.⌊√200⌋ = 14 open doors (1² through 14²).

Part B: 100 Prisoners

B1.50/100 = 1/2 = 50%
B2.(1/2)¹⁰⁰ ≈ 7.9 × 10⁻³¹ ≈ 0%. Independent probabilities multiply.
B3.Box 4→6, Box 6→2, Box 2→7, Box 7→4 ✓. Cycle: 4→6→2→7→4 (length 4).
B4.A cycle of length 51+ requires 51 steps to complete; prisoners only get 50. No strategy can overcome this constraint.
B5.31.18% × 10,000 ≈ 3,118 groups go free.
B6.1 − Σ(1/k, k=51→100) ≈ 0.3118 ✓. Each 1/k = probability a labelled cycle of length k exists in a random permutation.
fractionrush.com  ·  Logic Puzzles Worksheet  ·  Think carefully, work clearly!