Hacker News Reader

Comment by steventhedev | Hacker News Reader

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 cases that you should focus on to solve this are those where the number of true/false is almost equal. Figure out how to pack them together, layer a few solutions together, and you should be able to answer the exam to within some N guaranteed.

EDIT: 12 correct answers. not 13. And you can easily pack this into 1 bit. Leaving my wrong answer for posterity.

View on HN

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.

Doesn't your method only guarantee 12 answers -- half of 23 (rounded up)?

That can be reduced to a single bit:

If you should mark 'true' on all the answers, he leaves during the first half of the exam; if you should mark 'false' on all the answers, he leaves during the second part of the exam. This gets you at least 12 correct answers in 1 bit.

This leaves you with 11 bits to modify the pattern with to improve your score.

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

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.

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

I wrote a simple program to test all possible majority-of-group breakdowns for generic number of questions and bitlengths, and found that the optimal result in all cases for this class was to use all but one bit for individual questions and then use that one bit for majority of the rest.

You can probably get better bit usage by doing some sort of more complex error code correction scheme--imagine having overlapping groups that you know majority vote on. It's been a decade since I've touched that stuff, so I don't know any concrete numbers here.

The problem states that the friend can only walk out of the room once though...

Reply on news.ycombinator.com