Imagine n points are distributed uniformly at random on the perimeter

of a circle that has circumference $1.$ Show that the expected number

of pairs of points that are within distance $\backslash$theta $(1/$n$2)$ of each other is

greater than $1.$ FYI: this problem has applications in efficient routing

in peer$-$to$-$peer networks.

Hint: Partition the circle into n$2/$k regions of size k$/$n$2$ for some constant k; then use the Birthday paradox to solve for the necessary k$.$