Problem #58 MEDIUM
The River Island Census
Scenario Number Theory Modular Arithmetic CRT
Problem Statement
On a small river island in the Brahmaputra delta, a government census officer named Dipankar arrives by boat every five years to count the island's inhabitants.
This year, he rows up to the island's only dock and meets the village elder, an ancient woman named Bina, who has lived there her entire life.
'How many people live on this island?' Dipankar asks, pen ready.
Bina smiles. 'I will tell you this,' she says. 'If you arrange all of us into rows of three, two people are left over. If you arrange us into rows of five, three are left over. If you arrange us into rows of seven, two are left over. And I can tell you the total is less than one hundred.'
Dipankar puts down his pen. He closes his eyes for a moment. Then he writes a number in his census book without asking another question.
How many people live on the island?
Answer & Quick Explanation
Think you've got it? Click below to check your answer.
23 people live on the island. Verified: 23 = 3×7+2 (remainder 2 when divided by 3), 23 = 5×4+3 (remainder 3 when divided by 5), 23 = 7×3+2 (remainder 2 when divided by 7). The next solution, 128, exceeds 100.
Detailed Editorial Solution
Want to see the step-by-step breakdown? Click below to reveal the editorial.
The Chinese Remainder Theorem guarantees a unique solution modulo (3×5×7=105) when the moduli are pairwise coprime — which 3, 5, and 7 are. The unique solution in the range 1-105 is found by systematic search or algebraic construction.
Step 1: Translate clues: N ≡ 2 (mod 3) means N leaves remainder 2 when divided by 3. N ≡ 3 (mod 5) means remainder 3 when divided by 5. N ≡ 2 (mod 7) means remainder 2 when divided by 7.
Step 2: Start with N ≡ 2 (mod 7): candidates are 2, 9, 16, 23, 30, 37, 44, 51, 58, 65, 72, 79, 86, 93.
Step 3: Filter for N ≡ 2 (mod 3): check which of the above leave remainder 2 when divided by 3. 2 mod 3 = 2 ✓. 9 mod 3 = 0 ✗. 16 mod 3 = 1 ✗. 23 mod 3 = 2 ✓. 30 mod 3 = 0 ✗. 37 mod 3 = 1 ✗. 44 mod 3 = 2 ✓. Remaining candidates: 2, 23, 44, 65, 86.
Step 4: Filter for N ≡ 3 (mod 5): 2 mod 5 = 2 ✗. 23 mod 5 = 3 ✓. 44 mod 5 = 4 ✗. 65 mod 5 = 0 ✗. 86 mod 5 = 1 ✗.
Step 5: Only N = 23 satisfies all three conditions and is less than 100. Verify: 23 = 7×3+2 ✓. 23 = 5×4+3 ✓. 23 = 3×7+2 ✓. N = 23.
Step 6: The next solution would be 23 + 105 = 128, which exceeds 100 — confirming uniqueness below 100.
Key Insight:
The CRT tells us that when moduli are pairwise coprime, there is always a unique solution within the product of all moduli (here 3×5×7=105). The 'less than 100' constraint was redundant in this case — but it elegantly narrows the puzzle to a single human-scale answer.