https://en.wikipedia.org/wiki/Braess%27s_paradox is very famous.
Something that definitely won't work: The parity of the number of edges.
Still, it's pretty general.
> What's so cool about the theorem is thst it proves _any_ property you can think of has _some_ sudden threshold like that.
...like what? The example you give, of the number of heads yielded from 1000 coin flips, doesn't have a sudden threshold at any point. What do you mean by a sudden threshold?
In general what I am familiar with is 'percolation theory'.
[1] https://en.wikipedia.org/wiki/Kolmogorov%27s_zero%E2%80%93on...
The puzzle instances are pseudo-random graphs in which edges are defined by the siphash24 hash function, and the solutions are cycles of length L, which have a chance of about 1/L of occurring.
A classic example is cuckoo hashing: You want to know how many edges the random graph of hashes can have before it contains a cycle, since that's when you need to rehash into a larger table. You might expect that this number is "pretty random" in that you sometimes get a cycle with few edges or sometimes have many edges but no cycle. However it turns out that it very predictably happens exactly when the graph gets to a certain size. In the same way as 1000 coin flips very predictably have 450-550 heads.
What's so cool about the theorem is thst it proves _any_ property you can think of has _some_ sudden threshold like that.