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:
SpoilerJust concatenate N with itself backwards.
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:
SpoilerSince we don't care about which ant is which, we can ignore all collisions and pretend the ants pass through each other.
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:
SpoilerIf two rectangles both have their left corner at even x and even y coordinates, then they will never intersect, so we can make them the same color.
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:
SpoilerThe naive method involves checking if, for all $$$j,k<3000,$$$ $$$\sum_{i} A_{ji}B_{ik} = C_{jk}$$$. This is cubic and will be too slow. We could try to just check if it holds for few random integers $$$j$$$, $$$k$$$, but this will probably be wrong on inputs where only one entry of $$$C_{jk}$$$ is wrong. A different approach is needed. Note, the mod 2 constraint isn't important at all for the solution so don't get confused by it.
Key observation:
SpoilerIf the matrices are equal, then for any random binary vector $$$v$$$, $$$ABv = Cv$$$.
Source: A class in complexity theory
