Littlewood-Offord Problem

The number of points inside the circle is 10 ≤ 

6

3

 = 20.

All the red points are outside the black circle.

Form the

2

n

sums (black dots) of all possible subsets of

n

vectors (red dots). If all

n

vectors have norm at least 1, then at most



n

⌊

n

2

⌋



of the vectors lie in the green circle of diameter 1. (The function

⌊x⌋

is the floor of

x

.)