71 views

N rooms are there and they are numbered from 1 to N.

A person P is in charge of room allocation and allocates these rooms inthe following way:

• Each query ask for two consecutive rooms.
• P selects two consecutive rooms out of the vacant rooms and serves the query. Once allocated those two rooms can not be reallocated. Example : if 2nd and 3rd rooms are vacant, P can consider to select them. If 4th,5th and 7th rooms are vacant, (5,7) can not be considered [ these two can not be considered as allocatable ( because these two(5,7) are not consecutive) ] but (4,5) can be considered to be allocatable. Out of all allocatable vacant rooms at present , P selects any two consecutive randomly (randomly uniform).
• Queries are coming continuously and P is serving them.
• At some point of time, all allocatable rooms are exhausted. At that time further queries are not processed. Process STOPPED.

K is a positive integer $\leq$ N. What is the reccurece relation for the probability of Kth room being filled up after the room allocation process has been stopped.

one example :

If initially 4 rooms are given [1,2,3,4].

First query : assume P selects (2,3)

Seconds query onwards can not be processed. because although 1,4 are vacant, these rooms are not consecutive.

edited | 71 views

how can we do this? :-/

i could only figure out that ,in your example (1,2,3,4)

for,1 to be filled,2 should be filled .

for 2 to be filled,1 or 3 should be filled.

for 3 to be filled,2 and 4 should be filled.

and for 4 to be filled,3 should be filled.

for corner rooms,the probability that they are filled is 1/nC2

for other rooms,the probabioty that they are filled is 2/nC2 (considering their adjacent rooms)

pls help further in solving and correct me  :)