Let H $=$ $$\backslash \{$ h$\_1,$ h$\_2,...\backslash \}$$ be a collection of has functions where $h$\_$i$ : U $$\backslash$rightarrow$ $$\backslash \{0,1,...,$ M$-1\backslash \}$$ for every $$\backslash$textit$\{$i$\}$$ and we assume that $$|$U$|$$ $=$ $$2^$u$ and that M $=$ $$2^$b$ $($the same setup as in class when we designed a universal has family$).$ Recall that H is a universal hash family if $$\backslash$textbf$\{$Pr$\}$$$\_\{$h$\backslash$simeq H$\}$$$[$h$($x$)=$ h$($y$)]$$ $$\backslash$leq$ $$\backslash$frac$\{1\}\{$M$\}$$ for x$,$ y $$\backslash$epsilon$ U$.\backslash \backslash$

Consider the following, slightly different definition. We say that H is a $$\backslash$textit$\{2-$universal hash family$\}$$ if $$\backslash$textbf$\{$Pr$\}$$$\_\{$h$\backslash$simeq H$\}$$$[$h$($x$)=$ a $\backslash$wedge h$($y$)]$$ $$\backslash$leq$ $$\backslash$frac$\{1\}\{$M$^2\}$$ for all x$,$ y $$\backslash$epsilon$ U with x $

eq$ y and a$,$ b $$\backslash$epsilon$ $\backslash \{0,1,...,$ M$-1\backslash \}.\backslash \backslash$

$($a$)$ Prove that any $2-$universal hash family is also a universal hash family.$\backslash \backslash$

$($b$)$ Prove that for every $$\backslash$textit$\{$u$\}$$ and $$\backslash$textit$\{$b$\}$$ there is some universal has family from U to $\backslash \{0,1,...,$ M$-1\backslash \}($with $$|$U$|$$ $=$ $$2^$u$ and M $=$ $$2^$b$$)$ which is $$\backslash$textit$\{$not$\}$$ a $2-$universal has family.$\backslash \backslash$

$($c$)$ Give a universal has family from U $=\backslash \{0,1,2,3,4,5,6,7\backslash \}$ to $\backslash \{0,1\backslash \}$ that contains at most four functions $($and prove it is universal$).$ Is this also a $2-$universal has family? Why or why not?$\backslash \backslash$