Hacker News Reader

Comment by asrp | Hacker News Reader

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

Edit: formatting

View on HN

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.

I 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.

I 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?

This 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

I 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.)

This 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.)

> What's the connection between this solution and string theory?

Which string theory? The one in physics or the one in computer science?

If someone could ELI5 this, that'd be great!

My take on this:

The naive approach (which is what I did) is to assign each second to a binary number and work out how high the number goes - this works out at 2^12.

The clever way other people did - and which I've been thinking about all morning, is:

The complete answer to the test is a set of true/false answers that we map to 23-bit vectors.

We know that there 2^23 vectors, which is way more than the 90*60=5400 ways we have to identify each of them.

Pretty sure we're all clear on that.

The hard part comes when we start saying that we can let some of the bits be wrong. This lets us say that some of the 2^23 23-bit vectors are pretty much the same as some others. I think of it like grouping vectors together into groups that are all related to each other by flipping up to 3 bits.

So let's take an example with 4-bit vectors instead because I find it more intuitive. This is a test with 4 true/false answers. Our naive method would make us think we need 2^4=16 seconds to correctly identify true/false answers. But if we look at what happens when we say one of those answers can be wrong, it gets interesting. Let's look at the first 4-bit vector:

  [0 0 0 0]

Now we can let any bit be wrong:

...and we have FIVE possible vectors identified by the SAME second. Just by looking at the first vector we've reduced our space from 2^16 to 2^16-5. And remember we can group all of our 4-bit vectors together like this.

If you let 2 answers be wrong you have larger, fewer groups.

If you let 3 answers be wrong you only need one bit of information! Your cheating friend gets up on second 1 or second 2.

This is my intuitive way of looking at it anyway. For the actual maths and such look at other answers...

This line:

Just by looking at the first vector we've reduced our space from 2^16 to 2^16-5.

Should be:

Just by looking at the first vector we've reduced our space from 2^4 to 2^4-5.

Can't edit it now - sorry if that confused anyone.

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 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

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.

Interestingly this just came across in my YT feed :)

https://www.youtube.com/watch?v=1_X-7BgHbE0

5400 = 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.

The game is you're trying to guess a long word 23 letters long and your buddy can only tell you a number below 10K, although you are allowed to share dictionaries...

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.

I think this attempt is closest to the "five years old" level:

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.

I just posted my solution: https://news.ycombinator.com/item?id=13694535

It's not quite ELI5, but I'd be happy to answer any questions.

I'm not sure if you're looking for an ELI5 of the question or the answer. I'll explain the answer since others already explained the question.

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)

is still two small. So there are bound to be sets of true answers where you'll get more questions wrong.

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)

(which is now bigger than 2^23) because that's only an upper bound. Each second from 0 to 2399 "covers"

    1 + 23 + 23 * 22 / 2 + 23 * 22 * 21 / (2 * 3)

set of true answers (so if those are the true answers to the test, your scheme works). But if for some set of true answers is covered by more than one of the seconds (it happens when there are two different times at which your friend can leave and give you at most 3 answers wrong), it means that some other set of true answers might not be uncovered.

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.)

Also worth noting that this allows you to allocate the first 21 minutes for your friend to finish the exam.

Does it?

Sure, 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.

You didn't answer the extra credit, how this relates to quantum physics. I'd love to know that.

Reply on news.ycombinator.com