Here I've enumerated some of my favorite problems. The 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://mirror.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://mirror.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://mirror.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