Why shuffle them up?

There are at least 3 students in a classroom. The teacher then randomly shuffles the students's position.

What is the maximum possible probability that none of the students are in their original position?


The answer is 0.375.

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

2 solutions

Rohith M.Athreya
Feb 28, 2017

Let P ( n ) \mathbb{P}(n) denote the probability of "the required event"

P ( n ) = r = 0 n ( 1 ) r r ! \mathbb{P}(n)=\sum_{r=0}^{n}\frac{(-1)^{r}}{r!}

Let us first convince ourselves that the maximum occurs at even n n

Why? if maxima occurs at a P ( 2 n + 1 ) \mathbb{P}(2n+1) , the next term is an addition which makes the maxima lesser than P ( 2 n + 2 ) \mathbb{P}(2n+2) which is a contradiction

Now,let us assume that a maximum occurs at a certain k > 4 k > 4

P ( k ) = 1 0 ! 1 1 ! + 1 2 ! . . . + 1 ( k 2 ) ! 1 ( k 1 ) ! + 1 k ! \mathbb{P}(k)=\frac{1}{0!}-\frac{1}{1!}+\frac{1}{2!}-...+\frac{1}{(k-2)!}- \large \frac{1}{(k-1)!}+\frac{1}{k!}

Clearly, P ( k 2 ) > P ( k ) \mathbb{P}(k-2)> \mathbb{P}(k)

And so, P ( 2 ) \mathbb{P}(2) is greatest.But since there have to be atleast 3 students, our maxima is at P ( 4 ) \mathbb{P}(4) which is 0.375

Let us first convince ourselves that the maximum occurs at even n n

Okay, you have shown that "if n is even, then max(P(n)) occurs when n=4". But why can't the maximum occurs when n is odd?

Pi Han Goh - 4 years, 3 months ago

Log in to reply

thats simple

if maxima occurs at an P ( 2 n + 1 ) \mathbb{P}(2n+1) , the next term is an addition which makes the maxima lesser than P ( 2 n + 2 ) \mathbb{P}(2n+2) which is a contradiction

Rohith M.Athreya - 4 years, 3 months ago

Log in to reply

Yeah that's good. You should add that into your solution. ;)

I was actually thinking of solving this problem by converting P(N) = N! * D(N), and rewriting D(N) as the integral as shown here , but yours is clearly much easier. KUDOS

Pi Han Goh - 4 years, 3 months ago

Log in to reply

@Pi Han Goh yeah!I added it :)

the simplicity of my solution arises from the fact that my knowledge is currently limited.

If i was aware of some such integral before,i might have gone that way too!

Rohith M.Athreya - 4 years, 3 months ago

Log in to reply

@Rohith M.Athreya COngratulations! Keep it uppp!!!

Pi Han Goh - 4 years, 3 months ago
Md Zuhair
Feb 26, 2017

To find the maximum probability, note that your expression for the probability when there are LaTeX: n n students is a partial sum of an alternating series. Use this (along n 3 n\geq 3 ) to find maximum probability is just 1 0 ! 1 1 ! + 1 2 ! 1 3 ! + 1 4 ! = 0.375 \frac{1}{0!} - \frac{1}{1!} + \frac{1}{2!} - \frac{1}{3!} + \frac{1}{4!} = 0.375

The maximum doesn't occur in the limit.

To find the maximum probability, note that your expression for the probability when there are n n students is a partial sum of an alternating series. Use this (along with n 3 n\geq 3 ) to find maximum probability is just 1 0 ! 1 1 ! + 1 2 ! 1 3 ! + 1 4 ! = 0.375 \frac{1}{0!} - \frac{1}{1!} + \frac{1}{2!} - \frac{1}{3!} + \frac{1}{4!} = 0.375

Brian Moehring - 4 years, 3 months ago

Log in to reply

Yes, it would have been better to have us find a b \frac{a}{b} where a , b a,b are coprime and then enter a + b a + b as the answer, which would be 3 + 8 = 11 3 + 8 = 11 .

Brian Charlesworth - 4 years, 3 months ago

The maximum is attained at n = 4, which gives a probability of 3/8 = 0.375. After which the probability value D(n)/n!, approaches 1/e(~0.3679) for n>4.

Siva Bathula - 4 years, 3 months ago

Log in to reply

Oh, So now what to do?

Md Zuhair - 4 years, 3 months ago

1/e = 0.3678...

the answer is 0.375

Pi Han Goh - 4 years, 3 months ago

Log in to reply

Ohkay ohkay.

Md Zuhair - 4 years, 3 months ago

Log in to reply

You didn't explain why the answer is true when n=4.

Pi Han Goh - 4 years, 3 months ago

Log in to reply

@Pi Han Goh i did

and hope it is rigorous enough?

Rohith M.Athreya - 4 years, 3 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...