Iranian Mathematical Olympiad

Suppose that the sets are $A_1,A_2,\dots ,A_{100}$. We claim that Mahdi needs $100$ steps. First of all, notice that $100$ would be enough; by calling $(1,2)$, $(1,3)$ and $(2,3)$ he can understand $A_1$, $A_2$ and $A_3$. Because we have $$A_1=((A_1\cup A_2)-(A_2\cup A_3))\cup (A_1\cap A_2)\cup (A_1\cap A_3).$$ Then by calling $(i,3)$ for $4\le i\le 100$ he can determine all sets.

To prove that $100$ is necessary, consider a graph with $100$ vertices, and at each step connect vertices $i$ and $j$ if Mahdi calls $i$ and $j$. After $99$ steps the graph has $99$ edges so one of the connected components should be a tree. Hang the tree on a vertex and consider at each step $A_i\cup A_j=\{1\}$, $A_i\cap A_j=\varnothing$ then Mahdi can't distinguish between the case that all the sets at odd levels of the tree are empty and the sets on even levels are $\{1\}$ and the case where all the sets at odd levels are $\{1\}$ and the sets at even levels are empty. ■