I read until the end and it turns out to be a nonconstructive proof via the probabilistic method!

https://en.wikipedia.org/wiki/Probabilistic_method