سوال ۶۱ کنکور ارشد مهندسی کامپیوتر ۱۴۰۰

Each hash function maps keys into $\{0,1\}$, so the table size is $m = 2$ and universality requires, for every pair of distinct keys $u \neq v$,

$\Pr_{h \in H}[h(u) = h(v)] \le \frac{1}{m} = \frac{1}{2}.$

The family has exactly two functions chosen uniformly, so for a pair $(u,v)$ this probability equals $\tfrac{(\text{number of } h_i \text{ that collide } u,v)}{2}$, which is $0$, $\tfrac{1}{2}$, or $1$. The bound $\le \tfrac{1}{2}$ therefore means: for every pair, at most one of $h_1, h_2$ may map them to the same value — equivalently, no pair may collide under both functions.

Form the combined map

$g(x) = \bigl(h_1(x),\, h_2(x)\bigr) \in \{0,1\}^2.$

Two keys collide under both functions exactly when $g(u) = g(v)$. To forbid any such pair, $g$ must be injective on the $n$ keys. Since the codomain $\{0,1\}^2$ has only $4$ elements, injectivity forces

$n \le 4.$

$n = 4$ is achievable. Give the four keys distinct $g$-values:

$g: \;1\mapsto(0,0),\; 2\mapsto(0,1),\; 3\mapsto(1,0),\; 4\mapsto(1,1),$

so $h_1 = (0,0,1,1)$ and $h_2 = (0,1,0,1)$. Every pair differs in at least one coordinate, so each pair collides under at most one function and $\Pr \le \tfrac{1}{2}$ holds throughout — the family is universal.

$n = 5$ fails. By the pigeonhole principle, two of the five keys must share the same pair $g(\cdot)$, so they collide under both $h_1$ and $h_2$, giving $\Pr = 1 > \tfrac{1}{2}$.

Hence the largest possible $n$ is $4$, option 2.

Exam trick: With $k$ functions each into a table of size $m$, the joint map lands in $m^{k}$ buckets; universality (no pair forced to collide everywhere) caps $n$ at $m^{k}$. Here $m^{k} = 2^{2} = 4$.