Roots of Unity Filter

MathDash
Last updated 2025-01-24

1 Example

s h
Example 1.1 (2018 AIME I #12)

y
a l
For every subset 𝑇 of 𝑈 = {1, 2, 3, . . . , 18}, let 𝑠(𝑇 ) be the sum of the elements of 𝑇 ,
with 𝑠(∅) defined to be 0. If 𝑇 is chosen at random among all subsets of 𝑈 , the prob-

D n
ability that 𝑠(𝑇 ) is divisible by 3 is 𝑚
𝑛 , where 𝑚 and 𝑛 are relatively prime positive
integers. Find 𝑚.

t h e O
Solution. Roots of unity filter is a technique that has generating functions as a prereq, so

a s
please read about that first. Now that you are done reading about generating functions,
suppose we have a generating function

M U
∞
∑︁

l
𝑓 (𝑥) = 𝑎𝑖 𝑥 𝑖 .

y
𝑖=0

B rna
Let 𝜔 be a primitive 𝑛-th root of unity. Note the following fact:
𝑛−1 𝑛−1 ∞ ∞ 𝑛−1
1 ∑︁ 𝑗 1 ∑︁ ∑︁ 𝑖𝑗 1 ∑︁ 𝑖
∑︁
𝑓 (𝜔 𝑥) = 𝑎𝑖 𝑥𝑖 𝜔 = 𝑎𝑖 𝑥 (𝜔𝑖 ) 𝑗 .

e
𝑛 𝑗=0
𝑛 𝑗=0 𝑖=0
𝑛 𝑖=0 𝑗=0

t
Now, recall the fact that if 𝜔 𝑖 ≠ 1, then

In
𝑛−1
∑︁
(𝜔𝑖 ) 𝑗 = 0.
𝑗=0

It then follows that

∞ 𝑛−1 ∞
1 ∑︁ 𝑖
∑︁
𝑖 𝑗
∑︁
𝑎𝑖 𝑥 (𝜔 ) = 𝑎𝑘𝑛 𝑥 𝑘𝑛 .
𝑛 𝑖=0 𝑗=0 𝑘=0

In particular, we have filtered 𝑓 to only have nonzero coefficients for the terms whose
exponent is divisible by 𝑛. This trick is called the Roots of Unity Filter and it is very
helpful whenever a counting problem asks you to count the cases that are some specific
modulo class. In this problem, we are counting subsets whose sum is 0 mod 3. Note
that the natural generating function for the sum of a randomly chosen subset is
18
Ö 1 + 𝑥𝑖
𝑓 (𝑥) = .
2
𝑖=1
1
MathDash (Last updated 2025-01-24) Roots of Unity Filter

Let 𝜔 be a third root of unity. Since we are computing the probability the sum is 0 mod
3, we look at the following generating function:
∞
𝑓 (𝑥) + 𝑓 (𝜔𝑥) + 𝑓 (𝜔2 𝑥) ∑︁
= 𝑃(𝑇 = 3𝑘)𝑥 3𝑘 .
3
𝑘=0

Plugging in 𝑥 = 1 gives the answer we want! We then want to compute 𝑓 ( 1) , 𝑓 (𝜔) , and
𝑓 (𝜔2 ) . Obviously, 𝑓 ( 1) = 1. Recall that 𝜔 satisfies 𝜔2 + 𝜔 + 1 = 0. It then follows that
18 6 6
Ö 1 + 𝜔𝑖 Ö ( 1 + 𝜔)( 1 + 𝜔2 )( 1 + 1) Ö −𝜔2 · −𝜔 · 2
𝑓 (𝜔) = = = = 2−12 .
2 8 8
𝑖=1 𝑘=1 𝑖=1

Since 𝜔 2 is the conjugate of 𝜔 , it follows that 𝑓 (𝜔 2 ) = 2−12 as well. Our probability is

h
then
1 + 2−12 + 2−12 2048 + 1 683

s
= =

y
.
3 3 · 211 2048

a l
It follows that 𝑚 = 683. □

hD O n
a t s e
y M l U
B rna
te
In

2
MathDash (Last updated 2025-01-24) Roots of Unity Filter

2 Problems
There are 7 total points available in this unit, including feedback. Try to complete at least
1
2
of the total points.

https://mathdash.com/contest/roots-of-unity-filter

[1] Problem 1 (1992 AHSME #29). An ”unfair” coin has a 2/3 probability of turning up
heads. If this coin is tossed 50 times, what is the probability that
 the total number of
2 50

1 1 1 1 1 2
heads is even? (A) 25 1− 1+


3
(B) 2 350
(C) 2
(D) 2 350
(E) 3

[1] Problem 2 (2017 AMC 12A #25). The vertices 𝑉 of a centrally symmetric hexagon in
the complex plane are given by

h
√ √ 1 1 1 1
 
𝑉= 2𝑖, − 2𝑖, √ ( 1 + 𝑖), √ (−1 + 𝑖), √ ( 1 − 𝑖), √ (−1 − 𝑖) .

s
8 8 8 8

a ly
For each 𝑗 , 1 ≤ 𝑗 ≤ 12, an element 𝑧 𝑗 is chosen from 𝑉 at random, independently of the
Î12
other choices. Let 𝑃 = 𝑗=1 𝑧 𝑗 be the product of the 12 numbers selected. What is the

D n
probability that 𝑃 = −1?

h O
52 · 11 22 · 5 · 11

t
5 · 11 5 · 11 5 · 7 · 11
(A) (B) (C) (D) (E)
310 2 · 310 39 2 · 310 310

a s e
[1] Problem 3 (2014 HMMT Guts #21). Compute the number of ordered quintuples of
nonnegative integers (𝑎1 , 𝑎2 , 𝑎3 , 𝑎4 , 𝑎5 ) such that 0 ≤ 𝑎1 , 𝑎2 , 𝑎3 , 𝑎4 , 𝑎5 ≤ 7 and 5 divides

M U
2 𝑎1 + 2 𝑎2 + 2 𝑎3 + 2 𝑎4 + 2 𝑎5 .

y l
[1] Problem 4 (2020 HMMT Combo #6). Alice writes 1001 letters on a blackboard, each

B rna
one chosen independently and uniformly at random from the set 𝑆 = {𝑎, 𝑏, 𝑐}. A move
consists of erasing two distinct letters from the board and replacing them with the third
letter in 𝑆 . What is the probability that Alice can perform a sequence of moves which
results in one letter remaining on the blackboard? If your answer can be written in the
𝑎 − 𝑎−𝑐

e
form where 𝑎, 𝑏, 𝑐 are positive integers with gcd (𝑎, 𝑏) = 1, find 4𝑐 · (𝑎2 + 𝑏2 ) .

t
𝑏
[i]Proposed by Daniel Zhu.[/i]

In
[1] Problem 5 (1986 IMO SL 10). Three persons 𝐴, 𝐵, 𝐶 , are playing the following game:

A 𝑘 -element subset of the set {1, ..., 1986} is randomly chosen, with an equal probability
of each choice, where 𝑘 is a fixed positive integer less than or equal to 1986. The winner
is 𝐴, 𝐵 or 𝐶 , respectively, if the sum of the chosen numbers leaves a remainder of 0, 1, or
2 when divided by 3.

For what values of 𝑘 is this game a fair one? (A game is fair if the three outcomes are
equally probable.)

[1] Problem 6 (2017 HMMT Combo #8). Kelvin and 15 other frogs are in a meeting, for
a total of 16 frogs. During the meeting, each pair of distinct frogs becomes friends with
probability 12 . Kelvin thinks the situation after the meeting is cool if for each of the 16
frogs, the number of friends they made during the meeting is a multiple of 4. Say that
the probability of the situation being cool can be expressed in the form 𝑎𝑏 , where 𝑎 and
𝑏 are relatively prime. Find 𝑎.
3
MathDash (Last updated 2025-01-24) Roots of Unity Filter

[1] Feedback. Please let me know what you thought of this unit! In particular, I would
like to know:

• which problems you thought were nice, too easy/difficult, helpful, etc.;

• what needs clarification; and

• how this unit could be improved.

s h y
D a n l
a t h e O
M U s
y
B rna l
te
In