TestTubeGames Forums

I came across an interesting math question this weekend -- which seemed like it should be tremendously easy -- but so far we haven't quite been able to crack it.

You have a class of n students, and you're handing back their exams. The twist is, you do so randomly. What is the chance that *at least one student* will get his/her paper back?

The first few cases are easy. With 1 student, there's a 100% chance they'll get the right paper. With 2 students, there's a 50% chance at least one will get the right paper (since the two options are: they either both get their papers, or they both get the wrong paper). And so on.

Try out the case of three students, or four. A brute force method can work, but it'll get overwhelming with just a few more students. And, I suppose a computer program could keep on brute-forcing it... but I'm interested in something more elegant. We've been looking for a general equation for the answer over here (so that we could easily find the probabilities for the n=10 case, for instance). We're getting close, but it's been pretty challenging. I thought you all might enjoy taking a crack at this (and of course, no googling the answer!)

So, to start us off and make sure we're on the right track, what is the answer when n=3? n=4?

Alright, I'll take a try at this.
So this should be easy. First, we start with the odds that, giving 1 test, it will hit the wrong person. This appears to be (n-1)/n. So let's see.
If I hand it to 1 student, it'll have a 0/1 or 0% chance of not hitting the right person.
2 students, 1/2 or 50%
3 students, 2/3 or 66.(6)%

So this checks out so far.

Now, after we do this, we do it again and subtract n by 1. Then we repeat the process until n = 1. At n = 1 we stop.

So, let's try:
n = 1
1 = 100%

n = 2
1/2 = 50%

n = 3
1/2 * 2/3 = 2/6 = 1/3 = 33.(3)%

n = 4
1/2 * 2/3 * 3/4 = 6/24 = 1/4 = 25%

I compared my results with a "brute force" attack I tried for myself, but at n = 4 it equaled 37.5% which isn't the results this tells us. I double and even triple checked, so this doesn't check out. However, the way I did it gave me an idea.

I did my brute force attack like this:
On top I had n numbers. Like, 12
Then below, I placed every combination of letters up to the equivalent of n. So in this case I'd have:

12
AB-
BA

I then marked the ones where at least 1 student had the right test with a - as you could see.
Anyway, what I noticed was, if I split this into, say, groups where A was on a certain column, I would get this pattern. let me add 1 so you can see this:

123
ABC-
ACB-

BAC-
CAB

BCA
CBA-

Did you see the pattern? The first one had all with at least 1 correct, while the other two had 1 each. Add another iteration, and the first group has all right, and the rest all have three. Out of six occasions per group. So this appears to be split in half.
So for n = 3 we have 2 + 1 + 1 scenarios where at least 1 student gets it right. For n = 4 we have 6 + 3 + 3.

So for starters, I'll need to figure out just how many ways I can arrange the n tests. So, n factorial.
Now I split that into n groups, divide all but one by 2 and then sum all the results. That will be the number of scenarios in which we got someone right.
So we got:

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

Let's see if this checks out:

n = 1
(1+1)((1-1)!)/2 = 2*0!/2 = 1

n = 2
3/2... I'm not sure about this one, let's just keep going

n = 3
4*(2!)/2 = 4

n = 4
5*(3!)/2 = 15

Yep, checks out so far. I'm placing my bet on this one. The reason it failed at 2 was because of rounding errors, but we can just call it an exception and leave it at that.
Now, we need to divide the good scenarios by the total scenarios. Easy peasy.

