The Maximimum Monochromatic k-Cliques for Complete Graph Show: 
For a complete graph $K_{n}$, there is a coloring of the edges with $2$ colors, such that the number of monochromatic $k$-Cliques is a maximum of $\binom{n}{k}2^{1-\binom{k}{2}}$.
I do not know where to begin on this exercise. As a hint, our professor gave us the following pre-exercise, which I have been able to solve:

Let $n \in \mathbb N$, and $\mathcal{K}$ be the set of permutations
  possible for a set $\{1,...,n\}$. Let $\sigma \in \mathcal{K}, $ such
  that $\sigma: [n] \to [n]$ is a randomly selected permutation. Find
  the probability space, define random variable $X$ as the number of
  fixed points and find $\mathbb E[X]$.

How do the two questions fit together? I am lost. 
 A: This problem is a classical problem in probabilistic graph theory due to Erdos and can be found in pretty much any introductory course on probabilistic graph theory.
Denote by $I_{x_1,...,x_k}$ the indicator function of the k-clique of vertices ${x_1,...,x_k}$(for a random coloring of $K_n$). Thus $I_{x_1,...,x_k}$ is 1 if ${x_1,...,x_k}$ is monochromatic or 0 else. Then the total number of monochromatic k-Cliques is equal to $\sum_{x_1,...,x_k}I_{x_1,...,x_k}$ where the sum is taken over all ${n\choose k}$ groups of k-vertices in the graph. The expected number of monochromatic k-Cliques is then equal to ${n\choose k}P({x_1,...,x_k}$ is monochromatic $) = {n\choose k}2^{1-{k\choose 2}}$, by linearity of expectation and also by $E(I_A)=P(A)$, for any event set A, so you can find at least one graph with ${n\choose k}2^{1-{k\choose 2}}$ monochromatic k-Cliques. 
For completion, note that $P({x_1,...,x_k}$ is monochromatic $) = 2^{1-{k\choose 2}}$ because ${x_1,...,x_k}$ is monochromatic if it is either red or blue(whence the factor of 1 in its exponent and the probability that each of its $k \choose 2$ edges is red is exactly $\frac{1}{2}$)
