This is one of the best puzzles I’ve come across:

100 prisoners have their names placed in 100 boxes so that each box contains exactly one name. Each prisoner is permitted to look inside 50 boxes of their choice, but is not allowed any communication with the other prisoners. What strategy maximizes the probability that every prisoner finds their own name?

I heard about this puzzle years ago, spent several days thinking about it, and never quite solved it. Actually, I did think of a strategy in which they would succeed with probability over 30% (!), which was the unbelievably-high success rate quoted in the puzzle as I heard it posed. However, I ended up discarding the strategy, as I didn’t think it could possibly work (and probably wouldn’t have been able to prove it would work in any case).