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

11–20 of 76 posts

Re: Cheating on a string theory exam

#11

Post by mattb314 »

steventhedev wrote: post #5

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…

You can actually transmit this information in a single bit: just have your friend send a 0 if you should answer false on everything or 1 if you should answer true on everything. To use the other 11 bits, transmit the first 11 answers first, and then encode whether to guess true or false on all of the remaining 12 questions in the last bit. This method gives 11 + (23-11)/2 = 17 answers correct in the worst case, but (according to the author) this is still suboptimal.

Re: Cheating on a string theory exam

#12

Post by szemet »

SomeStupidPoint wrote: post #10
szemet wrote: post #8

Earlier quoted context omitted.

Using this on only 3 questions, you get 2/3 success rate: 000,001,010,100,000 -> buddy signals 0, I write 000 111,110,101,011,111 -> buddy signals 1, I write 111 with 7 bit you definitely win 14 questions from 21

You can get at least 17 by using the 1 bit to express preference for just the first 12 questions, and the remaining 11 bits the answers to the last 11 questions exactly. I've been trying to think if there's a clever scheme to spread the knowledge around to beat 17 with statistical tricks. (As a fun aside: 17/23 is about 73%, which typically gets you a C -- so you'd pass the exam.)

6 bit to win 12 question from the first 18 (group by 3) 5 bit for the remaining 5

17 answer and one bit remained

Re: Cheating on a string theory exam

#13

Post by rinovan »

I would say that the lower bound is 18.

Because we want to represent a 23 bits string by 12 bits codewords, the max distance between 2 codewords is 11 bits.

So the protocol would be to agree on a dictionary of 12 bits codewords and send the closest codeword to the actual answer.

The max hamming distance between any answers and a codeword would be floor(11/2) = 5. Which corresponds to 18 correctly answered questions.

Re: Cheating on a string theory exam

#14

Post by yakult »

cperciva wrote: post #3
pizza wrote: post #2

My attempt: - need 23 bit string to fill 23 yes/no answers - the test is 90min * 60sec/min = 5400 sec - log2 5400 time-indexes = ~13 bit time-address capability 23 bits required - 13 bits given = 10 bits that are unavailable. You can answer 13 questions.

I rephrased the question slightly for clarity after you posted this: You're looking for the largest value N such that you can guarantee that you get at least N questions correct. Since log(5400)/log(2) is only ~12.3987, your approach only counts as 12 correct answers. (You can do better.)

We can start with the prior that there will probably be a similar number of trues and falses. We are mapping 23 bits of state into 12 bits, we can leave out those states where T>>F or vice versa. If the test turns out to be one of those unexpected states, pick the answer that gives the best score.

Edit: Rereading, it looks like we're optimizing the worst case, rather than average. So we're looking for a 12:23 map where at most n bits are inaccurate, minimizing n. I'm sure there's a signals alg that does this...

Re: Cheating on a string theory exam

#15

Post by SomeStupidPoint »

szemet wrote: post #12
SomeStupidPoint wrote: post #10

Earlier quoted context omitted.

You can get at least 17 by using the 1 bit to express preference for just the first 12 questions, and the remaining 11 bits the answers to the last 11 questions exactly. I've been trying to think if there's a clever scheme to spread the knowledge around to beat 17 with statistical tricks. (As a fun aside: 17/23 is about 73%, which typically gets you a C -- so you'd pass the exam.)

6 bit to win 12 question from the first 18 (group by 3) 5 bit for the remaining 5 17 answer and one bit remained

Which answer do you use the extra bit on that's guaranteed to give you one more correct?

For any you choose, there are answer patterns where you already counted that answer being correct in your guaranteed number as part of the 2/3rds correct.

So I don't think you can (trivially) use that bit to guarantee another correct answer.

Re: Cheating on a string theory exam

#16

Post by wnoise »

log_2 of 60*90 is about 12.4. This shows that a naive scheme would expect to get about 12.4 + (23 - 12.4)/2 = 17.7 questions right. I would be very skeptical about any scheme that purports to guarantee better than this. A reasonable approach would be trade the possibility of doing better than this with the possibility of doing worse.

In fact, I can guarantee 17 correct questions, with only 11 bits which has the same floor for expected value (11 + (12/2) = 17):

Divide the first 18 questions into 6 groups of three. Use the first 6 bits of time to indicate the majority in each group of three, giving you 12 guaranteed answers. The last 5 questions can be encoded directly.

It seems like there should be room for improvement, as this does very well on each group in the 1/4 time that each is uniform. I also worry that the average here is 12 + 1.5 + 5 > 17.7.

Perhaps overlapping the groups could help, which starts to look like an LDPC code, but with max, rather than parity. The difficulty is that overlapping bits can no longer guarantee more, because the previous ones could have already done so.

Re: Cheating on a string theory exam

#17

Post by jcranmer »

szemet wrote: post #12
SomeStupidPoint wrote: post #10

Earlier quoted context omitted.

You can get at least 17 by using the 1 bit to express preference for just the first 12 questions, and the remaining 11 bits the answers to the last 11 questions exactly. I've been trying to think if there's a clever scheme to spread the knowledge around to beat 17 with statistical tricks. (As a fun aside: 17/23 is about 73%, which typically gets you a C -- so you'd pass the exam.)

6 bit to win 12 question from the first 18 (group by 3) 5 bit for the remaining 5 17 answer and one bit remained

The last bit for the extra answer doesn't guarantee you an extra point in all cases.

Re: Cheating on a string theory exam

#18

Post by asrp »

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 http://www.sztaki.hu/~keri/codes/2_tables.pdf

Edit: formatting

Post reply on HN