Hard Mode: Repeater Placement

Mission 7: Building the Quantum Internet. Part of the Quantum Courier Service, a free course from the Oxford University Quantum Information Society.

Repeaters need breathing room. Cluster them together and coherence dies before it reaches the next hop. As a combinatorics stand-in: how many ways can you place k repeaters among n segments so that no two are adjacent?

The job: write solve(n, k) that returns the number of ways to choose k non-adjacent positions from n segments (positions 1..n, and "adjacent" means consecutive integers).