Cheating on a test
You’ve spent a long semester in Linear Algebra, understanding nothing, doing horribly on tests, and hating your teacher. It’s final time, and if you don’t do well on the final, you’re gonna fail the class and get das boot from your Mechanical Engineering major. Luckily, though, you have a friend who is a linear algebra god, and you’re going to use your ingenuity not to study, but to craft the perfect plan to cheat on the test.
Here’s what you know:
- The test is 23 multiple choice questions (all true/false)
- Your friend is a linear algebra genius and can finish the test in literally a span of seconds.
- You have 1.5 hours to take the test, and while there is no way for you to communicate with your friend, you have a stopwatch and can measure precisely when your friend stands up to turn in the test. Your stopwatch is accurate to the second.
Given this, what is the maximum number of questions you can guarantee you will get right?
(Spend some time thinking about this — it’s a fun problem, and I don’t want to spoil the answer before you think about it).
The Naive Solution
Let’s start with the basics. The test is 1.5 hours long, which means there are 5400 seconds. Your friend can therefore leave any time between 0 seconds and 5400 seconds, and you can measure this with your stop watch.
The solution space of this problem is a 23-bit binary number (a true or false answer for every single test question). Meanwhile, 2¹² < 5400 < 2¹³, and so our friend can use the time he stands up to represent any binary number between 0 and 2¹². (For instance, getting up at 0 seconds would represent the binary number 000000000000, which would indicate 12 “falses”, where getting up at 2¹² seconds would indicate 111111111111, which would indicate 12 “trues”).
As a result, our naive solution could be as follows:
- Our friend gets up at some time between 0 and 2¹² seconds.
- We convert the time he gets up into a 12-digit binary number
- We answer the first 12 questions on our test based on the 12 digit number our friend just told us (and since our friend is a genius, we know those first 12 answers are right).
This would guarentee we get 12 questions right, and if we guess on the remainder, we could get an expected value of 12 + (23–12)*.5=17.5. Not bad!
The Naive Solution — Part 2
Okay, so maybe you got the naive solution, but we can do better :).
We know our friend can only convey 12 bits of information to us (since the time limit of the test only permits up to 12 bits of time). So, how can we convey “more” guaranteed answers in those 12 bits? Well, one way is to group the questions.
What if we treated the first 11 bits as the answers to the first 11 questions, and the 12th bit as the answer that is most common in the remaining 22 questions? As an example, if my friend left at a time corresponding to the binary 111111111110, then I would answer true for the first 11 questions, and false for all of the remaining questions.
This would guarantee I get the first 11 questions right, plus AT LEAST half of the remaining questions right (since the 12th bit represents the most common answer in the remaining questions). This gives us a guaranteed 11+(23–11)*.5 = 17 answers correct.
Getting Fancier
17 is pretty good (17/23 is a C-, Brian would probably have been okay with that in linear assuming no studying). But, can we do better?
To start, let’s consider a much simpler case. What if I wanted to send you the answers to a test with just 3 true-false questions, but I only had one bit?
An approach I could take is to try to “reduce” the 3 dimensional answer space by grouping the 3 dimensional space into values that are within some edit distance of each other. This is a little confusing, so let me try to explain more:
Normally, the possible 3 dimension answers are: 000, 001, 010, 011, 100, 101, 110, and 111. There are 2³ = 8 such values.
Now, what if I decided that I would “group” these values into groups where every value in a group is just 1 bit away from any other value in the group? For instance, let group 1 be all values within 1 bit of 000, and let group 2 be all values within 1 bit of 111. Then:
Group 1: 000, 001, 010, 100
Group 2: 111, 101, 110, 011
Note that I can now represent this 3 dimensional answer space to you with just 1 bit: group 1, or group 2. So, let’s say I want to tell you the answers to a 3 answer true-false test, but I can only send you 1 bit of information. I would determine what group the answer to the test is a part of, and then I would tell you the group that corresponds to that answer.
While you would not be guaranteed to get all 3 answers right, you would be guaranteed to get AT LEAST 2 answers right, since every answer in a group is at most 1 bit away from the group’s basis (000 or 111).
For instance, say the true answer to the test is True-False-True (aka 101). I would determine that 101 is part of group 2, and so I would send you the bit that corresponds to group 2. Since i told you group 2, you would just write 111 (or true true true) for the test, knowing you are guaranteed to get at LEAST 2 answers right (since, no matter what answer was the real answer, if that answer was in group 2, it was at most 1 bit different from 111).
How does this answer the original question?
Okay, so even if you didn’t follow the above example, understand the following key idea
If I need to represent a solution space of size X, but I only have K < X bits, I can group the solution space into related answers, such that answers in each group are guaranteed to only be so different from each other.
Above, I showed you an example where I had a solution space of 3 bits, but could only communicate K=1 bit, and so I grouped the solution space into 2 groups of answers no more than 1 bit different from each other. By doing this, I could send you 1 bit of information (group 1 or group 2), and represent FOUR different values with that 1 bit.
We can generalize this strategy to MUCH larger problems, such as needing to represent 23 bits of solutions into 12 bits of information (the problem at hand).
It turns out (through some fancy math) that you can partition a 23 bit solution space into 2¹² values, where each answer represents solutions that are no more than 3 bits different from each other. This implies that your friend can get up at some second which will give you some answer that is no more than 3 bits away from the true solution, ensuring you get at least 20 answers correct.
So, by coasting with a stop watch, you can get a 20/23 on your final :) Confused because I didn’t explain well? Check out the below sources for additional explanations:
