Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

2016 MPFG Problem 18

Problem

Let $T = \{1, 2, 3, . . . , 14, 15\}$. Say that a subset $S$ of $T$ is handy if the sum of all the elements of $S$ is a multiple of $5$. For example, the empty set is handy (because its sum is $0$) and $T$ itself is handy (because its sum is $120$). Compute the number of handy subsets of $T$.

Solution 1

We can use roots of unity to solve this problem.

$F(x) = \Pi_{k=1}^{15}(1+x^k)$

$\frac{(F(1)+F(w)+F(w^2)+F(w^3)+F(w^4)}{5}$ $(w^5=1)$

$(1+w^0)(1+w^1)(1+w^2)(1+w^3)(1+w^4) = 1+w^5 = 2$

$F(w) = F(w^2) = F(w^3) = F(w^4) = 2^3 = 8$

$\frac{2^{15}+4\cdot8}{5} = \boxed{6560}$

~cassphe

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2016_MPFG_Problem_18&oldid=258944"