Suppose h: x rightarrow y is an (N, M)-hash function. For any y elementof H, let h^-1(y) = {x:h(x) = y} and denote s_y = |h^-1(y)|. Define S = |{{x_1, x_2}: h(x_2) = h(x_2)}|. Note that S counts the number of unordered pairs in x that collide under h. (a) Prove that sigma_y elementof y s_y = N, so the mean of the sy's is bar s = N/M. (b) Prove that S = sigma_y elementof y (s_y 2) = 1/2 sigma_y elementof y s_y^2 - N/2. (c) Prove that sigma_y elementof (s_y - bar s)^2 = 2s + N - N^2/M. (d) Using the result proved in part (c), prove that S greaterthanorequalto 1/2(N^2/M - N). Further, show that equality is attained if and only if s_y = N/M