Earlier quoted context omitted.
The 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 in…
This is still an ELI21 at least :) ELI5-s should use cars cookies or candies to explain :)
Cheating on a string theory exam
51–60 of 76 posts
Re: Cheating on a string theory exam
#52Pick 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…
Also worth noting that this allows you to allocate the first 21 minutes for your friend to finish the exam.
Re: Cheating on a string theory exam
#53Step 1: 10 bits information - First 10 answers as seconds from start of exam. After x seconds, friend goes to toilet.
Step 2: Restart counter
Step 3: On return from the toilet, take time taken in toilet. You may want to limit this to 6 bits of information / ~ 1 minute in the toilet. Anything longer might be suspicious.
Step 4: Restart counter
Step 5: Only 7 bits of information to hand over to get 23 questions. Count time till he leaves.
Step 6: Repeat toilet-going process for more answers in different situations.
There should be no suspicions, as the answer-receiver will not go to the toilet.
Do not drink tea when attempting this method.
Re: Cheating on a string theory exam
#54Pick 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!
So you have 23 questions, and on each you can either answer yes or no. You goal is that your friend "transmits" you some information so that you get the most of the answers right. As the problem is set up, what he can transmit to you is just an exact second of a 90 minutes span, that is one number between 0 and 5399.
Having 23 questions, every with 0 or 1, gives 23 bits of information to pass. 4096 is 2 to 12 th power, so the friend can pass you only 12 complete bits.
Now the major point: you're lucky that you don't care which answers exactly you get right. You need 23 bits passed to get the exact 100% right solution. But you don't care. It turns out, if you cleverly write on the paper 4096 different "solutions" before the test and your friend transmits you which one of these 4096 you should take to fill out the form, the mentioned cleverness can guarantee you that you get N answers right, you just don't know which specifically in advance and you don't care as you prepare these 4096 solutions. The friend must also know the same table, and has to select one of the prepared 4096 solutions only once he discovers what the "100%" solution is.
The remaining question was how many answers you can be sure you can get right (N), and it turns out, N is 20.
Why? If you carefully construct each of these 4096 solutions to be "as different" from all the other 4095 solutions as possible, it can be proven that then 20 is the result.
So you have to take to the test a list with 4096 longer binary numbers, carefully prepared, your fried can transmit you which one to write through the time of his leaving of the test, and you'll have 20 answers right. Or you can train yourself to perform a special algorithm to produce a pattern of 23 answers from the time and the friend to do the opposite.
The math details are, thanks to allenz, here (not on "five years old" level): https://en.wikipedia.org/wiki/Binary_Golay_code There are also some algorithms. The 20 in the solution can be figured out from the sentence "G23 is a perfect code. That is, the spheres of radius three around code words form a partition of the vector space." Which for our task means that not more than 3 answers will be "wrong" from 23 answers known to your friend, if the whole trick is performed correctly, therefore 23-3=20.
And of course, this kind of cleverness (but used for error correction, that is, to allow sending more data than minimally necessary, but where some of the data is lost before it reaches the other side and everything still works) is actually built-in in the modern communication and data storage equipment, but we, typically, just reap the benefits and don't think of it.
On another side, human languages also evolved to contain redundancies, so the evolution is very capable to find the acceptable solutions for the message encoding too.
--
1) This way you haven't used all 5400 possible values, but now your can split the remaining thousand-something seconds between you and your friend, for him to prepare the transmission, and for you to fill the form after you received the code but before the test is over.
Re: Cheating on a string theory exam
#55Earlier quoted context omitted.
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?
Sadly, 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.
Re: Cheating on a string theory exam
#56Earlier quoted context omitted.
Also worth noting that this allows you to allocate the first 21 minutes for your friend to finish the exam.
Does it?
Re: Cheating on a string theory exam
#57https://en.wikipedia.org/wiki/Leech_lattice https://en.wikipedia.org/wiki/Monstrous_moonshine http://motls.blogspot.com/2015/03/umbral-moonshine-and-golay...
Re: Cheating on a string theory exam
#58This makes it easy mode: friend takes 10 minutes to read test and get answers in his head, start the timer (0 seconds) at the 10 minute mark. Friend "starts" sometime in the next 34 minutes. 34 minutes is 2048 seconds or 11 bits of info. Then "finishes" between 44 minutes and 78 minutes: another 34 minute window and another 11 bits of info. 22 of 23 questions answered. Friend coughs on way out if last answer is true. Boom, all questions answered.
Yes, OP said we can't do this, but it is more practical than memorizing 5400 bit vectors, doesn't assume the friend can instantly finish the test, gives the friend some lead time to actually do some binary conversions, and ensure the correct times down to the second.
Re: Cheating on a string theory exam
#59Getting 12 out of 23 should get him the average on the lucky assumption the teacher was not a joker that put all answers higher than bit 6 to false ...