4
$\begingroup$

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$?

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

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.