1. ## http://www.artofproblemsolving.com/Forum/viewtopic.php?t=278908

View topic - nice probability problem &bull; Art of Problem Solving
sir see this post .they are giving the answer 1/2 how it is possible

2. 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?
Counting the possible seatings...

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.

View topic - nice probability problem &bull; Art of Problem Solving
sir see this post .they are giving the answer 1/2 how it is possible