Educational Codeforces Round 67 F. Expected Square Beauty
https://codeforces.com/contest/1187/problem/F
\documentclass[margin=2mm]{standalone} \usepackage{amsmath,amssymb,bussproofs} \begin{document} %\begin{prooftree} \AxiomC{\(N^2\)} \UnaryInfC{\(E[N^2]\)} \AxiomC{\(\displaystyle \sum_{i} \Pr[x_i=x_{i+1}]\)} \UnaryInfC{\(\displaystyle \sum_{i}E[X_i]\)} \RightLabel{Linearity of Expecation} \UnaryInfC{\(\displaystyle E\left[\sum_{i}X_i\right]\)} \RightLabel{\(({}* -2N)\) Introduction} \UnaryInfC{\(\displaystyle -2NE\left[\sum_{i}X_i\right]\)} \AxiomC{\(\displaystyle \sum_{i} \Pr[x_i=x_{i+1}]\)} \UnaryInfC{\(\displaystyle E\left[\sum_{i}X_i^2\right] \)} \AxiomC{\(\displaystyle \sum_{i} \Pr[x_i=x_{i+1}=x_{i+2}] \)} \UnaryInfC{\(\displaystyle E\left[\sum_{i} X_i X_{i+1} \right]\)} \AxiomC{\([i+2 \le j]^{(1)}\)} \AxiomC{\(\displaystyle \Pr[x_i=x_{i+1}] \Pr[x_j=x_{j+1}] \)} \BinaryInfC{\(\displaystyle \Pr[x_i=x_{i+1} \land x_j=x_{j+1}] \)} \UnaryInfC{\(\displaystyle E[X_iX_j]\)} \RightLabel{\(\Sigma\) Introduction (1)} \UnaryInfC{\(\displaystyle \sum_{i+2 \le j} E[X_i X_j] \)} \RightLabel{Linearity of Expection} \UnaryInfC{\(\displaystyle E\left[\sum_{i+2 \le j} X_i X_j\right]\)} \BinaryInfC{\(\displaystyle E\left[\sum_{i<j}X_i X_j\right]\)} \RightLabel{\(({}*2)\) Introduction } \UnaryInfC{\(\displaystyle 2E\left[\sum_{i<j} X_i X_j\right] \)} \BinaryInfC{\(\displaystyle E\left[\sum_{i}X_i^2 + 2 p\sum_{i<j} X_i X_j\right] \)} \UnaryInfC{\(\displaystyle E\left[\left(\sum_{i}X_i\right)^2\right]\)} \RightLabel{Linearity of Expectation} \TrinaryInfC{\(\displaystyle E\left[\left(N-\sum_{i}X_i\right)^2\right] \)} \RightLabel{Let \(X_i\) be the indicator variable of \(x_i=x_{i+1}\). } \UnaryInfC{\(\displaystyle E[(N-X)^2] \)} \RightLabel{Let \(X\) be the number of \(i\) such that \(x_i=x_{i+1}\).} \UnaryInfC{answer} \DisplayProof %\end{prooftree} \end{document}