A problem from Alon, N., & Spencer, J. H. (2015). The probabilistic method. John Wiley & Sons.
Outline suggested: Take a random two-coloring. Let $X$ be the number of monochromatic $K_a$ and find $E[X]$. For some coloring the value of $X$ is at most this expectation.
My approach so far:
Make a random two-coloring (w.l.g red/blue) of $K_n$ with $p(e = blue) = 1/2$. Let $X_{ \left\{ V_i \right\}_{i = 1}^{n}}$ be the indicator random variable that the subset of vertices $\left\{ V_i \right\}_{i = 1}^{a}$ is a monochromatic $K_a$.
$$E[X_{ \left\{ V_i \right\}_{i = 1}^{a}}] = P(X_{ \left\{ V_i \right\}_{i = 1}^{a}}) = \frac{1}{2^a} \times P(\left\{ V_i \right\}_{i = 1}^{a} = K_a) $$
if I am not mistaken $P(\left\{ V_i \right\}_{i = 1}^{a} = K_a) = 1 $.
Let $X$ be the number of monochromatic $K_a$ in $G$ then:
$$E[X] = \sum_{\left\{ V_i \right\}_{i = 1}^{a} \in V} E[X_{\left\{ V_i \right\}_{i = 1}^{a}} ]= \sum_{ \left\{ V_i \right\}_{i = 1}^{a} \in V} \frac{1}{2^a} = {n \choose a} \frac{1}{2^a}$$
Which is different from $ {n \choose a} 2 ^{1 - {a \choose 2}}$. I suppose I have a mistake in the calculation of expectancy. I also don't know how to make the final conclusion: For some coloring the value of $X$ is at most this expectation => there is a 2-coloring of $K_n$ with at most ${n \choose a} 2 ^{1 - {a \choose 2}}$ monochromatic $K_a$