حل تشریحی سوال شماره 13 ساختمان داده ها و طراحی الگوریتم ها

خانواده $H=\left\{h_1,\dots ,h_k\right\}$ از توابع در هم ساز را در نظر بگیرید که $h_i:\left\{a,b,c,d\right\}\to \left\{0,1\right\}$ برای آن که این خانواده یک خانواده در هم ساز سراسری باشد k حداقل چقدر باید باشد؟ (خانواده توابع H سراسری است اگر و فقط اگر به ازای هر دو مقدار u و v داشته باشیم. $P{r}_{h\in H}\left[h\left(u\right)=h\left(v\right)\right]\le \frac{1}{m}$ که m اندازه جدول در هم سازی است.)