Imagine n points are distributed independently and uniformly at ran- dom on the circumference of a circle that has circumference of length 1. Let the distance between a pair of points on the circumference be the length of the arc between them. Show that the expected number of pairs of points that are within distance 0(1a) of each other is greater than 1. FYI: this problem has applications in efficient routing in peer-to-peer networks. Hint: Partition the circumference of the circle into n-/k arcs of length k2 for some constant k; then use the Birthday paradox to solve for the necessary k. Imagine n points are distributed independently and uniformly at ran- dom on the circumference of a circle that has circumference of length 1. Let the distance between a pair of points on the circumference be the length of the arc between them. Show that the expected number of pairs of points that are within distance 0(1a) of each other is greater than 1. FYI: this problem has applications in efficient routing in peer-to-peer networks. Hint: Partition the circumference of the circle into n-/k arcs of length k2 for some constant k; then use the Birthday paradox to solve for the necessary k