Skip to content
Get started

Subsets whose sum is divisible by five

MediumCombinatorics6 min

How many subsets of {1,2,…,10}\{1,2,\dots,10\} (the empty set included) have a sum that is divisible by 55?

Show hints (2)+
  1. Write subset sums as exponents in ∏k=110(1+xk)\prod_{k=1}^{10}(1+x^k) and average over the fifth roots of unity.
  2. Plug x=−1x=-1 into x5−1=∏r(x−ωr)x^5-1=\prod_r(x-\omega^r) to evaluate ∏r=04(1+ωr)\prod_{r=0}^{4}(1+\omega^r).

Answer

Reveal answer →

208

Create a free account to see the full worked solution and track your progress.

Interview format: Prop Trading, Systematic & Data-Driven Trading

Related questions