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

This is the classic Carter–Wegman universal hash family $h_{a,b}(x) = \big((ax + b) \bmod n\big) \bmod m, \qquad m = 20.$

Conditions for universality. The family is provably universal only when $n$ is a prime (with $n \ge |U|$ and $n > m$). The parameters range as $a \in \{1, 2, \ldots, n-1\}, \qquad b \in \{0, 1, \ldots, n-1\}.$

Why $a \neq 0$: if $a = 0$ then $h_{0,b}$ is a constant function — every pair of keys collides with probability $1 > \tfrac{1}{m}$ — so $a = 0$ is excluded. This leaves $n-1$ choices for $a$ and $n$ choices for $b$, hence $|H| = n\,(n-1).$

Test each option — we need a value of the form $n(n-1)$ with $n$ prime:

Only $506 = 23 \cdot 22$ has the form (prime) $\times$ (prime $-1$), with $n = 23$ prime. So $H$ can have $506$ elements, and option 3 is correct.

Exam trick: The size of the Carter–Wegman family is $p(p-1)$ where $p$ is the prime modulus. To spot the valid count, factor each candidate as a product of two consecutive integers $n(n-1)$ and check that the larger factor $n$ is prime — only $506 = 23\cdot 22$ passes.