61–70 of 76 posts
Here's my writeup, spoilers: We're looking for a lossy compression function that maps strings of length 23 (answers) to strings of length 12 (bits of information in 5400 min). We seek to minimize the number of errors, aka the Hamming distance. Under the Hamming distance metric, the space of strings forms a hypercube where two strings are adjacent if they are related by a bit flip (one error).[1] This gives an elegant…
Solvable by basic information analysis > answer at least N out of the 23 questions correctly This represents S(N) = \sum_{i=N}^23 \binom{23}{i} acceptable states of correct answers out of 2^23 all possible states, which requires -log_2(S(N)/2^23) bits of self-information transmittable with a code of alphabet size of 5400. Therefore the largest N that satisfies this is 20. 23 - log_2(S(20)) = 12, log_2(5400) = 12.399
But you can use those 12 bits as a key into some pre-arranged set of information, each of which carries more information.
Presumably the extra credit is that the binary Golay code is closely related to the Leech Lattice, and thus to the entire moonshine situation, which gets you to string theory. See: https://en.wikipedia.org/wiki/Leech_lattice https://en.wikipedia.org/wiki/Monstrous_moonshine http://motls.blogspot.com/2015/03/umbral-moonshine-and-golay...
Pick 5400 23-bit vectors (the answers you will write) and your friend picks the one that minimizes its Hamming distance to the true answer. 5400*23 + 5400*23*22/2 so answering 21 questions with certainty is impossible. (Pick the true answers so as to maximize the Hamming distance between it and whatever answer you decide to write, regardless of the scheme used.) And there is a size 4096 [1] see n = 23, R = 3 here htt…
If someone could ELI5 this, that'd be great!
You ask your buddy what the correct word is, and a dictionary holding all 23 letter combinations would be incredibly long, however in English there's not really all that many words, so your buddy can simply tell you the right word is on page 2352 of the dictionary and the word you pick might not be it, but it'll be close enough.
I tried to avoid using 5 yr old words to explain EE telecom coding, which isn't going to help much, so this is more "in the spirit of the problem" than being an exact analogy.
Pick 5400 23-bit vectors (the answers you will write) and your friend picks the one that minimizes its Hamming distance to the true answer. 5400*23 + 5400*23*22/2 so answering 21 questions with certainty is impossible. (Pick the true answers so as to maximize the Hamming distance between it and whatever answer you decide to write, regardless of the scheme used.) And there is a size 4096 [1] see n = 23, R = 3 here htt…
Correct! You're the second person to find the answer (the first was not on HN). Now for the extra credit part: What's the connection between this solution and string theory?
Expanding on this, though, you can improve the average result against an arbitrarily-powerful test-writer by first XOR'ing the test answers with a pre-shared value (key); the resulting value is random (even to very powerful test-writers), so e.g. encoding possible answers into the unused values improves your expected result (i.e. data rate.)
Presumably the extra credit is that the binary Golay code is closely related to the Leech Lattice, and thus to the entire moonshine situation, which gets you to string theory. See: https://en.wikipedia.org/wiki/Leech_lattice https://en.wikipedia.org/wiki/Monstrous_moonshine http://motls.blogspot.com/2015/03/umbral-moonshine-and-golay...
Yes. In particular, the Leech Lattice gives rise to Bosonic String Theory.
A simple approach that gives 13 correct answers minimum is to have him walk out after X seconds, where X is the number of true answers. Answer true for everything if X is greater than 12. Otherwise answer false for everything. This uses only 6 bits of information, and you should be able to pack some extra info rather easily into the remaining 7. Thinking about alternative approaches leads me to think that the only ca…
Pick 5400 23-bit vectors (the answers you will write) and your friend picks the one that minimizes its Hamming distance to the true answer. 5400*23 + 5400*23*22/2 so answering 21 questions with certainty is impossible. (Pick the true answers so as to maximize the Hamming distance between it and whatever answer you decide to write, regardless of the scheme used.) And there is a size 4096 [1] see n = 23, R = 3 here htt…
If someone could ELI5 this, that'd be great!
You'll only have the time at which your friend leaves (in seconds since the start of the exam). Knowing only this, whatever you two scheme, you'll have to write down your answers (from a scheme you both agreed on beforehand like "leaving after 324 seconds means answer true for the first 7 questions and false for the rest", "leaving after 325 seconds means answer false everywhere", ...) once your friend leaves. So really, you're just a transcriber. During the exam, its your friend who decide what you're going to write down by picking the right second to leave at.
Of course, they'll pick the second which makes you write as many correct answers as possible. (And of course, you'll want to pick the best scheme to help with that. But let's see what you can't do, no matter the scheme, first.)
Why can't you just always get all answers right? Because there are too many possible set of answers (2^23 for 23 questions) and your friend can only choose from the 90 * 60 = 5400 you two agreed on before the start of the exam.
In fact, you can't even be sure of getting 22 questions right. For each second (from 0 to 5399), there are only 23 set of true answers to the exam (among 2^23) for which leaving at that second gets you exactly one answer wrong (namely, one of getting each of the questions wrong). So 5400 + 5400 * 23 is an upper on the number of sets of true answers for which you'll get at most one answer wrong (using whatever scheme). Since 5400 + 5400 * 23 is still (much) less than 2^23, there will be many set of true answers to the exam where your friend doesn't have a choice but to make you write down many wrong answers.
The same goes for getting 21 answers right. For each second, there are 23 * 22 / 2 set of true answers for which leaving the exam at that time gets you exactly two questions wrong. (Pick the first question to get wrong, pick the second question to get wrong, divide by 2 because there are two ways to pick these two questions.)
5400 + 5400 * 23 + (5400 * 23 * 22 / 2)
It turns out that getting 20 answers right is possible. Now you have to actually pick a scheme. We can't just make the same calculation and add
5400 * 23 * 22 * 21 / (2 * 3)
1 + 23 + 23 * 22 / 2 + 23 * 22 * 21 / (2 * 3)
In your scheme, the only thing that matters is which 5400 set of answers your friend can make you write (swapping which answer goes with which second doesn't change anything).
As it happens, people have made tables of the minimum and maximum number of seconds needed to cover all 2^23 possibilities for getting at most 3 answers wrong. And its 4096 seconds which is less than 5400. In fact, the table contain ranges for different total number of questions and different number of questions that you can get wrong.
(I think there's something more interesting about this particular scheme that gets you 4096 but I haven't read all the other comments yet and haven't thought about this questions more since.)
Earlier quoted context omitted.
This is still an ELI21 at least :) ELI5-s should use cars cookies or candies to explain :)
We always have to be wrong, but we can bunch up all the ways we can be wrong so they're always close to being right. Each way to be right will have a few ways to be wrong as neighbours, so even if we're wrong, we aren't wrong by much.