Serving the Quantitative Finance Community

 
User avatar
alghosh
Topic Author
Posts: 0
Joined: April 28th, 2010, 9:11 am

optimal allocation

August 21st, 2013, 5:49 pm

Long back I have posted this teaser No one took keen interest ... May be I didnt write it properly : Here is the version again :Suppose you are an event manager, there are 57 guests who would stay in a hotel. In one room you may allocate as many guests as you want with a fixed amount for the room and you may book as many room you want.But unfortunately you got an information - among 57 guests , each hate exactly three other guests. Hate is such that if one hates other and stays in same room one would get killed . Now you want to book rooms in such a way that total cost is minimized as well as no one gets killed.Also note if a guest hates another guest does not necessarily mean the later would hate him/her.
 
User avatar
frenchX
Posts: 11
Joined: March 29th, 2010, 6:54 pm

optimal allocation

August 22nd, 2013, 5:32 am

Do you really want with a 100 % occurence than no one gets killed or does the killing enters your cost function ? (I know I'd be a pitiful hotel manager )
 
User avatar
alghosh
Topic Author
Posts: 0
Joined: April 28th, 2010, 9:11 am

optimal allocation

August 22nd, 2013, 7:55 am

QuoteOriginally posted by: frenchXDo you really want with a 100 % occurence than no one gets killed or does the killing enters your cost function ? (I know I'd be a pitiful hotel manager )1st priority would be that no one gets killed as well you dont want to book 57 rooms . Suppose 10 is optimal number then no matter what is the distribution of the guests ( and their hate relationship amongst themselves) you can always allocate them in 10 rooms such that no one gets killed. But if you allocate 9 rooms , then there is a distribution where no matter how you allocate , atleast one would get killed.It took sometime for me to understand this. And given my writting skills... it would definitly take longer time for people here.
 
User avatar
frenchX
Posts: 11
Joined: March 29th, 2010, 6:54 pm

optimal allocation

August 22nd, 2013, 10:21 am

The "hate relationship" is known or unknown by the book manager ? (I suppose it's known otherwise I don't see a solution)
 
User avatar
Paul
Posts: 6604
Joined: July 20th, 2001, 3:28 pm

optimal allocation

August 22nd, 2013, 10:46 am

I used to stay in the Chelsea Hotel in NYC. Much of the appeal is that so many famous people have died there, often violently!P
 
User avatar
Cuchulainn
Posts: 20254
Joined: July 16th, 2004, 7:38 am
Location: 20, 000

optimal allocation

August 22nd, 2013, 11:36 am

QuoteOriginally posted by: PaulI used to stay in the Chelsea Hotel in NYC. Much of the appeal is that so many famous people have died there, often violently!PViciously?
 
User avatar
alghosh
Topic Author
Posts: 0
Joined: April 28th, 2010, 9:11 am

optimal allocation

August 22nd, 2013, 12:38 pm

QuoteOriginally posted by: frenchXThe "hate relationship" is known or unknown by the book manager ? (I suppose it's known otherwise I don't see a solution)Unfortunately or may be fortunately it is unknown... only known fact is each person hates exactly three others... but why cant there be any solution ?
 
User avatar
frenchX
Posts: 11
Joined: March 29th, 2010, 6:54 pm

optimal allocation

August 22nd, 2013, 1:13 pm

In this case there should be a solution but between 57 and 29 rooms I guess? I feel that if you have more than 2 people in a room you can find a "hate" distribution so you have 2 people in a room who will kill each others but that's a raw system 1 intuition. I won't be surprised in there is a clever math solution.
 
User avatar
alghosh
Topic Author
Posts: 0
Joined: April 28th, 2010, 9:11 am

optimal allocation

August 22nd, 2013, 3:19 pm

I don't know whether the solution I found is elegant or not .... but answer is quite interesting .... its way below 29....
 
User avatar
Alan
Posts: 2958
Joined: December 19th, 2001, 4:01 am
Location: California
Contact:

optimal allocation

August 22nd, 2013, 4:13 pm

The problem seems mis-stated to me. Otherwise, if there is more than 1 person in a room, and you don't know the haterelationships, then the probability of a killing is > 0. Since that was ruled out, it doesn't make sense.
 
User avatar
Cuchulainn
Posts: 20254
Joined: July 16th, 2004, 7:38 am
Location: 20, 000

optimal allocation

August 22nd, 2013, 6:32 pm

QuoteOriginally posted by: outrunQuoteOriginally posted by: CuchulainnQuoteOriginally posted by: PaulI used to stay in the Chelsea Hotel in NYC. Much of the appeal is that so many famous people have died there, often violently!PViciously?"I can't keep track of each fallen robin. I remember you well in the Chelsea Hotel, that's all, I don't even think of you that often."Ymca is safer
 
User avatar
alghosh
Topic Author
Posts: 0
Joined: April 28th, 2010, 9:11 am

optimal allocation

August 22nd, 2013, 7:03 pm

QuoteOriginally posted by: AlanThe problem seems mis-stated to me. Otherwise, if there is more than 1 person in a room, and you don't know the haterelationships, then the probability of a killing is > 0. Since that was ruled out, it doesn't make sense.Yes we don't know the relationships... And do we need to know? No .... We just need to find the minimum number of rooms required such that given any relationship (with one condition -- exactly 3 hates ) there exist an allocation where no one gets killed... So this says assume any arbitrary relationship... show that its possible to allocate the guests in the desired conditions within these optimal number of rooms... Do we need to find the allocation... again No... Its just like Pigeon hole principle (PHP)... Now let me float the optimal number which I believe is correct... it is 7
 
User avatar
Alan
Posts: 2958
Joined: December 19th, 2001, 4:01 am
Location: California
Contact:

optimal allocation

August 22nd, 2013, 7:27 pm

That clarifies it. "Assume any arbitrary relationship" is quite different than saying "we don't know the relationship".The relationship is arbitrarily chosen from the class of all possible relationships, but once chosen -- it is revealed tothe booking agent, right?. Then, for any such relationship (known to the booking agent), a certain minimum number of rooms are needed, andthe problem is to show that the maximum of these minimums (among the class of all possible relationships) is 7. That's how I would state it. Now, somebody solve it.
Last edited by Alan on August 21st, 2013, 10:00 pm, edited 1 time in total.