1
$\begingroup$

Randomly pick $\color{red}5$ distinct integers from $1, 2,3,4, 5,\cdots, 76, 77,78,79,\color{red}{80}$, and then sum the five integers together.

Try to find the frequencies when the last decimal digit of the sum is $0, 1,2,3,\cdots,7,8,9$ respectively.

The frequencies can be obtained by rolling out all the $\displaystyle\binom{80}{5}=24,040,016$ possible cases, and then counting per the last digits of the sum. But that is usually CPU time and memory demanding especially when $\displaystyle\binom{n}{m}$ is large.

BTW:

  1. the frequency results for the $\displaystyle\binom{80}{5}$ case is: $2,404,00\color{red}8$ for those ended with digits $0$ and $5$, while $2,404,000$ for other digits.

  2. while for $\displaystyle\binom{80}{4}$ case, it is: $158,080$ for those ended with odd number digits, and $158,236$ for even number digits.

Is there any simpler and smart way to solve such a problem?

$\endgroup$
  • $\begingroup$ you can play with thing quite a bit google calculator shows there's 375 possible sums and that means 64106.7093... times is the average per sum. in fact since that's greater than 64106 we can show via pigeonhole principle most values show up at least 64107 times each. $\endgroup$ – user451844 Aug 17 '17 at 1:53
2
$\begingroup$

The question is about the sum of a $5$-subset of $\{1,2,\dots,80\}$, taken modulo $10$.

Yes, there are some tricky ways to enumerate those.

Denote $\varepsilon_k = e^{\pi k i/5}$, $k=1,\dots,9$, $10$th roots of unity. Then $$\tag{1} \sum_{k=0}^9 \varepsilon_k^n = \begin{cases} 10, & 10\mid n,\\ 0, & 10\nmid n. \end{cases} $$

Note that $$ F(u,z) = \prod_{j = 1}^{80} (1+ u z^j) = \sum_{j,n} A(j,n) u^j z^n, $$ where $A(j,n)$ is the number of $j$-subsets with sum $n$. Therefore, the number of $5$-subsets with sum equal to $0$ modulo $10$ is equal, thanks to $(1)$, to $$ [u^5]\frac{1}{10}\sum_{k=0}^9 F(u,\varepsilon_k), $$ (the coefficient before $u^5$).

If $\varepsilon_k$ is a primitive root (i.e. $k=1,3,7,9$), then (noting that $\varepsilon^{10}_k = 1$) $$ F(u,\varepsilon_k) = \Big(\prod_{n=0}^{9}(1+u \varepsilon_k^{n})\Big)^{8} = \big(1 - (-u)^{10}\big)^{8} = (1-u^{10})^8, $$ since $\varepsilon_k^n$, $n=0,\dots,9$, are different $10$th roots of unity.

If $k=2,4,6,8$, then $\varepsilon_k$ is a primitive $5$th root of unity, so, similarly, $$ F(u,\varepsilon_k) = \big(1 - (-u)^{5}\big)^{16} = (1+u^5)^{16}. $$ Further, $$ F(u,\varepsilon_5) = \big(1-(-u)^2\big)^{40} = (1-u^2)^{40}. $$ Finally, $$ F(u,\varepsilon_0) = F(u,1) (1+u)^{80}. $$

Therefore, the number of $5$-subsets with sum divisible by $10$ is $$ [u^5]\frac{1}{10}\big( 4(1-u^{10})^8 + 4(1+u^5)^{16} + (1-u^2)^{40} + (1+u)^{80} \big)\\ = \frac25 {16 \choose 1} + \frac1{10}{80\choose 5} = 2\,404\,008. $$

The number of $4$-subsets: $$ [u^4]\frac{1}{10}\big( 4(1-u^{10})^8 + 4(1+u^5)^{16} + (1-u^2)^{40} + (1+u)^{80} \big)\\ = \frac1{10} {40 \choose 2} + \frac1{10}{80\choose 4} = 158\,236. $$

I leave you other last digits as an exercise.


If we were interested in the sum modulo some prime number, the computation would be much easier.

$\endgroup$
  • $\begingroup$ From the answer, I don't understand how to apply the same deduction to different digits. For example, in the $\binom{80}{5}$ case, It is expected that digits $0$ and $5$ have the same frequency, while others don't. How can we know the frequency difference between different digits only from the deduction? Thank you! $\endgroup$ – LCFactorization Aug 19 '17 at 21:19
  • 1
    $\begingroup$ @LCFactorization, say you need the number of subsets with sum equal to $4$ modulo $10$. Instead of the polynomial $F(u,z)$, consider $z^6 F(u,z)$ and repeat the same procedure. $\endgroup$ – zhoraster Aug 20 '17 at 9:42

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.