The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
0 votes
118 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 (57.4k points)
edited by | 118 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  :)

Please log in or register to answer this question.



Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

28,831 questions
36,676 answers
90,577 comments
34,638 users