So the final result is:
(n+1)((n-1)!)/(2(n!)

If you can simplify this be my guest, but this is my answer so far. Here are the results for someone to check out:

n--Result
1--1
2--0.75
3--0.(66)
4--0.625
5--0.6
6--0.58(3)
7--0.(571428)
8--0.5625
9--0.(5)
10--0.55

So that is my answer. If anyone wants to see if it's true or not, be my guest! Who knows, considering the fail with 2, maybe there's a ton of other wrong values. I'm counting on you guys to prove me wrong ;)

PS:I used google's calculator to do the maths on that table I made. Does this count as googling?

I'm pretty sure it's ██████, but I'm busy right now so I can't check. I'm not sure why, but it works for 2 to 4.

No solutions yet, I'm afraid.

Robly, that is a good line of reasoning, and a great start to the problem, but it doesn't end up matching the values.

Your first approach was to look at each paper getting handed out... and figure the chance of it going astray was ((1-#students left)/#students left). Then you multiplied that into the cumulative probability of no-one getting the right paper. So for two students, you get (1/2), which works. For three students, you get (2/3)*(1/2), which also works. But it stops working at four students.

The place your logic breaks down is in the chance of a paper going astray -- it isn't, in general (1-#students_left)/#students_left. That would be the case if we were certain this student's paper was still in play. But this isn't always true. Maybe the teacher has already handed student 3's paper to student 1. So the chance of a particular paper going to the right student depends on the previous actions (and their probabilities). In the extreme example, with a million kids, the second-to-last kid to get his/her paper does not have a 50% chance of getting it.

Your second approach was to notice a pattern in the cases of n=3 and n=4, where one column always had a match, and the other columns had 50% matches. That pattern is totally there -- but only for those two cases, I'm afraid. Already at n=5, you'll get a different result. (The chance of at least one student getting his/her paper when n=5 is not 60%, for the record). That kept tripping us up as we worked on it, too -- we'd see a pattern, but it didn't extend past n=4.

And this is the fun thing about the problem -- on its surface, it seems so simple. But my first few (okay, many) attempts at answering it also failed. There's always some extra challenge or exception that crops up. In fact, while I think I'm closer to an answer than before, I haven't been able to write down a complete formula yet.

Okay, here's my answer. Also, I just wanted to attract some attention to some topics that I have posted in that aren't getting replied to so that I can receive feedback:
The "Series of Levels" topic in the Velocity Raptor forums
The "Centrifugal Game" topic in the And the Rest forums
I understand why anyone hasn't replied to my posts in the "Hello" topic and the "Welcome" topic, and I don't really care for anyone to post in there, but I just want to point out that no one has responded on those (didn't expect someone to post in there, did ya? )
Also, though I was not the last to post in the "Quantum Game" thread, I would still like it if other people could contribute ideas, because I'm out of ideas to contribute to the "Quantum Game" thread in the And the Rest forums
The thing I would like people to contribute to the most is my series of levels, because I spent a lot of time on it, and for some reason, people just stopped posting in there. I haven't even received a post from anyone saying that they completed the whole story. By the way, 1,000 awesome points to the first to do so and post about it! I would find it super-awesome if anyone could post anything about my series in that thread, whether it be asking for help on a level, suggesting a way to improve a level, or saying you have the most achievements of anyone. Well, enough chitter-chatter, let's get to the problem:

So, this is the sum of the chances for each student being the first in their class to get their own paper. Let's see the chances for each person being the first to get their own paper and try to spot any patterns that crop up. I will represent the number person getting their first paper as x.
Starting off, at x=1, the probability is:
1/n
Nice and sweet, though it gets harder at x=2, because we have to account for the first person taking neither his/her paper nor the second person's paper and the chance that the second person gets their paper:
(n-2)/n * 1/(n-1)
or
(n-2) / ((n)(n-1))
Somehow, it reaches an even higher level of difficulty at x=3, because not one, but two terms come into play. The first is the chance that the first person chooses a paper not belonging to one of the first three paper, then the second chooses neither his/her paper nor the third persons, then the third person chooses their paper. The second is the chance that the first person chooses the second person's paper and the second person doesn't choose the third person's paper, then the third person chooses their own paper. Here it is:
(n-3)/n * (n-3)/(n-1) * 1/(n-2) +
1/n * (n-2)/(n-1) * 1/(n-2)
Already we see patterns emerging. The denominator counts down from n for obvious reasons (you lose an essay each time), and the numerator always ends in one (the last person always needs their essay, because this is the chance that they get it while the people in front of them don't). Also, interestingly, the numerator stays (n-3) until the 1 on the first term. On x=2 it stays (n-2). If x=1 had more to it, we might even see that there would be an (n-1) before the 1 there. Also, since the denominators of both of these terms are the same, we can add them without much trouble. Here they are added together:
((n-3)^2 + (n-2)) / ((n)(n-1)(n-2))
or
(n^2 - 5n + 7) / ((n)(n-1)(n-2))
Hm... It seemed prettier before. Anyways, lets move on to x=4, where we have to count the chance of the first person choosing none of the first four's and the second not choosing the second's, third's, or fourth's, the chance of the first person choosing none of the first four's and the second choosing the third's, the chance of the first choosing the second's and the second not choosing the third's or the the fourth's, the chance of the first choosing the second's and the second choosing the third's, and the chance of the first choosing the third's and the fourth still getting his/hers. Wow. Hopefully, we won't have to go any farther than this before we figure out how to solve it (the terms represent the chances of the events on the list happening plus any other criteria for the fourth getting his/her paper first in order top to bottom representing the first to last ones in the list):
(n-4)/n * (n-4)/(n-1) * (n-4)/(n-2) * 1/(n-3) +
(n-4)/n * 1/(n-1) * (n-3)/(n-2) * 1/(n-3) +
1/n * (n-3)/(n-1) * (n-4)/(n-2) * 1/(n-3) +
1/n * 1/(n-1) * (n-3)/(n-2) * 1/(n-3) +
1/n * (n-3)/(n-1) * (n-3)/(n-2) * 1/(n-3)
This can be summed up to:
((n-4)^3 + 2(n-4)(n-3) + (n-3)^2 + (n-3)) / ((n)(n-1)(n-2)(n-3))
So, here's the list so far:
x=1, ((1)) / ((n))
x=2, ((n-2)) / ((n)(n-1))
x=3, ((n-3)^2 + (n-2)) / ((n)(n-1)(n-2))
x=4, ((n-4)^3 + (2)(n-4)(n-3) + (n-3)^2 + (n-3)) / ((n)(n-1)(n-2)(n-3))
And, if you feel the urge to simplify this, you could look at it this way:
x=1, ((1)) / ((n))
x=2, ((n-2)) / ((n)(n-1))
x=3, ((n-3)^2) / ((n)(n-1)(n-2)) + ((1)) / ((n)(n-1))
x=4, ((n-4)^3) / ((n)(n-1)(n-2)(n-3)) + ((2)(n-4) + (n-3) + (1)) / ((n)(n-1)(n-2))
If you add all these simplified expressions up, you will get this:
((1)) / ((n)) + ((n-2) + (1)) / ((n)(n-1)) + ((n-3)^2 + (2)(n-4) + (n-3) + (1)) / ((n)(n-1)(n-2)) + ((n-4)^3) / ((n)(n-1)(n-2)(n-3))
Simplify this and you get:
((1)) / ((n)) + ((n-1)) / ((n)(n-1)) + (n^2 - 3n - 1) / ((n)...(n-2)) + ((n-4)^3) / ((n)...(n-3))
And now I will keep on rearranging this in hopes of seeing a pattern of some sort...
2/n + (n^2 - 3n - 1)/(n...(n-2)) + ((n-4)^3)/(n...(n-3))
Let's try this out for n=1 and n=2:
2/1 + (1^2 - 3*1 - 1)/(1(1-1)(1-2)) + ((1-4)^3)/(1(1-1)(1-2)(1-3))
2 + (1 - 3 - 1)/(1*-1*0) + (-3)^3/(1*-1*-2*0)
2 + (-3)/0 + (-27)/0
Of course, I get an answer even more indeterminate than indeterminate itself! Did I do anything wrong? I think no, but I could be wrong, so tell me if I am. This should give 1, not two, and I believe it does in fact equal 1. If I have stuck to the basic principles of mathematics, then it has to give 1! So, 2 + undefined + undefined = 1! Of course, in my understanding, 2 + undefined + undefined = indeterminate as well. It can also equal undefined, which is why I say it is more indeterminate than indeterminate itself, because indeterminate never equals undefined, yet this expression can equal undefined or indeterminate, so you have even less of a chance of knowing what it will equal. Sorry for going into the mathematics of infinite, but I just thought that it was interesting how I got myself into a situation where division by zero crops up without doing anything mathematically wrong. Well, I didn't really arrive at the expression that I was looking for, but I hope this can be a starting point for anyone else looking into this, and I did get a cool end result!

That sounds like the opposite of a derangement, where no one gets there respective papers... So the answer would be [  ( (total possibilities) - (derangement of n, or !n) ) / (total possibilities)  ]. The total number of possibilities is, of course, n!, so the answer is (n!-!n)/n!! (That last exclamation mark is punctuational). So, let's check, curtesy of wolfram alpha:

n=1, 1 chance (http://www.wolframalpha.com/input/?i=%2 ... %29%2F1%21)
n=2, 1/2 chance (http://www.wolframalpha.com/input/?i=%2 ... %29%2F2%21)
n=3, 2/3 chance (http://www.wolframalpha.com/input/?i=%2 ... %29%2F3%21)
n=4, 5/8 chance (http://www.wolframalpha.com/input/?i=%2 ... %29%2F4%21)
n=5, 19/30 chance (http://www.wolframalpha.com/input/?i=%2 ... %29%2F5%21
n=6, 91/144 chance (http://www.wolframalpha.com/input/?i=%2 ... %29%2F5%21)
...
(This seems about right)

This should work out. Here's where I found out about derangements: http://what-if.xkcd.com/9/
It's near the bottom, right after the part about chatroulette. Funny, I was just going through old what-ifs because I can't wait a whole week for them, and I found that, researched it a little, then a light-bulb went off in my head. Also, here is a direct quote from the examples part of the Wikipedia page on derangements:

"How many ways could the professor hand the tests back to the students for grading, such that no student received his or her own test back?"

After reading that, I was just like, "Woah, I'm gonna finally find the answer to that TTG thread." Now, after all of this, I am near certain that I have found the answer, which means, I win.



It just took me almost a year to figure it out.

Nice.

It's a bit of a wall of text, above most of which I just grazed over, but good job on this.

robly18 wrote:...It's a bit of a wall of text...

Wall of text? You mean my previous post before my latest onto this topic? I posted that months ago. If you're not referring to that, then I really don't see how you could call my post a wall of text...

Guess I must've missed your other post. I don't have a habit of looking at dates.

robly18 wrote:Guess I must've missed your other post. I don't have a habit of looking at dates.

Yeah, that would make sense. I've seen threads where the last post was months ago, but when somebody finally posted in it again, the post before theirs (the months old one) was replied to instead. I've just found that funny. Is it just me who analyzes these fora so much? It also seems like I'm the only one to refer to "This" as "fora" instead of one "forum," too. I mean, it says forums on the TTG main page anyways, so there are obviously multiple fora/forums according to Andy.