The Four-Digit Lockbox

Minimum 15 operations: 0→1(A)→2(B)→4(B)→8(B)→9(A)→18(B)→19(A)→38(B)→76(B)→77(A)→154(B)→308(B)→616(B)→617(A)→1234(B). Every target 0–9999 is reachable since repeated +1 generates all numbers mod 10000.

Model as a BFS problem. States = integers 0-9999. Transitions = +1 mod 10000 and ×2 mod 10000. Find shortest path from 0 to 1234. Alternatively, work backwards from 1234: reverse operations are ÷2 (if even) and -1. Step 1: Forward BFS is systematic but slow to describe. Work backwards from 1234 using reverse operations: if current number is even, its predecessor via Op B is n/2. If odd, must come from n-1 (via Op A, so predecessor was n-1). Always, predecessor via Op A is n-1. Step 2: Backwards from 1234 (even): came from 617 via ×2. 617 (odd): came from 616 via +1. 616 (even): from 308. 308 (even): from 154. 154 (even): from 77. 77 (odd): from 76 via +1. 76 (even): from 38. 38 (even): from 19. 19 (odd): from 18 via +1. 18 (even): from 9. 9 (odd): from 8 via +1. 8 (even): from 4. 4 (even): from 2. 2 (even): from 1. 1 (odd): from 0 via +1. Step 3: Reverse path: 0 → 1 → 2 → 4 → 8 → 9 → 18 → 19 → 38 → 76 → 77 → 154 → 308 → 616 → 617 → 1234. Step 4: Count operations: 0→1 (A), 1→2 (B), 2→4 (B), 4→8 (B), 8→9 (A), 9→18 (B), 18→19 (A), 19→38 (B), 38→76 (B), 76→77 (A), 77→154 (B), 154→308 (B), 308→616 (B), 616→617 (A), 617→1234 (B). Total: 15 operations. Step 5: Can we reach any number? +1 generates all numbers from 0 (by repeated addition). So yes, every number 0–9999 is reachable. With ×2 as an additional operation, we can reach any target faster. The graph is strongly connected. Step 6: The minimum is 15 operations via the path above. BFS verification would confirm no shorter path exists. Key Insight: Working backwards transforms an open-ended search into a deterministic decode: each even number has a unique ÷2 predecessor via Op B, and every number has n-1 as a predecessor via Op A. The backward path greedily prefers ÷2 (halving) over -1 (decrement), since halving reduces the problem size exponentially while -1 reduces it by only 1.