A parallel computer consists of $n$ processors and $n$ memory modules. During a step, each processor sends a memory request to one of the memory modules. A memory module that receives either $one$ or $two$ requests can satisfy its request(s); modules that receive more than two requests will satisfy two requests and discard the rest. Assuming that each processor chooses a memory module independently and uniformly at random, what is the expected number of processors whose requests are satisfied?
How to solve this question?
To generalize: Given $k$ memory modules, $n$ requests uniformly from the memory modules, with each module able to serve at most $r$ requests. Denote the expected number of requests served by $\mathcal{E}(k,n,r)$.
By linearity of expectation and the restriction on number of requests: \begin{align*} \mathcal{E}(k,n,r) &= k \cdot \mathbb{E}\left[\,\text{# requests served per module}\,\right]\\ &= k \cdot \sum_{i=0}^n \min(i,r)p_i, \qquad \text{where $p_i \equiv \binom{n}{i}\left(\tfrac{1}{k}\right)^i\left(1 - \tfrac{1}{k}\right)^{n-i}$}\\ &= k\cdot \sum_{i=0}^r i p_i + k\cdot \sum_{i=r+1}^n r p_i\\ &= k\cdot \sum_{i=0}^r i p_i + k\cdot \left(\sum_{i=0}^n - \sum_{i=0}^r\right) r p_i\\ &= k r\cdot \underbrace{\sum_{i=0}^n p_i}_{=\,1} - k\cdot \sum_{i=0}^r (r-i) p_i \\ &= k r - k\cdot \sum_{i=0}^{r-1} (r-i) \binom{n}{i}\left(\tfrac{1}{k}\right)^i\left(1 - \tfrac{1}{k}\right)^{n-i}\\ &= k r - \frac{1}{k^{n-1}}\cdot \sum_{i=0}^{r-1}(r-i)\binom{n}{i} (k-1)^{n-i} \\ &= k r - \left(\,1 - \tfrac{1}{k}\,\right)^{n-r+1} k^{2-r} \cdot \sum_{i=0}^{r-1}(r-i)\binom{n}{i} (k-1)^{r-1-i} \\ \end{align*}
Specifically, for your problem: \begin{align*} \mathcal{E}(n,n,2) &= 2n - \left(\,1 - \tfrac{1}{n}\,\right)^{n-1} n^{0} \cdot \sum_{i=0}^{1}(2-i)\binom{n}{i} (n-1)^{1-i} \\ &= 2n - \left(\,1 - \tfrac{1}{n}\,\right)^{n-1} \cdot\left(\,2\cdot1\cdot (n-1)^1 + 1\cdot n\cdot(n-1)^{0}\,\right) \\ &= 2n - \left(\,1 - \tfrac{1}{n}\,\right)^{n-1} \cdot (3n-2)\\ &\sim (2-\tfrac{3}{e}) \cdot n. \end{align*}
Or more generally when $k=an$: \begin{align*} \mathcal{E}(an,n,r) &= a n r - \left(\,1 - \tfrac{1}{an}\,\right)^{n-r+1} (an)^{2-r} \cdot \sum_{i=0}^{r-1}(r-i) \binom{n}{i}(an-1)^{r-1-i} \\ &= an r - \left(\,1 - \tfrac{1/a}{n}\,\right)^{n-r+1}\cdot (an)\cdot (an)^{1-r} \cdot \left(\,\sum_{i=0}^{r-1}(r-i)\tfrac{1}{i!}n^{r-1} a^{r-1-i} + O(n^{r-2})\,\right) \\ &= a n r - an\left(\,1 - \tfrac{1/a}{n}\,\right)^{n-r+1}\cdot \sum_{i=0}^{r-1}\tfrac{r-i}{i!}(1/a)^i + O(1) \\ &\sim Cn \end{align*}
where \begin{align*} C &\equiv ar - a e^{-1/a}\sum_{i=0}^{r-1}\tfrac{r-i}{i!}(1/a)^i = ar - a e^{-1/a}\left(\, \frac{(1/a)^r}{r!} + (r-\tfrac{1}{a}) \sum_{i=0}^r \frac{(1/a)^i}{i!} \,\right) \\ &= ar - \frac{1}{e^{1/a}a^{r-1} r!} - \frac{ar-1}{e^{1/a}} \sum_{i=0}^r \frac{(1/a)^i}{i!}, \end{align*} which agrees with your special case of $a=1$ and $r=2$.