Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Cheating on a string theory exam

daemonology.net

Post reply on HN
Print view View original

41–50 of 76 posts

Re: Cheating on a string theory exam

#42

Post by kowdermeister »

turbohedgehog wrote: post #38
curiousgal wrote: post #30

Earlier quoted context omitted.

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

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

Re: Cheating on a string theory exam

#43

Post by botexpert »

Similar to the lottery problem and other covering problems.

Let's say lottery has N numbers. Tickets contain K numbers. What is the least amount of tickets M that you need to buy so you guarantee when the winning ticket is pulled that you matched at least R numbers on that winning ticket with your pool of tickets? LP(N, K, R) = M.

LP(N, K, K) = (N choose K), is winning the lottery and for that to be sure we need to buy all tickets.

LP(N, K, 2) is solved, I believe, for many values (theoretically).

LP(N, K, 3) is already a problem.

Re: Cheating on a string theory exam

#44

Post by curveship »

cperciva wrote: post #23
asrp wrote: post #18

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?

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?

Re: Cheating on a string theory exam

#45

Post by xfs »

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

Re: Cheating on a string theory exam

#46

Post by kowdermeister »

allenz wrote: post #33

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…

Thanks for the clearest (and still mysterious) explanation so far in this thread.

Re: Cheating on a string theory exam

#48

Post by mwielbut »

allenz wrote: post #33

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…

*bits of information in 5400 seconds (not min)

Re: Cheating on a string theory exam

#49

Post by mrkgnao »

xfs wrote: post #45

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.

Re: Cheating on a string theory exam

#50

Post by philbarr »

curiousgal wrote: post #30
asrp wrote: post #18

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!

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:

  [0 0 0 0]
  [0 0 0 1]
  [0 0 1 0]
  [0 1 0 0]
  [1 0 0 0]
...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...

Post reply on HN