No copying, students.

Probability Level 5

There are 5 students $S_1,S_2,S_3,S_4,S_5$ in a music class and for them there are 5 seats in a row. On examination day, all five students are randomly allotted the five seats. Let $T_i$ denote the event that $S_i$ and $S_{i+1}$ do NOT sit adjacent to each other on examination day. (i=1,2,3,4)

What is the probability that $T_1,T_2,T_3,T_4$ all occur simultaneously on examination day?

If the probability is of the form $\dfrac {a}{b}$ , where $a$ and $b$ are coprime positive integers, find $a+b$

The answer is 67.

2 solutions

Henry U
Dec 8, 2018

We can start writing down all seating arrangements in which all $T_i$ occur.

Let's label the chairs $C_{1,\ldots,5}$

Case 1: $S_1$ on $C_1$

Case 1.1: $S_2$ on $C_3$

\Rightarrow

\Rightarrow

Case 1.2: $S_2$ on $C_4$

\Rightarrow

\Rightarrow

Case 2: $S_1$ on $C_2$

Case 2.1: $S_2$ on $C_4$

Case 2.1.1: $S_4$ on $C_3$

\Rightarrow

Case 2.1.1: $S_4$ on $C_5$

\Rightarrow

Case 2.2: $S_2$ on $C_5$

\Rightarrow

\Rightarrow

Case 3: $S_1$ on $C_3$

Case 3.1: $S_2$ on $C_1$

Case 3.1.1: $S_3$ on $C_4$

\Rightarrow

Case 3.1.2: $S_3$ on $C_5$

\Rightarrow

Case 3.2: $S_2$ on $C_5$

Case 3.2.1: $S_3$ on $C_1$

\Rightarrow

Case 3.1.2: $S_3$ on $C_2$

\Rightarrow

Cases 1 and 2 can be flipped to give all cases where $S_1$ sits on $C_4$ or $C_5$ .

For all positions of $S_1$ there are the following number of good arrangements

$C_1$	2
$C_2$	3
$C_3$	4
$C_4$	3
$C_4$	2
Total	14

This means that the probability is $\frac {14}{5!} = \frac {14}{120} = \boxed{\frac 7{60}}$ and so the answer is $7+60=\boxed{67}$

Why cant we use contradiction method here ???

Rishav Singh - 2 years, 5 months ago

I don't know it, could you explain it a little? And if you want, you can post it as your own solution.

Henry U - 2 years, 5 months ago

You can use graph theory for this question. Make nodes S1, S2, S3, S4 and S5. Now only draw edges between nodes that are not adjacent to each other. Next find the total number of paths that covers every nodes and divide that by 5! (Total possible combinations)

Alex Kularatnam - 2 years, 5 months ago

Is there some relatively straightforward way to count this number of paths? I don't know right now, but maybe this method really helps.

Henry U - 2 years, 5 months ago

Jacobi Hwang
Aug 3, 2019

from itertools import permutations
import numpy as np

def isgood(x):
    l=len(x)
    y=[abs(x[i]-x[i+1]) for i in range(l-1)]
    if 1 in y:
        return False
    else:
        return True

def test(n):
    a=[i for i in range(1,n+1)]
    b=[np.array(i) for i in permutations(a,n)]
    count=0
    for i in b:
        if isgood(i):
            count+=1
    return count

def fac(n):
    if n==0 or n==1:
        return 1
    else:
        return n*fac(n-1)

s=[test(i) for i in range(10)]
t=[s[i]*1.0/fac(i) for i in range(10)]
print s
print t

This is not a smart way to solve this simple problem.

shriman keshri - 1 year, 1 month ago

No copying, students.

The answer is 67.

2 solutions

0 pending reports