Hat puzzle! Again! Enjoy!

0:00 Introduction
3:21 Analyzing the puzzle
7:32 Chasing our dream
12:00 Another realm
20:57 Woohoo!
21:30 Conclusion

Links! Below!

---

Other relevant videos:

How researchers saved on covid tests using polynomials:
[ Ссылка ]

Previous Hat Puzzle:
[ Ссылка ]

---

How Hamming came up with Hamming Codes:

The Art of Doing Science and Engineering is a lecture series ([ Ссылка ]) and book ([ Ссылка ], also available online) by Richard Hamming. Chapter 12 of the book goes into the process behind him coming up with the Hamming Code and Hamming Balls, and the whole book is wonderfully written.

You can also check out Hamming's original paper here: [ Ссылка ]

---

And here's the proof of the Gilbert-Varshamov bound: Take any error correcting code correcting k errors. As long as you can find signals that are distance more than 2k from every codeword, keep adding them as codewords. Since their distance is more than 2k, their radius-k Hamming ball won't overlap with the radius-k Hamming balls of the other codewords. When you can't find any more signals that are distance more than 2k from every codeword, that means that every signal contains a codeword within its radius-2k Hamming ball. But a codeword can only be in the radius-2k Hamming ball of exactly (Volume of radius-2k Hamming ball)-many signals. That means that for each signal to contain a codeword within its radius-2k Hamming ball, the number of codewords must be at least (# of signals)/(Volume of radius-2k Hamming ball).

---

Thanks again to the manim community for the amazing software!

свернуть