Here's a maths problem for you all:
If a teacher returns homework to each student in the class at random, what is the probability of no student getting his own homework back?
Obviously the answer depends on the size of the class, but as the class size increases, the probability rapidly approaches a limit. What is this limit?
Good luck!
x = number of students.
The probability that one student doesn't get his own homework is (1-x)/x = 1/x-1.
The probability that no students get his own homework back it is (1/x-1)^x = 1/(x^x)-1
The limit when the number of students increases is 1.
I hope I got it right. It's quite late 
| Peterssidan wrote: |
x = number of students.
The probability that one student doesn't get his own homework is (1-x)/x = 1/x-1.
The probability that no students get his own homework back it is (1/x-1)^x = 1/(x^x)-1
The limit when the number of students increases is 1.
I hope I got it right. It's quite late ;) |
No... I'm afraid that is incorrect. I figured this out last night, but I won't post an answer for a week or two because I want to give other people a chance to answer.... | Peterssidan wrote: |
x = number of students.
1. The probability that one student doesn't get his own homework is (1-x)/x = 1/x-1.
2. The probability that no students get his own homework back it is (1/x-1)^x = 1/(x^x)-1
3. The limit when the number of students increases is 1.
I hope I got it right. It's quite late |
I'm afraid you made a mistake in the first line:
The probability that the first student doesn't get his own homework is (x-1)/x, not (1-x)/x, which in any case is not the same as 1/x-1.
But then the probability that the second student doesn't get his own homework must be calculated separately.
I suggest you try some of the simplest cases first (n=1, 2, 3) to try and understand the problem better. Make sure you give back the homework to students one at a time, and keep track of which are left to give to which students
By the way, the final answer is a number strictly between 0 and 1 (i.e., it's neither 0 nor 1)
Good luck! | infinisa wrote: |
| Peterssidan wrote: | x = number of students.
1. The probability that one student doesn't get his own homework is (1-x)/x = 1/x-1.
2. The probability that no students get his own homework back it is (1/x-1)^x = 1/(x^x)-1
3. The limit when the number of students increases is 1.
I hope I got it right. It's quite late ;) |
I'm afraid you made a mistake in the first line:
The probability that the first student doesn't get his own homework is (x-1)/x, not (1-x)/x, which in any case is not the same as 1/x-1.
But then the probability that the second student doesn't get his own homework must be calculated separately.
I suggest you try some of the simplest cases first (n=1, 2, 3) to try and understand the problem better. Make sure you give back the homework to students one at a time, and keep track of which are left to give to which students
By the way, the final answer is a number strictly between 0 and 1 (i.e., it's neither 0 nor 1)
Good luck! |
He also got the limit incorrect... but I think that may be partly from him not understanding the question... | Afaceinthematrix wrote: |
I figured this out last night, but I won't post an answer for a week or two because I want to give other people a chance to answer.... |
OK, if you want me to check the answer without spoiling it for the other folks, you can send a private message for now if you wish.Hello Folks
Have you all forgotten about this problem, or are you just stuck?
Hoping to hear from you!
The way I calculated it, I got the limit as 0 as x approaches infinity .... 
I have PMed you my method ... please tell me where I have gone wrong ... Hi AVG,
I hope you don't mind replying to your PM by post for everyone's benefit.
| _AVG_ wrote: |
The probability of the first student not getting his homework = (x-1/x)
2nd student = (x-2/x-1)
3rd student = (x-3/x-2)
....
(x-1)th student = (2/3)
xth student = (1/2)
Therefore, to get the probability of no student getting his homework, you multiply all .... resulting in (1/x) as the answer.
Thus, the limit as x approaches infinity is 0 since 1/infinity is 0.
Where have I gone wrong? |
When you considered the 2nd student, you forgot to consider the possibility that Student 1 gets Student 2's homework: In this case the probability of Student 2 not getting his homework is 1!
Hope this helps. I was just thinking of a method to solve this one...
i don't know if this is the right way to do it, so the first thing that I'm going to ask what is Chapter you're dealing with in Maths? (Can help us figure out the problem)
I thought: why not doing it on a Statistics-way:
It has been a while since I have got those lessons. 
Let say there are 3 students...
The Graphic should be like this (done in Paint >.<)
EDIT: For some reason it wont dispay here so you get the URL.
EDIT 2: My Hotlink was on, I included this website too now.
Student 1 has two options: Getting the Good sheet back or the Fault Sheet... so he has 50% of getting his paper back right?
Student 2 has got 25% chance of getting his sheet back (because if Student 1 gets the right sheet back,...)
Student 3 has 12.5% chance
Student 4 has 6.25% chance (not on the picture 
)
So If we want the chance of the 4 people we do: 0.5 * .25 * .125 * .0625 = 0.0009765 = 0.097% chance that 4 people all get a wrong sheet.
Now I don't really have a formula (still working on that >.< ) but I do think this is a good method to solve this.
Adri | adri wrote: |
I was just thinking of a method to solve this one...
i don't know if this is the right way to do it, so the first thing that I'm going to ask what is Chapter you're dealing with in Maths? (Can help us figure out the problem)
I thought: why not doing it on a Statistics-way:
It has been a while since I have got those lessons.
Let say there are 3 students...
The Graphic should be like this (done in Paint >.<)
EDIT: For some reason it wont dispay here so you get the URL.
EDIT 2: My Hotlink was on, I included this website too now.
Student 1 has two options: Getting the Good sheet back or the Fault Sheet... so he has 50% of getting his paper back right?
Student 2 has got 25% chance of getting his sheet back (because if Student 1 gets the right sheet back,...)
Student 3 has 12.5% chance
Student 4 has 6.25% chance (not on the picture )
So If we want the chance of the 4 people we do: 0.5 * .25 * .125 * .0625 = 0.0009765 = 0.097% chance that 4 people all get a wrong sheet.
Now I don't really have a formula (still working on that >.< ) but I do think this is a good method to solve this.
Adri |
Although I don't comprehend this method, if you do continue with it, you will end up with 0.5^x for the number of students 'x'. As the value of 'x' reaches infinity, wouldn't the limit eventually be 0 again? So, I feel that this method is wrong.
I'm highly confused ... infinisia, could you PM me another hint? | _AVG_ wrote: |
| adri wrote: | I was just thinking of a method to solve this one...
i don't know if this is the right way to do it, so the first thing that I'm going to ask what is Chapter you're dealing with in Maths? (Can help us figure out the problem)
I thought: why not doing it on a Statistics-way:
It has been a while since I have got those lessons.
Let say there are 3 students...
The Graphic should be like this (done in Paint >.<)
EDIT: For some reason it wont dispay here so you get the URL.
EDIT 2: My Hotlink was on, I included this website too now.
Student 1 has two options: Getting the Good sheet back or the Fault Sheet... so he has 50% of getting his paper back right?
Student 2 has got 25% chance of getting his sheet back (because if Student 1 gets the right sheet back,...)
Student 3 has 12.5% chance
Student 4 has 6.25% chance (not on the picture )
So If we want the chance of the 4 people we do: 0.5 * .25 * .125 * .0625 = 0.0009765 = 0.097% chance that 4 people all get a wrong sheet.
Now I don't really have a formula (still working on that >.< ) but I do think this is a good method to solve this.
Adri |
Although I don't comprehend this method, if you do continue with it, you will end up with 0.5^x for the number of students 'x'. As the value of 'x' reaches infinity, wouldn't the limit eventually be 0 again? So, I feel that this method is wrong.
I'm highly confused ... infinisia, could you PM me another hint? |
The method I'm using is just "the Tree method":
Student 1 has the option to get a Good sheet (G) or a Fault Sheet (F), If he has a good Sheet (G) than Student 2 has 2 options: a good sheet or a Fault sheet. If Student 1 has a wrong sheet than Student 2 still can have a good sheet or a wrong sheet and so on....
But I do think that the limit is 0.
2 Students = 50% chance
The more Students the less chance you have to have them all wrong so obviously the limit is zero.
Adri 
Yes, Adri, what you said makes perfect sense but infinisia earlier mentioned that the limit was not zero but something between 1 and 0 ... (neither was it 1) 
| _AVG_ wrote: |
| Yes, Adri, what you said makes perfect sense but infinisia earlier mentioned that the limit was not zero but something between 1 and 0 ... (neither was it 1) |
If the limit isn't 0, someone has to give an explanation because I can't think of a way that the limiit isn't 0. 
Adri | adri wrote: |
I was just thinking of a method to solve this one...
i don't know if this is the right way to do it, so the first thing that I'm going to ask what is Chapter you're dealing with in Maths? (Can help us figure out the problem)
I thought: why not doing it on a Statistics-way:
It has been a while since I have got those lessons.
Let say there are 3 students...
The Graphic should be like this (done in Paint >.<)
EDIT: For some reason it wont dispay here so you get the URL.
EDIT 2: My Hotlink was on, I included this website too now.
Student 1 has two options: Getting the Good sheet back or the Fault Sheet... so he has 50% of getting his paper back right?
Student 2 has got 25% chance of getting his sheet back (because if Student 1 gets the right sheet back,...)
Student 3 has 12.5% chance
Student 4 has 6.25% chance (not on the picture )
So If we want the chance of the 4 people we do: 0.5 * .25 * .125 * .0625 = 0.0009765 = 0.097% chance that 4 people all get a wrong sheet.
Now I don't really have a formula (still working on that >.< ) but I do think this is a good method to solve this.
Adri |
The tree diagram is fine, but the calculations are off:
| Quote: |
| Student 1 has two options: Getting the Good sheet back or the Fault Sheet... so he has 50% of getting his paper back right? |
50% is only true if there are 2 students. For n students, the probability is 1/n.
I can't help you with the "Chapter you're dealing with in Maths" as this problem isn't from a Maths book. All I can say is that the problem is not as easy as it may appear at first sight.
Keep trying & good luck! | _AVG_ wrote: |
Although I don't comprehend this method, if you do continue with it, you will end up with 0.5^x for the number of students 'x'. As the value of 'x' reaches infinity, wouldn't the limit eventually be 0 again? So, I feel that this method is wrong.
I'm highly confused ... infinisia, could you PM me another hint? |
| adri wrote: |
The method I'm using is just "the Tree method":
Student 1 has the option to get a Good sheet (G) or a Fault Sheet (F), If he has a good Sheet (G) than Student 2 has 2 options: a good sheet or a Fault sheet. If Student 1 has a wrong sheet than Student 2 still can have a good sheet or a wrong sheet and so on....
But I do think that the limit is 0.
2 Students = 50% chance
The more Students the less chance you have to have them all wrong so obviously the limit is zero.
Adri |
I suggest you work out the probability (very carefully!) for the first few values of n (number of students). So far we have:
1: 0 (nothing can go wrong in this case)
2: 0.5 (as you said; There's a 1/2 chance the first student will get the wrong homework; then the same thing will happen to the other student as happens to the first)
Now, what about 3 & 4?
Good luck!For 3 students, I got the probability as 1 / 3
and for 4 students I got the probability as 3 / 8
| _AVG_ wrote: |
For 3 students, I got the probability as 1 / 3
and for 4 students I got the probability as 3 / 8 |
These results are both correct!
See if you can do the same for 5 & 6 students (I myself have worked it out up to 8 students), and then try to guess what the limit is. Hint: it's easier to recognise if you take the reciprocal of each result, and write it in decimal form.
Good luck!
P.S.: I hope that by now you can see the limit is neither 0 nor 1!Come on people, we're making progress here - let's not give up now!
Maybe you need a hint, but I don't think so yet.
| infinisa wrote: |
Here's a maths problem for you all:
If a teacher returns homework to each student in the class at random, what is the probability of no student getting his own homework back?
Obviously the answer depends on the size of the class, but as the class size increases, the probability rapidly approaches a limit. What is this limit?
Good luck! |
the theory of probablity is correct when it reaches to infinity infinity is not possible so large valy is correct | infinisa wrote: |
Here's a maths problem for you all:
If a teacher returns homework to each student in the class at random, what is the probability of no student getting his own homework back?
Obviously the answer depends on the size of the class, but as the class size increases, the probability rapidly approaches a limit. What is this limit?
Good luck! |
As there hasn't been much progress on this problem for a while, here's a substantial hint:
Let's define nFr to be the number of ways of returning homework to to n students so that exactly r students receive their own homework (I've invented this notation for the sake of this problem).
So the number of ways of no student getting his homework back is nF0.
Since the total number ways of returning the homework is n!, the probability of no student getting his homework back is nF0/n!.
So we need to calculate nF0.
The idea is that we work out nFr for successive values of n. For each n, we need to work out nFr for all values of r (from 0 to n), as it turns out that nF0 is the hardest to work out, and here's how:
To calculate nFr for any value of r that is not 0:
If exactly r students get their own homework back , that means of the other (n-r) students, none gets his homework back, which can happen in (n-r)F0 ways. Bearing in mind that the r students can be chosen in nCr ways), we get:
nFr = nCr (n-r)F0 (for r > 0).
Since n! = nF0 + nF1 + nF2 + ... nFn, we can now work out nF0 as
nF0 = n! - (nF1 + nF2 + ... nFn)
I used an Excel spreadsheet to work out nFr for n from 0 to 8.
By that point, the limit of nF0/n! becomes pretty obvious if you look at its reciprocal, n!/nF0, so I included a column with this value as well.
The challenge is now to make a table for nFr, and hence figure out the limit of nF0/n! (via its reciprocal, n!/nF0).
Good luck!^HMMMMM nice hint..lol its almost the full prob...here the reminin lil bit of it:
Here nFr means no of ways in which r students get thier copy back]
nF1=1*(n-1)*(n-2)*(n-3)....(1)
nF2=1*1*(n-2)*(n-3)....(1)
nF3=1*1*1*(n-3)....(1)
.
.
.
.
nFn=1*1*1..1=1
Addind all nFr from r==1 to n=let it b add1
add1=
=[1+(1*2)+(2*3)+(2*3*4)+...+(2*3*4*...*(n-1)]
=[1!+2!+3!+4!+...+(n-1)!]
nF0=n!-add1
Req. probability=p2
p2=
=nF0/(n!)
Subst nF0:
p2=
=[1+(1*2)+(2*3)+(2*3*4)+...+(2*3*4*...*(n-1)]/(n!)
=[(1/n!)+(1*2/n!)+(2*3/n!)+(2*3*4/n!)+...+(2*3*4*...*(n-1)/n!]
As n bcums vv large i.e n (tends to)->infinity
p2=0
Which is so convincing!
Hhmmm........
Last edited by nanunath on Sat May 30, 2009 8:52 pm; edited 2 times in total
Hi nanunath
Congratulations - someone finally worked on my hint from a week ago!
Unfortunately, your reasoning is not 100%. The fact is, I'm pretty sure you can't work out nFr (for a given n) unless you have worked out all the previous "rows", i.e. mFr for all m < n . This is made possible by by iterative formula I gave in my last post:
| Quote: |
| nFr = nCr (n-r)F0 (for r > 0). |
where you see that the right hand side only involves (n-r)F0 for r > 0, so that (n - r) < n, and that's why the formula is no use in the case we're interested in: r = 0, so that to find nF0 we have to use the formula:
| Quote: |
| nF0 = n! - (nF1 + nF2 + ... nFn) |
But to see why this is so, I must explain the flaw in your argument, which is in the first part, where you attempt to give the values of nFr directly, without knowing the previous "rows":
| nanunath wrote: |
^HMMMMM nice hint..lol its almost the full prob...here the reminin lil bit of it:
Here nFr means no of ways in which r students get thier copy back]
nF1=1*(n-1)*(n-2)*(n-3)....(1)
nF2=1*1*(n-2)*(n-3)....(1)
nF3=1*1*1*(n-3)....(1)
.
.
.
.
nFn=1*1*1..1=1
|
Let's look at nF1 - the number of ways exactly one student gets his homework back.
You say:
| Quote: |
| nF1=1*(n-1)*(n-2)*(n-3)....(1) |
In fact the formula should start not as:
nF1=1*...
but as:
nF1=n*...
because although there is only one way a student can get his homework back, there are n students that this could happen to.
Then, all you know is that none of the (n-1) remaining students gets his homework back, so we get:
nF1=n*(n-1)F0
which is the application of my iterative formula, nFr = nCr (n-r)F0, in the case r=1.
So in your formula, you are assuming that (n-1)F0 = (n-1)*(n-2)*(n-3)....(1) = (n-1)!, which can't be true, as it counts all possible ways of returning the homework to (n-1) students, and so includes the situations in which some students get their own homework back.
I hope you get the point.
Your last line:
gives the correct answer, but the implicit line before:
nF(n-1)=1*1*1..*2*1=2
is wrong, as nF(n-1) = 0. In fact, if (n-1) students get their own homework back, then so must the last one!
So it's back to the drawing board, I'm afraid - better luck next time!
P.S.: As I don't see any short cut, I suggest you make the Excel spreadsheet, row by row, as proposed in my hint. Ok...wait I'll try again..
actually I'm really bad @probability...coz I've been skippingit for yrs...all thru my FYJC..till now
but I'll try...actually its intrstin!
Hhmmmmm...
I went thru ur 1st post hint properly now...and I think I got
it now
that means:
No of ways in which 'r' students get thier copy back=
=[no. of ways in which 'r' students can b chosen]*[no. of
ways in which a single set of 'r' students get thier copy
back]
=[no. of ways in which 'r' students can b chosen]*[no. of
ways in which a single set of 'r' students get thier copy
back]
=[no. of ways in which 'r' students can b chosen]*[(n-r)F0]
So.....
nFr=nCr*[(n-r)F0]
Which is what u derived in there..
Ok..
Again:
nF0=n!-[nF1+nF2+.....]
But....
nF1=nC1*[(n-1)F0]
Again:
(n-1)F0=(n-1)!-[(n-1)F1+(n-1)F2+.....]
.
.
..proceeding we get to a value we can evaluate manually..
Like 2F0=1
2F0=1 ................(I)
As...
3F0=3!-[3F1] ................(II)
3F1=3C1*[2F0]=3*1=3
3F2=0
So...
3F0=3!-3=3 {Subst in II}
3F0=3 ...{which cums true if u check by counting]
4F0=4!-[4F1+4F2] ........(III)
4F1=4C1*{(4-1)F0}=4*3F0=4*3=12
4F2=4C2*{(4-2)F0)}=6*2F0=6*1=6
4F3=0
So...
4F0=4!-[12+6]=24-18=6
4F0=6 ...{there seems to b a problem here!}
Lemme check!
Hi nanunath
It's good to see that you now get my recursive formula, nFr=nCr*[(n-r)F0] , and its derivation.
Still, you need to be more careful with its application.
For instance, when calculating 3F0:
| Quote: |
3F0=3!-[3F1] ................(II)
3F1=3C1*[2F0]=3*1=3
3F2=0
So...
3F0=3!-3=3 {Subst in II}
|
you forgot to take into account 3F3. Clearly nFn is always 1 (just one way for all students to get their own homework back), so the working should be:
3F0 = 3! - (3F1 + 3F2 + 3F3)
= 6 - (3 + 0 + 1)
= 2
which is, in fact, the correct value:
- There are 2 ways to give the first student the wrong homework back
- If we then consider the student whose homework was not given to the first, there's only one way to give him the wrong homework back (there are only two left: one is his, and the other is that of the first student, so he must get that of the first student)
- The third student must then get the homework of the second student
- so we get 2 x 1 x 1 = 2
Now I'll leave you to correct the working for 4F0 
.....
he he ... 
...
I am an impossible man!
cant stop makin mistakes... 
| nanunath wrote: |
.....
he he ... ...
I am an impossible man!
cant stop makin mistakes... |
That's OK, please just keep at it. They say practice makes perfect For 5 people, is the probability 7/24 ?
| _AVG_ wrote: |
| For 5 people, is the probability 7/24 ? |
I'm afraid not. Did you use my recursive formula, or some other method? May be you could show me your working.
At least you hold the record so far for getting the right answer for 3 & 4
| _AVG_ on Fri Apr 17 wrote: |
For 3 students, I got the probability as 1 / 3
and for 4 students I got the probability as 3 / 8 |
@infisa
Huh.....
was busy for 2-3 days...
and am gonna b more busy for sum more days..
Will b back with ans nxt time...
neways what ur academic background my friend?? | nanunath wrote: |
@infisa
Huh.....
was busy for 2-3 days...
and am gonna b more busy for sum more days..
Will b back with ans nxt time...
neways what ur academic background my friend?? |
I am curious to know why you ask this...
I have an MA in Maths from Cambridge University (UK), and a PhD in Pure Maths from Manchester University (UK).
Actually, I had been away from active maths for a long time, but made a recent come back.
I've been teaching the International Baccalaureate (IB) Maths HL course (for university entry) since 2006, and was an online tutor for a subject in the Maths course at the Portuguese Open University during the first semester of this academic year.
All this has brought back the enthusiasm for maths that I used to have back at school and university - I am keen on maths problem solving and learning more maths.
One of my interests is the writing maths off & online, which has brought me into contact with Moodle, LaTeX, MathML and Microsoft Equation Editor. I have made several appeals to have LaTeX enabled here on Frihost, so that we can write Maths properly (like you see in Wikipedia), but so far to no avail.
I look forward to your next stab at the homework problem | infinisa wrote: |
| _AVG_ wrote: | | For 5 people, is the probability 7/24 ? |
I'm afraid not. Did you use my recursive formula, or some other method? May be you could show me your working.
At least you hold the record so far for getting the right answer for 3 & 4
| _AVG_ on Fri Apr 17 wrote: | For 3 students, I got the probability as 1 / 3
and for 4 students I got the probability as 3 / 8 |
|
I used another method. But I found out that was totally wrong .... now, I've recounted using yet another two different methods ... I got the answer as 47/120 with one method. With the second method, I got 11/30.
Because the second method was easier, I could compute values for 6 and 7 students as well. They are as follows (according to method 2):
- 53/144
- 103/280
Which method's answers are, if any, correct?
I feel that Method 2 could be correct as I made an observation regarding successive values of the probability i.e. for n students and say (n+1) students, when both the fractional values are considered keeping (n+1)! as the denominator:
1 and 2:
0/1 and 1/2 (0/2 and 1/2) 1 gets added
Consider 2 and 3:
1/2 and 1/3 (can be written as 3/6 and 2/6) 1 gets subtracted
3 and 4:
1/3 and 3/8 (8/24 and 9/24) 1 gets added
4 and 5:
3/8 and 11/30 (may be incorrect) (45/120 and 44/120) 1 gets subtracted
5 and 6:
11/30 and 53/144 (both may be incorrect) (264/720 and 265/720) 1 gets added
6 and 7:
53/144 and 103/280 (both may be incorrect) (1855/5040 and 1854/5040) 1 gets subtracted
So, they definitely do follow a pattern. Using this pattern, predictions can be made for 8, 9 and 10:
8 - ((1854* 8 )+1)/8! = 14833/40320
9 - ((14833* 9 )-1)/9! = 133496/362880
10 - ((133496* 10 )+1)/10! = 1334961/3628800
Moreover, if one considers their decimal forms (I've taken 5 decimal places), they seem to be approaching a limit somewhere around 0.36788:
1 - 0.00000
2 - 0.50000
3 - 0.33333
4 - 0.37500
5 - 0.36667*
6 - 0.36806*
7 - 0.36786*
8 - 0.36788* (0.367882)
9 - 0.36788* (0.3678792)
10 - 0.36788* (0.3678794)
*may be incorrect
PS: Sorry for such a long post! @infinisa
Just wanted to know for the sake of curiosity... ...but after reading that..my immedate reaction was like:
WwooooWWWW....
Actually Im a Mechanical Engg. student[Last year]...its my vacation...but Im busy sorting things out coz I've been taking things very lightly till date[since my FY...merely coz I just find the way they teach @ my collg.[but fortunately this felling is no more!]...so will solve ur quest completely..till I get things settled..
1more question...u know any other good forum where such type of Question & Discussions go on?
I'd subscribed to the INTP mailing list..where I thought I'd b getting such stuff directly to my mailbox..but sadly...mostly I get discussions on topics on "politics"..etc I dont like...
And lastly...I want ur EMAIL ID...
My Email Idd is: nanunath@gmail.com
Coz ur I the first person online I found...among the types I search for... ... 
... | _AVG_ wrote: |
.... now, I've recounted using yet another two different methods ... I got the answer as 47/120 with one method. With the second method, I got 11/30.
Because the second method was easier, I could compute values for 6 and 7 students as well. They are as follows (according to method 2):
- 53/144
- 103/280
Which method's answers are, if any, correct? |
The second method's correct: you've got the correct answers for 5, 6 & 7 students.
| _AVG_ wrote: |
I feel that Method 2 could be correct as I made an observation regarding successive values of the probability i.e. for n students and say (n+1) students, when both the fractional values are considered keeping (n+1)! as the denominator:
1 and 2:
0/1 and 1/2 (0/2 and 1/2) 1 gets added
Consider 2 and 3:
1/2 and 1/3 (can be written as 3/6 and 2/6) 1 gets subtracted
3 and 4:
1/3 and 3/8 (8/24 and 9/24) 1 gets added
4 and 5:
3/8 and 11/30 (may be incorrect) (45/120 and 44/120) 1 gets subtracted
5 and 6:
11/30 and 53/144 (both may be incorrect) (264/720 and 265/720) 1 gets added
6 and 7:
53/144 and 103/280 (both may be incorrect) (1855/5040 and 1854/5040) 1 gets subtracted
So, they definitely do follow a pattern. Using this pattern, predictions can be made for 8, 9 and 10:
8 - ((1854* 8 )+1)/8! = 14833/40320
9 - ((14833* 9 )-1)/9! = 133496/362880
10 - ((133496* 10 )+1)/10! = 1334961/3628800 |
I see the pattern - it's really simple, and gives the correct answers up to 10 - so well done!
What I don't see is the method you used to get the numbers - did you use my recursive formula or a method of your own?
| _AVG_ wrote: |
Moreover, if one considers their decimal forms (I've taken 5 decimal places), they seem to be approaching a limit somewhere around 0.36788:
1 - 0.00000
2 - 0.50000
3 - 0.33333
4 - 0.37500
5 - 0.36667*
6 - 0.36806*
7 - 0.36786*
8 - 0.36788* (0.367882)
9 - 0.36788* (0.3678792)
10 - 0.36788* (0.3678794)
*may be incorrect |
Now, finally, you can see that the probability is tending towards a limit strictly between 0 and 1 (as I promised ). To recognise this limit, I suggest you look carefully at the reciprocals of the probabilities (expressed in decimal form).
Well done | nanunath wrote: |
| 1more question...u know any other good forum where such type of Question & Discussions go on? |
If you are mean forums about solving maths problems, I would suggest Math Help Forum. I haven't used it yet myself, but it comes with an excellent recommendation (from my PhD supervisor).
I'll send you my e-mail address by PM.Well, the method I used was very strange.
For 5 numbers, I arranged a string ABCDE with all its possible permutations - 120 of them and I counted the number of permutations in which neither A, B, C, D nor E are in their original positions. It does get very tedious to count through 120 strings, so I created a computer program in Java to help me with my counting. I got the result as 44 so I got 44/120 as the probability. Similarly, that's how I could count through 720 permutations for ABCDEF and through 5040 permutations for the string ABCDEFG. Then, I used the pattern to get 8,9 and 10.
Now, let's see the reciprocals:
1/0 = undefined
2/1 = 2.0000
8/3 = 2.6667
30/11 = 2.7273
144/53 = 2.7170
280/103 = 2.7184
40320/14833 = 2.7183 (2.718263332)
362880/133496 = 2.7183 (2.718283694)
3628800/1334961 = 2.7183 (2.718281654)
I think these values seem to be approaching e.
So, that would make the limt 1/e.
Damn it! How could I not notice that before? | _AVG_ wrote: |
Well, the method I used was very strange.
For 5 numbers, I arranged a string ABCDE with all its possible permutations - 120 of them and I counted the number of permutations in which neither A, B, C, D nor E are in their original positions. It does get very tedious to count through 120 strings, so I created a computer program in Java to help me with my counting. I got the result as 44 so I got 44/120 as the probability. Similarly, that's how I could count through 720 permutations for ABCDEF and through 5040 permutations for the string ABCDEFG. Then, I used the pattern to get 8,9 and 10. |
OK, I see you used a "brute force" method via software. Hadn't thought of that.
| _AVG_ wrote: |
Now, let's see the reciprocals:
1/0 = undefined
2/1 = 2.0000
8/3 = 2.6667
30/11 = 2.7273
144/53 = 2.7170
280/103 = 2.7184
40320/14833 = 2.7183 (2.718263332)
362880/133496 = 2.7183 (2.718283694)
3628800/1334961 = 2.7183 (2.718281654)
I think these values seem to be approaching e.
So, that would make the limt 1/e.
Damn it! How could I not notice that before? |
Yes, that's the right answer - 1/e - at last!
Not only that, but the simple pattern you found actually leads to a proof of the answer:
| _AVG_ wrote: |
So, they definitely do follow a pattern. Using this pattern, predictions can be made for 8, 9 and 10:
8 - ((1854* 8 )+1)/8! = 14833/40320
9 - ((14833* 9 )-1)/9! = 133496/362880
10 - ((133496* 10 )+1)/10! = 1334961/3628800
|
For those who don't know, the number e = 1 + 1/1! + 1/2! + 1/3! + ... and is about 2.71828.
There's a formula for e^x: e^x = 1 + x/1! + x^2/2! + x^3/3! + ...
Since 1/e = e^(-1), and e^(-1) = 1 + (-1)/1! + (-1)^2/2! + (-1)^3/3! + ...
we get 1/e = 1 - 1/1! + 1/2! - 1/3! + 1/4! - 1/5! + 1/6! - 1/7! + 1/8! - 1/9! + 1/10!...
which corresponds exactly to your pattern.
Once again, well done
BTW, did anyone use my suggestion to make an Excel spreadsheet? (that was how I was able to check _AVG_'s answers very quickly.) P.S.: I've just noticed that the Wikipedia article on the number e actually refers to our problem in the section Derangements as the "hat check problem", together with the formula 
