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.