Problem 3. Impossibility of election (20 points). A symmetric function f:SkS has the property that for all s1,s2Sk, if s1 is a permutation of s2 then f(s1)=f(s2). That is, for k=3, f(1,2,3)=f(2,3,1)=f(3,1,2), etc. Consider a synchronous algorithm SymGk running on a graph G with indegree k. That is, each process Pj reads the states of exactly k other processes. In this algorithm. SymGk, every node updates its state xi according to some symmetric function f:SkS, that is, x[i]:=f(x[j](j,i)G) Show that it is impossible for SymGk to elect a leader if initially every process has the same value of x[i]. [Hint: State an invariant and prove it by induction on rounds.]