The Coat Check

Parts A and B: a formula that works mod $m$ cannot hide the remainder

With $h(x)=xmod64$, any eight multiples of 64, or any eight tickets with the same remainder, share a hook. Picking $a$ and $b$ at random does not help if the formula still works mod $m$: $h(x)-h(y)\equiv a(x-y)\left(\mathrm{mod}256\right)$, so $b$ cancels, and two tickets 256 apart are together for every $a$. The pranksters never needed to know tonight's choice.

Part C: why exactly 3/31

Fix two different tickets $x,y$. For $a\ne 0$, the map $(a,b)\mapsto (ax+b,ay+b)mod31$ is a bijection onto the ordered pairs $(r,s)$ of different values: given $r$ and $s$, solve $a=(r-s)(x-y{)}^{-1}$ and $b=r-ax$. So each of the $31·30=930$ choices of $(a,b)$ gives a different pair $r\ne s$, and the tickets collide exactly when $r\equiv s\left(\mathrm{mod}8\right)$. Among $0,\dots ,30$, seven remainders mod 8 occur four times and one (7) occurs three times. The colliding ordered pairs number $7·4·3+3·2=90$, and $90/930=3/31\approx 0.097$, below $1/m=0.125$. It is the same for every pair of tickets.

Allowing $a=0$ breaks the bijection. Then $h$ ignores the ticket on $1/31$ of the nights, and the worst pair's chance rises to $121/961$, just above $1/8$.

Part D: work mod a prime, reduce mod $m$ at the end

Take a prime $P$ above every ticket ($2^{61}-1$ works), draw $a$ from $1$ to $P-1$ and $b$ from $0$ to $P-1$ with the night's seed, and return $((ax+b)modP)modm$. The argument of part C shows that any two tickets collide with probability at most about $1/m$, whatever tickets the adversary picks. The argument needs the two tickets to differ mod $P$, which is why $P$ must exceed every ticket. The prime $2^{31}-1$ is one short: ticket $2^{31}-1$ is $0$ mod $P$, so it shares a hook with ticket $0$ every night. The grader tries that pair. Passing part D is evidence; this argument is the proof. In the grader's run, the worst pair it tried shared a hook on 44 of 400 nights at $m=16$: close to $400/16=25$, far below the 100 allowed. Multiply-shift ($a$ odd and random, keep the top bits of $axmod{2}^{64}$) is cheaper and guarantees $2/m$.

The broken families fail at once: with x % m, (a * x) % m or (a * x + b) % m, tickets 0 and 16 share a hook on all 400 nights at $m=16$.

Going further

• Hash flooding is a real attack. Crosby and Wallach showed in 2003 that web servers could be slowed to a crawl by keys chosen to collide. In 2011 Klink and Wälde demonstrated it against the form parsing of most web frameworks. Languages then randomized their string hashing: Python uses SipHash for strings since version 3.4 (PEP 456). Small integers still hash to themselves.
• Stronger families. Universal hashing bounds pairs. Some algorithms, such as linear probing, need more independence. Simple tabulation hashing (Pătrașcu and Thorup) is fast and behaves far better than its independence suggests.
• Part E points at the limit of the model: universal hashing assumes the adversary never sees the outcome. Timing and observed collisions leak the draw, which is why keyed functions such as SipHash are used instead.

References

1. J. L. Carter, M. N. Wegman. Universal classes of hash functions. Journal of Computer and System Sciences 18(2), 1979.
2. M. Dietzfelbinger, T. Hagerup, J. Katajainen, M. Penttonen. A reliable randomized algorithm for the closest-pair problem. Journal of Algorithms 25(1), 1997.
3. S. A. Crosby, D. S. Wallach. Denial of service via algorithmic complexity attacks. USENIX Security Symposium, 2003.
4. J.-P. Aumasson, D. J. Bernstein. SipHash: a fast short-input PRF. INDOCRYPT, 2012.
5. M. Pătrașcu, M. Thorup. The power of simple tabulation hashing. Journal of the ACM 59(3), 2012.