5 ms·
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*
by asrp 10y ago
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 < 2**23
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 < 5400 covering code [1] so answering 20 question is possible (by picking the 23-bit vectors in that code).
[1] see n = 23, R = 3 here http://www.sztaki.hu/~keri/codes/2_tables.pdf http://www.sztaki.hu/~keri/codes/2_tables.pdf
Edit: formatting
- cperciva 10y agoCorrect! 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?
- dvt 10y agoThis was a neat brain-teaser (I took an information theory class years ago so it was a nice refresh), but the answer ended up being a lot less interesting than I had hoped :P
- cperciva 10y agoI said it was cute, not that it was interesting. :-) (And while asrp's answer is correct, it would have been nice if he had stated what the code is rather than merely citing the fact that it exists.)
- asrp 10y agoSadly, I can only give the Google answer to this one: > Working on a branch of physics called supersymmetry, Dr. James Gates Jr., discovered what he describes as the presence of what appear to resemble a form of computer code, called error correcting codes, embedded within, or resulting from, the equations of supersymmetry that describe fundamental particles.
- sp332 10y agoI don't remember the details, but the possible transitions between particles have the same pattern as the valid codes in a Reed-Solomon code. So any particle is possible, but the transitions seem to have been error-corrected? I remember thinking it was a little flimsy at the time.
- rudrigu 10y ago> What's the connection between this solution and string theory? Which string theory? The one in physics or the one in computer science?
- curveship 10y agoI can see how this proves that 20 is possible, but not that 20 is the largest possible, which is what the question asks. How would that be proven?
- JoachimSchipper 10y agoThis is clever! 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.)
- nightcracker 10y agoYou didn't answer the extra credit, how this relates to quantum physics. I'd love to know that.
- curiousgal 10y agoIf someone could ELI5 this, that'd be great!
- allenz 10y agoI just posted my solution: https://news.ycombinator.com/item?id=13694535 https://news.ycombinator.com/item?id=13694535 It's not quite ELI5, but I'd be happy to answer any questions.
- bmohlenhoff 10y ago5400 = 90 min * 60 seconds The test is a list of 23 true/false questions, so you can think of each question as a bit. You've prearranged a list of 5400 unique 23-bit vectors, so he determines the bit vector with the most correct answers (ie. smallest Hamming distance) and leaves at whatever time offset corresponds to that bit pattern. It's not a perfect scheme since you only have 5400 possible bit vectors, and 2^23 > 5400.
- turbohedgehog 10y agoThe table basically says it's possible to pick a set of 4096 (2^12) different vectors of T/F combinations in a way that you only need flip up to 3 (R=3) of the T/F answers to cover all 2^23 (n=23) possible solutions to the quiz. Thus you only need 68 minutes and 16 seconds (4096 seconds) in order to guarantee you get at least 20 answers correct. You can use the remaining 1304 seconds to encode some more vectors to increase the possibility of getting more answers correct, but you cannot guarantee 21 or more correct answers in the allotted time. The lower & upper bound (not sure what this part means) for n=23,R=2 is 30686-32768 about 9 hours! Very simple example with n=3. I have listed all the vectors with Hamming distance of 1 or less (R=1). Looking at the table, we see that for n=3, R=1, we can cover all the vectors with 2 different codes. Heads and tails for example. It's easy to see which combinations we can pick to guarantee coverage, a&h, b&g, c&f, d&e. Using any of those combinations and some way to signal to the other person 'heads' or 'tails' will guarantee they get at least 2 answers correct. a TTT <= TTT TTF TFT FTT b TTF <= TTT TTF TFF FTF c TFT <= TTT TFT TFF FFT d FTT <= TTT FTT FTF FFT e TFF <= TTF TFT TFF FFF f FTF <= TTF FTT FTF FFF g FFT <= TFT FTT FFT FFF h FFF <= TFF FTF FFT FFF
- contravariant 10y agoAlso worth noting that this allows you to allocate the first 21 minutes for your friend to finish the exam.
- optimuspaul 10y agoDoes it?
- contravariant 10y agoSure, if you only need to specify one out of 4096 sets of answers by leaving the room at a certain time (accurate to the second) then you have 5400-4096 = 1304s = 12.7 min of time left over. Which means your friend needs a slightly less superhuman ability to solve string theory problems.