Problem 5 (20 points). Consider the following generalization of Power of 2 choices to d > 2 choices: 1. Prepare of perfectly random hash functions 1%,. . . , hd : U % [n]. 2. For each ball A? allocate it into the bin among his d. choices {h1(A), . . . ,hd(A)} with the lightest load at this moment. Suppose we are throwing n balls into n bins. Modify the proof to show that: With probability 1 7172, the maxload is logd log n + 0(1) instead of log2 log n + 0(1)