Always Blame the Autograder
Puzzle for the week of 4/13
Inspired by the Fiddler on the Proof (formerly The Riddler), X’s Puzzle Corner aims to produce a weekly puzzle for readers that enjoy math, probability, and algorithms. Please submit your solution! Solutions will be accepted until 11 pm the following Sunday after the puzzle is posted (in this case 4/20/25). While it isn’t required, I encourage you to opt to have your solution shared so that we all get the chance to see how others thought about and attempted the problem! The solution and submitted responses will be posted around Wednesday at 10 am.
I make no guarantees my solutions are correct! You are all smart people so please comment if you think I made a mistake!
Last week we introduced Professor Hadamard and the remarkable outcome of one of his exams. Recall that the professor gave out a 4-question True/False test to his 4 students and something curious emerged: for every possible pair of students, exactly two of their answers matched and two differed—a property we'll refer to as pairwise orthogonality. The result was so striking that Professor Hadamard began to suspect a bug in his automated answer-checking system.
While reviewing the code, he discovered a flaw: the part of the program that determined whether a student had answered “True” or “False” was occasionally incorrect. Specifically, it had a 10% chance of flipping each answer—so if a student marked “True,” the system would incorrectly record it as “False” with probability 0.1, and vice versa. Upon realizing this, Professor Hadamard decided to go back and check the tests by hand. He confirmed that the students’ actual answers were indeed pairwise orthogonal—just as the system had reported, despite the flaw. To be clear, he did not check whether each individual answer had been read correctly—only whether the actual test results were pairwise orthogonal.
The question for this week is how likely was was this?
In other words, if we have assume that the actual student test answer are pairwise orthogonal, and that the the test scoring program has a 10% chance of flipping an answer, what is the probability that program would also believe that the students’ test answers were pairwise orthogonal?
Now what about if the there had been an 8 students taking an 8 question true-false test? And what if there had been 4N students taking a 4N-question test?
Please submit your answers here. Please ask any questions in the comments.