Number of $1$'s in a Kolmogorov-random number
I've found an answer which uses certain facts I was not aware of, but it's nevertheless really good.

Our machine $M$ takes the length of a number, $n$, and an index $j$ as an input (we encode the first argument in such a way so that there was no doubt where it ends, i.e. putting $0$ in between every digit and ending with $1$). $j$ denotes the $j$-th number with less than $n/4$ ones in a lexicographic order. The only problem we have now, is to evaluate how big $j$ can be.

We have $$j_{\max}=\sum\limits_{i\leq n/4}\binom{n}{i}$$

Often, when proving Second Shannon's Theorem, the above sum (even more general, with $\lambda n,\ \lambda\in (0,1/2]$) is evaluated to be less than $2^{nH(\lambda)}$ with $H(\lambda)$ being the entropy of a non-fair coin throw.

Thus, we get $j_{\max}\leq 2^{nH(1/4)}$. Since $H(\lambda)\leq 1$, a number with less than $n/4$ ones cannot be random besides finitely many cases.

More exactly, $$C_U(x)\leq 2\log(n) + nH(1/4) + c$$ and this, for $n$ large enough, is less than $n$.