GATE CSE
First time here? Checkout the FAQ!
x
0 votes
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.

asked by Veteran (45.6k points)  
edited by | 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  :)

Your answer

Your name to display (optional):
Privacy: Your email address will only be used for sending these notifications.
Anti-spam verification:
To avoid this verification in future, please log in or register.


Top Users Apr 2017
  1. akash.dinkar12

    3508 Points

  2. Divya Bharti

    2542 Points

  3. Deepthi_ts

    2040 Points

  4. rude

    1966 Points

  5. Tesla!

    1768 Points

  6. Shubham Sharma 2

    1610 Points

  7. Debashish Deka

    1588 Points

  8. Arunav Khare

    1454 Points

  9. Kapil

    1424 Points

  10. Arjun

    1420 Points

Monthly Topper: Rs. 500 gift card

22,076 questions
28,040 answers
63,230 comments
24,135 users