Communication complexity


Alice enjoys watching table tennis and in her local league there are n players, each of whom is assigned an identification number between 1 and n. • Unfortunately Alice had to leave before the end of the most recent match, so she knows the two player’s numbers but not the winner. • Bob does not watch table tennis but overheard the number of the winner of that most recent match (but not the number of the loser). Other than that he did not pay attention at all and knows nothing else. Give a communication protocol which allows Alice to discover the winner from Bob. You should argue both that your protocol is correct and also give an upper bound for the number of bits used in the worst case. Protocols using fewer bits will receive more marks (Θ(log n) bit protocols will get two marks).

Pleae help