View topic - nice probability problem • Art of Problem Solving

sir see this post .they are giving the answer 1/2 how it is possible

- January 16th 2011, 08:10 AMayushdadhwalhttp://www.artofproblemsolving.com/Forum/viewtopic.php?t=278908
View topic - nice probability problem • Art of Problem Solving

sir see this post .they are giving the answer 1/2 how it is possible - January 18th 2011, 03:34 PMtom@ballooncalculusQuote:

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. - January 18th 2011, 05:57 PMCaptainBlack