\author{Problem Author: Nick Wu}
\newcommand{\mingleheader}{Problem G: Mingle}

\begin{frame}{\mingleheader{}}
  \begin{block}{Problem}
    \begin{itemize}
      \item Given $n$ nonnegative integers from $0$ to $n-1$, each one
      is shifted independently and uniformly at random by an integer
      from $-k$ to $k$, and then renormalized modulo $n$ back to $[0, n-1]$.
      Compute the expected number of integers that appear exactly once.
    \end{itemize}        
  \end{block}
\end{frame}
\begin{frame}{\mingleheader{}}
  \begin{block}{Solution}
    \begin{itemize}
      \item By linearity of expectation, this is equivalent to
      computing $n$ times the probability that the integer at index $0$
      uniquely appears.
      \item This occurs with probability $\left(\frac{2k}{2k+1}\right)^{2k}$,
      since there are $2k$ integers each within range of the final value and each
      one has a probability of $\frac{1}{2k+1}$ of aligning.
    \end{itemize}        
  \end{block}
\end{frame}
