Plenty of hard problems require a hard observation or several simple ones, but usually as the difficulty scales, you need more observations or need to use less obvious observations. Here I've enumerated some of my favorite problems whose solutions appear trivial in retrospect — but the 1 line observation is quite hard to come up with. You have to think really outside of the box for these! I think such problems are quite cool and hard to come by, so please add a comment if you have any other problems of this type that you've seen!
They are arranged from easiest to hardest (in my opinion).
1) For $$$N<10^6$$$, what's the Nth palindromic number in base 10 with an even number of digits? (The first is 11, then 22, 33, 44, 55, 66, 77, 88, 99, 1001).
Key observation:
Source: https://codeforces.com/contest/688/problem/B
2) A classic: $$$N < 10^6$$$ Ants are on a line of length $$$10^{15}$$$ at some positions $$$p_i$$$. Each has a starting position and direction left or right. They walk at a rate of 1 unit per second, and if 2 collide, both immediately turn around and walk the other way. How long will it be until no ants are on the line?
Key observation:
Source: https://codeforces.com/gym/102966/problem/G and other places
3) $$$N<10^5$$$ Rectangles with ODD side lengths are on a $$$10^9\times 10^9$$$ grid. The corners of each are at integer lattice points $$$(x, y)$$$. Color each of the rectangles one of 4 colors so that no adjacent two rectangles are the same color.
The four-color theorem shows that this is always possible, but provides no further insight for this problem.
Key observation:
Source: https://codeforces.com/contest/764/problem/D
4) You've got three $$$3000\times3000$$$ matrices $$$A, B,$$$ and $$$C$$$ containing only the elements 0 and 1. You need to output a boolean: if $$$AB=C$$$ with all elements of $$$AB$$$ taken mod 2. Note: Your method must work with high probability on ALL possible inputs. Maybe a lot of people want to hack your code.
Solutions that won't work:
Key observation:
Source: A class in complexity theory
