Expected number of heads after flipping any $k$ coins for $x$ rounds

Question

The game works as follows:

• You start with $n$ coins, all facing heads before flipping. You are instructed to select any $k$ coins at random and invert them. This process is done for $x$ rounds. Find the expected number of heads after the above process.

Found this problem from an old math contest, thoughts on how to approach it?

Answer 1

Hints

• A coin will end up showing heads if it gets flipped an even number of times.
• By symmetry,$$P(\text{coin}\ \ c\ \ \text{gets flipped an even number of times})$$ is the same for all coins.
• Therefore, if $\ H\ $ is the number of coins showing heads after $\ x\ $ rounds of flipping, then\begin{align} E(H)&=\sum_{c=1}^nP(\text{coin}\ \ c\ \ \text{gets flipped an even number of times})\\ &=n\,P(\text{coin}\ \ 1\ \ \text{gets flipped an even number of times}) \end{align}
• The probability that coin $\ 1\ $ gets flipped in any given round is $\ \frac{k}{n}\ $, independently of whether it got flipped in any other round.
• Therefore, the distribution of the number of times coin $\ 1\ $ gets flipped in $\ x\ $ rounds is binomially distributed with parameters $\ x\ $ and $\ p=\frac{k}{n}\ $:\begin{align} P(\text{coin}\ \ 1\ \ \text{gets flipped}\ \ r\ \ \text{times})={x\choose r}\left(\frac{k}{n}\right)^r\left(1-\frac{k}{n}\right)^{n-r}\ . \end{align} Can you now see how to evaluate $\ E(H)\ $?
• I agree with Gareth Ma's comment below that the result he cites (which I wasn't aware of) is also worth noting.