View topic - nice probability problem • Art of Problem Solving
sir see this post .they are giving the answer 1/2 how it is possible
View topic - nice probability problem • Art of Problem Solving
sir see this post .they are giving the answer 1/2 how it is possible
Counting the possible seatings...Quote:
There are n people in a class. The first person forgets his seat, and just picks one randomly. The next n-1 people operate as follows:
If their seat is vacant, then they will take it.
If their seat is taken, then they will pick a random one.
What is the likelihood that the last arriving person will sit in his or her assigned seat?
The first person sits in his own seat... 1
He sits in the nth person's seat... 1
So far that's one out of two possibilities in the last (i.e. nth) person's favour.
The first person sits in the (n-1)th person's seat... another 2 possibilities, one of which (again) unites the nth person with his seat.
The first person sits in the (n-2)th person's seat... another 4 possibilities, 2 of which unite the nth person with his seat.
The first person sits in the (n-3)th person's seat... another 8 possibilities, 4 of which unite the nth person with his seat.
Etc.
E.g., the above five cases for n = 7, where numbers are people in number order of choosing a seat, and the position of a number indicates whose seat the person has chosen. We have...
1 2 3 4 5 6 7 (everyone has chosen their own)
7 2 3 4 5 6 1 (first has chosen the seat belonging to the nth)
6 2 3 4 5 1 7
7 2 3 4 5 1 6 first has chosen the seat belonging to the (n-1)th
5 2 3 4 1 6 7
6 2 3 4 1 5 7
7 2 3 4 1 6 5
7 2 3 4 1 5 6 first has chosen the seat belonging to the (n-2)th
4 2 3 1 5 6 7
5 2 3 1 4 5 7
6 2 3 1 5 4 7
6 2 3 1 4 5 7
7 2 3 1 5 6 4
7 2 3 1 4 5 5
7 2 3 1 5 4 6
7 2 3 1 4 5 6 first has chosen the seat belonging to the (n-3)th
Treating each block of people from person 2 to person 1 as one person you can reduce the numbers as shown below, and proceed (after case one) on the assumption that the first person/block chooses seat 2. And this shows that the sets of possibilities are bound to double.
1 2 (everyone has chosen their own)
2 1 (first has chosen the seat belonging to the nth)
2 1 3
3 1 2 first has chosen the seat belonging to the (n-1)th
2 1 3 4
3 1 2 4
4 1 3 2
4 1 2 3 first has chosen the seat belonging to the (n-2)th
2 1 3 4 5
3 1 2 4 5
4 1 3 2 5
4 1 2 3 5
5 1 3 4 2
5 1 2 4 3
5 1 3 2 4
5 1 2 3 4 first has chosen the seat belonging to the (n-3)th
Notice each new set of seatings takes the previous and adds a new successor on the right, then duplicates the set but switches left and right ends round.
Ask there not here.Quote:
Originally Posted by ayushdadhwal
CB