Don't Get Caught by Professor Hadamard [Solution]

Solution for the week of 4/6

Last week we were introduced to Professor Hadamard who

[…] recently administered a four-question, True/False math test to his class of four students. Given the challenging nature of his exams, he's had issues with cheating in the past. To combat this, he developed a program that analyzes students' answers by comparing them pairwise. The program counts the number of identical and differing answers between each pair of tests. If a pair has an unusually high number of matching answers, it triggers further scrutiny.​

Upon running the students' tests through his program, Professor Hadamard stumbled upon a remarkable finding:​ Every pair of tests had exactly two answers in common and two that differed.​

Intrigued, the professor pondered the likelihood of this occurrence. Assuming each of the four students answered all four True/False questions randomly, what is the probability that every pair of students' tests would exhibit exactly two matching and two differing answers?​

If Professor Hadamard's class had six students and the test comprised six True/False questions, what’s the probability each pair would have 3 matching and 3 differing answers?​ More generally, for N students each answering N True/False questions randomly, what is the probability that every pair of students' tests would have exactly N/2 matching answers and N/2 differing answers?

We didn’t have any solution submissions this week which is probably my fault. Turns out deriving the general case with N=4M students and N=4M questions is quite challenging. I certainly wasn’t able to do it myself and instead relied on the literature to find a solution. However, determining the probability when there are 4 student and 6 students was much more manageable. In this post I’ll only present those solutions and omit the general solution. Links to the proof of the general solution are provided for those interested and courageous readers.

Let’s begin!

N=2

To get started, let’s begin with a simpler case where there are 2 student taking a 2 question exam. For the first student, it doesn’t really matter what answers they had so long as the other student has one answer that’s the same and one answer that’s different. So there are 2^2=4 possible test answer the first student could have had. The second student now needs one of their answers to match and one to differ. They can effectively choose one of them to be the same. There are (2 choose 1)=2 ways to do this. So overall there are 4*2=8 different configurations that satisfy our condition.

NOTE: From here on out, I will use the term pairwise orthogonal to refer the the feature where each pair of the N tests with N True/False questions has exactly N/2 answers that match and N/2 answers that differ.

Since there are 2^(2*2)=16 different possible ways the 2 students could have answered their tests, the probability is 8/16=50%

N=4

Ok, that was easy enough. Now let’s try 4.

Here again, we’ll build up the number of pairwise orthogonal configurations student-by-student. There’s no restriction on the first student so there are 2^4=16 different possible test results. For the second student, two of the 4 answer need to be different so there are (4 choose 2)=6 different sets of answer that work.

But 3 is where things get a little trickier. Now we need to determine how many possible test answers satisfy being orthogonal to both the first student and the second student. Let’s assume the first student had answers (a,b,c,d) and the second student had answers (~a,~b,c,d) where

\(a,b,c,d \in \{ -1,1 \}\)

We use -1 as the ‘False’ binary indicator here instead of the traditional 0 because it will make the subsequent orthogonality calculations more intuitive.

If we call the third student’s answers e, f, g, and h then we need the dot product of first and third’s answers to equal zero as well as the dot product of the second and third’s answers to equal zero.

\(\begin{align*} s_1 \cdot s_3 &= 0 = a \cdot e + b \cdot f + c \cdot g + d \cdot h \\ s_2 \cdot s_3 &= 0 = -a \cdot e + -b \cdot f + c \cdot g + d \cdot h \end{align*}\)

If we add these two equations together we get

\(0 = cg + dh\)

Since c and d are already fixed, let’s just say they are both 1 without loss of generality (we can easily apply the same reasoning regardless of what values we would have selected for c and d).

\(0=g+h \)

Obviously, there are only 2 ways to select g and h that satisfy this equation. If we now substitute this back into either one of our original equations and again assume a, b = 1, we get

\(0 = e + f\)

Again, there are 2 ways to select e and f that satisfy this equation. So overall, there are 2*2=4 ways to select the third student’s answers. Ok, not too bad, but we’re not done. We still have the 4th student.

