Visit five cities and come home by the shortest route. Simple to state, brutal to solve
A salesman must visit a handful of cities exactly once each and return to where he started, covering the shortest total distance. For a handful of cities you can just check every possible order; the question is what happens as the city count grows, and whether any shortcut method could ever reliably beat brute-force checking.
Reveal the answer
For small cases, trying every route and comparing total distances works fine, but the number of possible routes grows factorially: ten cities already have over 180,000 distinct routes to check. First studied formally by Karl Menger in 1930, the travelling salesman problem became one of the clearest examples of 'NP-hard': no algorithm is known that solves every instance efficiently as cities scale up, and finding one (or proving none exists) remains an open question at the heart of computer science.