hash collisions - 2025 NAFTA

Packet 8: Bonus 14

Open addressing and separate chaining are two methods to deal with these events. For 10 points each:

[10m] What events may be resolved using linear or quadratic probing? These events are more likely with a high load factor.

ANSWER: hash collisions

[10e] Hash collisions are unavoidable if the number of buckets is too small by this principle. Given n boxes and more than n of the namesake animal, one box must have at least two animals by this principle.

ANSWER: pigeonhole principle [or Dirichlet’s box principle]

[10h] Collision-resistant functions can be constructed from one-way compression functions with a method this man independently discovered along with a Danish scientist. He also names trees whose nodes are labelled with hashes.

ANSWER: Ralph Merkle [accept Merkle tree]

<BC, Other Science (Computer Science)> | NAFTA-Packet-8

Heard	PPB	E %	M %	H %
20	12.50	90%	30%	5%

Back to bonuses

Conversion

Team	Opponent	Part 1	Part 2	Part 3	Total	Parts
Ana Pauker? I hardly know her!	The Umayyad Caliphate be like REPEAL NAPHTHA	10	10	10	30	MEH
Berkeley A	Stanford B	10	10	0	20	ME
Berkeley B	Team 7	0	10	0	10	E
David Foster Gromit	Polish Orthographers Posting Their Łs	0	10	0	10	E
Georgia Tech 𓂈𓆉𓃡	Say It Ain't Zhou	0	10	0	10	E
I'm just here (being trivia club president) so I won't get fined	I fear not the man who has reviewed 10000 cards once, but I fear the man who has reviewed one card 10000 times	10	10	0	20	ME
It's something unpredictable/that in the end is right/please refrain from e-mailing my wife	Copán Seethe	0	10	0	10	E
Lex	WashU	10	10	0	20	ME
Licence to C. Wright Mill	Licence to Bill	0	10	0	10	E
Maybe Ever	The Worst Trade Deal in the History of Trade Deals	0	10	0	10	E
Not Old! (Old)	Team 8	10	10	0	20	ME
St. Marx	[Redacted]	0	10	0	10	E
Stanford A	Constans Constantius and Constantine Jr.	0	10	0	10	E
Tennessee A	Girls who Just Want to Have Fun + Liam	0	10	0	10	E
The Unbearable Heaviness of History Players	UBC A	0	10	0	10	E
UBC B	Abbas I founded the Abbasids	0	10	0	10	E
Where's the nearest library, I need to have a public crashout.	The lion does not concern itself with negging teammates out of their own categories	0	10	0	10	E
William of Baskerville attempts to investigate John P. Robarts, gets turned away for not having a student card	Guelph Cloze	0	0	0	0
You Don't Have the Cards	Strange Case of Dr. Joker and Mr. Pennywise	10	10	0	20	ME
four high school generalists shock natives with fluent stock in Tocharian B	W&L+Friend	0	0	0	0

Summary

Tournament	Edition	Match	Heard	PPB	E %	M %	H %
2026 NAFTA at Stanford	01/17/2026	✓	4	15.00	100%	50%	0%
2026 NAFTA at UBC	01/17/2026	✓	2	10.00	100%	0%	0%
2025 NAFTA Online	02/14/2026	✓	4	10.00	75%	25%	0%
2026 NAFTA at Vanderbilt	02/14/2026	✓	3	16.67	100%	33%	33%
2025 NAFTA at Toronto	09/13/2025	✓	5	12.00	80%	40%	0%
2025 NAFTA at Richmond	12/20/2025	✓	2	10.00	100%	0%	0%