This isn’t as had as you may think if we recall some important facts from linear algebra. Recall that we want 4 pairwise orthogonal answers. You’ve probably already noticed it, but these test answers can be thought of as vectors. In the examples above, we’ve been taking the dot product of these vectors and setting them equal to 0, meaning they’re orthogonal (which is precisely why I use the term ‘pairwise orthogonal’).

With that in mind, we’ll note that we want to count the number of orthogonal bases in 4 dimensions and that we’ve just counted the number of different ways of configuring the first 3 vectors. Now we need the 4th. But once the first 3 orthogonal vectors have been selected, the 4th is completely determined. The only degree of freedom is whether the 4th orthogonal vector will be oriented in the ‘positive’ or negative direction (if let v₄ be the 4th orthogonal vector, we can choose to use v₄ or -v₄). So there are only 2 options available to use for the 4th student.

So pulling everything together we have 16*6*4*2=768 different test answers that are pairwise orthogonal giving us a solution of 768/2^16=1.17%

But wait! Astute readers will notice that the problem we just solved is basically the same as counting the number of Hadamard matrices—giving us the name of our eponymous professor. But in OEIS, the answer is 384. What gives?

Well, if we have a Hadamard matrix H, most treatments wouldn’t consider H and -H to be distinct matrices as we did in our problem. To account for this we would divide our answer by 2 giving us 768/2=384. So all is right in the world after all.

N=6

Now what about N=6? Well, this is actually pretty easy to solve and the answer is 0%. To see this, we will prove that there are no Hadamard matrices when N isn’t divisible by 4 (excluding the case when N=2).

Without loss of generality, let’s assume that first row is all 1s. Then every other row must contain N/2 1s and N/2 -1s. Now let’s consider two different rows i and j, neither of which is the first row. Of course, these two rows will also have N/2 entries that agree and N/2 entries that disagree. Let’s focus on the columns where they agree. Some number x of these will have entries that are +1 while the other y are -1. We know

\(x+y=\frac{N}{2}\)

Moving our attention to a specific row (say i), we know it must have N/2 1s. We just identified x spots with 1s (locations where the two non-first rows agreed) and the rest come from spots where the two rows disagree. Let’s let b be the number of 1s in row i in columns that disagree with j. So we have

\(x +b=\frac{N}{2}\)

Row j also has N/2 disagreement columns and since the values in those columns are the opposite of row i, there are N/2-b 1s coming from the disagreement column for row j.

\(\frac{N}{2} = x + \frac{N}{2} - b\)

solving for x and b in these equations, we get x=b=N/4. But this can only be valid when N is divisible by 4. So in order to satisfy piecewise orthogonality when N>2, N must be divisible by 4.

For Any N

As I alluded to before, deriving the general form for N=4*M is actually quite involved. Here is a link to a proof. Even writing out the actual expression for the number matrices is long and not very informative so I will omit it. However, like most proofs, it’s interesting once you take the time to understand what the hell is going on :)

---

Other Thoughts

As the foreword of my puzzle posts says, the inspiration for X’s Puzzle Corner comes directly from

Zach Wissner-Gross

’ The Fiddler on the Proof. I’m preaching to the choir since most of your are here because of the generous shoutouts Zach has sent my way, but I’ve been a big fan for a while. The guy puts out straight bangers every week. He’s a goddam machine. But now that I’ve been writing my own for the past few months, I have a new appreciation for the work he does. It takes considerable time to write fun puzzles! And god knows Zach’s write-ups are much more comprehensive than my own—not to mention he probably solves the problem before posting it :)

So why am I writing this? I guess its to say “Thanks Zach!” The Riddler and Fiddler ended up giving my a lovely hobby that I almost certainly wouldn’t have discovered if not for all of Zach’s hard work. And with that said, go to the Fiddler, work on the problem, and for the love of God, submit your solution! All of this is so much more fun when you do!