Suppose all of the 200 integers lying in between (and including) 1 and 200 are written on a blackboard. Suppose we choose exactly 100 of these numbers and circle each one of them. By the score of such a choice, we mean the square of the difference between the sum of the circled numbers and the sum of the non-circled numbers. What is the average scores over all possible choices for 100 numbers?
Problem
Source:
Tags: algebra
ThE-dArK-lOrD
02.05.2017 10:27
Let $S$ denote set of all $100$-element subset of $\{ 1,2,...,200\}$ and let $s(A)$ denote sum of all element of $A$. We want to compute the sum of all scores which is equal to $\sum_{A\in S}{(20100-2s(A))^2}=20100^2\times \binom{200}{100}-80400\sum_{A\in S}{s(A)}+4\sum_{A\in S}{s(A)^2}$ Note that $\sum_{A\in S}{s(A)}=\sum_{i=1}^{200}{\Big( i\times \binom{199}{99}\Big)}=20100\times \binom{199}{99}$ $\sum_{A\in S}{s(A)^2}=\sum_{i=1}^{200}{\sum_{A\in S,i\in A}{is(A)}}=\sum_{i=1}^{200}{i\Big( \sum_{j=1,j\neq i}^{200}{j\binom{198}{98}+i\binom{199}{99}\Big) }}=\sum_{i=1}^{200}{i\Big( 20100\times \binom{198}{98}+i(\binom{199}{99}-\binom{198}{98})\Big)}=20100^2\binom{198}{98}+(\binom{199}{99}-\binom{198}{98})\sum_{i=1}^{200}{i^2}$. So the required sum is equal to $20100^2\Big( \binom{200}{100}-4\binom{199}{99}+4\binom{198}{98}\Big)+4\binom{198}{99}\times \frac{200\times 201\times 401}{6} =\frac{200^2\times 201}{3}\binom{198}{99}$ Finally, the average acore is equal to $\frac{\frac{200^2\times 201}{3}\binom{198}{99}}{\binom{200}{100}}=\frac{134000000}{199}$