Cheating on a string theory exam

"a fraction of the time" isn't a very clear problem statement, as 9999999/1000000 is a fraction, but that's certainly not what is meant by the common sense understanding of this phrase.

I am wondering what we can do without clarifying the statement further.

We can still encode 90*60 23-bit vectors and have the friend pick the one, in the remaining time after he finishes, that minimizes the distance to the true answer, but without knowing how early he finishes. That is probably still the way you can get the best score on average, but I don't think it does better for the guaranteed number of correct answers than just transmitting 1 bit of information (which guarantees at least 12 correct answers).

Would it help to use odd vs even seconds to indicate whether the fiend finished early enough to use the clock to indicate an arbitrary time vs the time at which he should have left was already gone when he finished his exam? I can't think of how to use this (or a similar) signaling to improve the worse case odds.

On the other hand, while I cannot think of a way to improve your worse case situation, you should be able to improve average score by sorting your 5400 23-bit vectors so that the distances between the last ones are as large as possible.

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 visual interpretation: we're searching for a way to partition the hypercube of 23-bit strings into 2^12 balls[2] containing 2^11 elements each.

What is the minimum radius of the balls? There is 1 element in the center of the ball, 23C1=23 elements at distance 1, 23C2=253 elements at distance 2, and 23C3=1771 at distance 3, which sums to precisely 2^11. This combinatorial coincidence makes it possible to build a beautifully symmetric 23->12 compression function!

In order to avoid overlap, the centers of any two balls must be 7 bits apart. One idea to evenly space the centers: write all possible first 12 bits (1 bit distance), then distribute the remaining bits 6 bits apart.

We can also see that inverting the compression function gives an error-correcting code going 12->23, mapping 12-bit inputs to optimally-spaced 23-bit strings. There is a duality between lossy compression (aka rate-distortion theory[3]) and error correction.

As it turns out, the optimal 12->23 error-correcting code is the perfect binary Golay code discovered in 1949.[4] The inverse of the Golay code is the compression function we're looking for.

A bit of historical trivia: Golay's 1949 paper was reviewed by Berlekamp, who in 1974 called it the "best single published page" in coding theory. At the time, Berlekamp was working as a code breaker with Jim Simons at the Institute for Defense Analyses. Later, Berlekamp would help Simons found Renaissance Technologies, which remains today the most successful quant hedge fund in history.[6] Renaissance was famous, of course, for hiring many of the best minds in string theory.

[1] https://en.wikipedia.org/wiki/Hamming_distance

[2] https://en.wikipedia.org/wiki/Ball_(mathematics)

[3] https://en.wikipedia.org/wiki/Rate%E2%80%93distortion_theory

[4] https://en.wikipedia.org/wiki/Binary_Golay_code

[5] https://en.wikipedia.org/wiki/Hamming_bound

[6] https://en.wikipedia.org/wiki/More_Money_Than_God

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.

Of course, it's banned here but the simplest thing (for the person taking the test) would be to take a short amount of time - or a long amount of time - to fill in each bubble. A short scribble = false, a long scribble = true. To thwart the proctors you could swap the keys every other question, such that for question 1 short=false, long=true; question 2 short=true, long=false, etc etc.

Of course, for any of these answers the proctors could trivially catch you cheating. The best way to prevent this would be applying a simple one-time pad to them - exchange a small number beforehand and use that.