# Number of $100$-element subsets with sum congruent to $1$ mod $5$

Given the set of first $2015$ natural numbers $\{1,2,3...,2015\}$. How many $100$-element subsets of this set are there such that the sum of the elements of the subset is congruent to $1$ modulo $5$?

• Do you have any ideas? This looks suspiciously like it might be from a contest, possibly a live contest... – Bob Krueger Jan 12 '16 at 16:11
• My guess is $\frac{1}{5}\times \binom {2015}{100}$, but I have no idea how to show it. – Peter Jan 12 '16 at 16:54
• @Peter: you are off by only one part in $10^{137}$ – Ross Millikan Sep 13 '18 at 22:29

Consider all the subsets that contain exactly one of $\{1,2,3,4,5\}$ and $99$ other numbers. For each choice of the $99$ other numbers there are five such subsets, of which one has a sum that is $1 \bmod 5$. Similarly, of all the subsets that have two of $\{1,2,3,4,5\}, \frac 2{10}$ have a sum that is $1 \bmod 5$ because there are $10$ two element subsets of $\{1,2,3,4,5\}, 2$ of which have each sum $\bmod 5$. The same argument works for those containing three or four.
For the subsets that have no elements or all of $\{1,2,3,4,5\}$ we can make the same argument for $\{6,7,8,9,10\}$. Exactly $\frac 15$ of the subsets that contain some but not all of them have sum $1 \bmod 5$. We continue upward. Each subset gets grouped into a group of $5$ or $10$ subsets that have the same number of elements in the lowest block of $5$ that is incomplete and all the same higher elements. That group is equally distributed among the values $\mod 5$. Once we consider all the blocks of $5$ we have accounted for all the subsets that do not consist of $20$ blocks of $5$ numbers. There are $403$ such blocks of $5$ numbers, so there are ${403 \choose 20}$ subsets that consist of these blocks, all of which have sum $0 \bmod 5$.
We can partition the ${2015 \choose 100}$ subsets into ${403 \choose 20}$ that have sum $0 \bmod 5$ and ${2015 \choose 100}-{403 \choose 20}$ that are equally distributed among the moduli. There are therefore $$\frac 15\left({2015 \choose 100}-{403 \choose 20}\right)\approx 4.717\cdot 10^{170}$$ subsets with sum $1 \bmod 5$ The difference from $\frac 15$ of the total $100$ element subsets is only of order $10^{33}$, so it is trivial by comparison.