Tag Archives: matching

Matching Tests Proof

Warning, this post uses some fierce math to prove why the pattern continues in the last post. If you want to know why the pattern continues, then welcome to the explanation.

In the last post we counted how many ways to hand student back their tests so that no student had his or her own test. This type of matching has a special name, a derangement. For a group of n students we denote the derangement as

!n

To determine this quantity we need a formula. From before, we know that !3 = 2 and !4 = 9. Now consider the general case. How many ways are there of handing back a test to the first student? We certainly can’t give him his own test. However, we could give him any of the other n – 1 tests. Let’s say we give him test i.

We could hand out the next test to anyone. Let’s consider handing it out to student i (the student with test i). We have two options. First, student i gets student 1’s test. Here is a picture:

pic 1

Once these 2 students have been assigned their tests, we have n – 2 students who still need tests. However, assigned them tests is analogous to our original problem, and we can denote this as !(n – 2).

Second, student i does not get student 1’s test. Thus, student i has 1 forbidden test. All the other students also have 1 forbidden test (namely their own test). Again, this is analogous to our original problem with n – 1 students (since we have not given student i a test yet). We can denote this as !(n – 1).

To summarize, to hand out n tests, we have the following recursive formula:

!n = (n-1)(!(n-1) + !(n-2))

We can use this formula to calculate derangements as high as we like, provided we proceed in order.

!5 = 4(!4 + !3) = 4(9 + 2) = 44

!6 = 5(!5 + !4) = 5(44 + 9) = 265

These are exactly the numerators we found when computing the fractions in the previous post!

To determine what would happen in a large class, we need a closed form for derangements. To simplify the notation for the next section, we will denote !n as D(n).

Observe the following pattern:

D(n)

D(n)-nD(n-1)

D(4) = 9

9 – 4*2 = 1

D(5) = 44

44 – 5*9 = -1

D(6) = 265

265 – 6*44 = 1

D(7) = 1854

1854 – 7*265 = -1

We can prove the above pattern continues using induction. The base case has been dealt with above. Our inductive hypothesis is:

D(n) - nD(n-1) = (-1)^n

Consider n+1:

D(n+1) - (n+1)D(n) = n(D(n)+D(n-1)) - (n+1)D(n) using the recurrence relation

= nD(n) + nD(n-1) - nD(n) - D(n)

= nD(n-1) - D(n)

= -(D(n) - nD(n-1))

= -(-1)^n by the inductive hypothesis

= (-1)^{n+1}

Using this information, we have a new recurrence relation for D(n):

D(n) = nD(n-1) + (-1)^n

Unfortunately, this is still not a closed form solution. However, we will use induction again to get us the rest of the way. The following is the closed form solution for D(n):

D(n)=n!\sum_{k=0}^n\frac{(-1)^k}{k!} = n! \left( \frac{1}{0!} -\frac{1}{1!} +\frac{1}{2!} - \frac{1}{3!} + \dots + \frac{(-1)^n}{n!} \right)

Checking the OEIS, we find that D(0) = 1 and D(1) = 0. Using the formula for D(3), we can see that the base case will hold:

D(3) = 3! \left( \frac{1}{0!} -\frac{1}{1!} +\frac{1}{2!} - \frac{1}{3!} \right)

= 6 \left( 1 -1 + \frac{1}{2} - \frac{1}{6} \right)

= 6 \left(\frac{3}{6} - \frac{1}{6} \right)

= 6 \left(\frac{2}{6} \right)

D(3) = 2 as expected.

Suppose the formula is true for D(n). Consider D(n+1):

D(n+1)= (n+1)D(n) + (-1)^{n+1} from the new recursive formula

= (n+1)n!\sum_{k=0}^n\frac{(-1)^k}{k!} + (-1)^{n+1} using the inductive hypothesis

= (n+1)!\sum_{k=0}^n\frac{(-1)^k}{k!} + (-1)^{n+1} definition of factorial

= (n+1)!\sum_{k=0}^n\frac{(-1)^k}{k!} + (-1)^{n+1} \frac{(n+1)!}{(n+1)!}

= (n+1)! \left[ \sum_{k=0}^n\frac{(-1)^k}{k!} + \frac{(-1)^{n+1}}{(n+1)!} \right]

= (n+1)! \sum_{k=0}^{n+1}\frac{(-1)^k}{k!}

Thus, the formula is true for any n. This formula is closed, but complicated. The last step in the process is to relate derangements to our original problem. Since we were looking for a probability, we were really interested in \frac{D(n)}{n!}. Using the Taylor series approximation for e-1 we get the following:

\frac{D(n)}{n!} = n! \left( \frac{1}{0!} -\frac{1}{1!} +\frac{1}{2!} - \frac{1}{3!} + \dots + \frac{(-1)^n}{n!} \right) \frac{1}{n!}

= \left( \frac{1}{0!} -\frac{1}{1!} +\frac{1}{2!} - \frac{1}{3!} + \dots + \frac{(-1)^n}{n!} \right)

\approx e^{-1}

Finally! We have our answer! Since the number of students determines how many terms of the sequence for e we use, the approximation is valid for even small classes of only 10 or 15 students. The probability of handing out tests properly is approximately e^{-1} = \frac{1}{e} = \frac{1}{2.71828} \approx 37\%

1 Comment

Filed under Uncategorized

Matching Tests

An interesting coincidence happened today in class. My co-teacher was handing the students back their tests. She wanted each student to mark another’s test. However, she accidentally handed a student back her own test. She casually said to me “weird, what are the chances of that?” Her question implied that this was a rare event. The answer is quite the opposite.

My co-teacher had a 63%, or \frac{e-1}{e} to be precise, chance of handing a student back his or her own test. If you are wondering, e stands for a special number:

e = 2.71828…

This percentage is not good. It means that, if you randomly distribute tests to students to mark, about two thirds of the time at least 1 student will end up with his or her own test!

How in the world did I come up with that answer? Let me back up a bit. Suppose we had 3 students and we wanted to give them back their tests to mark so that no student had his or her own test. What options do we have? One option is:

Student A: test B

Student B: test C

Student C: test A

Another option is:

Student A: test C

Student B: test A

Student C: test B

Hence, we have 2 options where we will hand back the tests with no matches. How many options do we have in total?

3! = 3*2*1 = 6

Thus, there is a 2/6 = 33.3% chance that everyone has a different test. In other words, there is a 66.6% chance that at least one student receives his or her own test to mark (which would not be good for academic standards).

What if we had 4 students? You can do the math, and you will find that there are 9 options where the students have different tests. For example:

Student A: test B

Student B: test C

Student C: test D

Student D: test A

Again, basic counting principles dictate that there will be 4! = 24 different possible combinations. Hence, there is a 9/24 = 38% chance each student will have a proper test to mark. We could continue on like this; painstakingly grinding out the probabilities for each situation until we reached a class size of 25. However, there is a pattern we can exploit. Consider the following table:

Number of Students

Fraction of proper distributions

3

2/6 = 33%

4

9/24 = 38%

5

44/120 = 37%

6

265/720 = 37%

7

1854/5040 = 37%

8

14833/40320 = 37%

Do you see the pattern? Once the class size gets to 5, the percentage becomes stable. Based on the above data, we could predict that a class of 25 students will have roughly the same percentage, 37%. Indeed, one can prove mathematically that this percentage will be true for any size class, large or small.1 Thus, my advice to teachers is as follows. Be careful distributing tests to students to mark. You are playing a game with a 37% chance of winning. And any gambler knows, those are not good odds.

 

1See next blog post.

1 Comment

Filed under Uncategorized