wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> medium >> people in a building
        
(Message started by: cool_joh on Sep 17^th, 2008, 5:40am)

Title: people in a building
Post by cool_joh on Sep 17^th, 2008, 5:40am

There are m people in a building which has n rooms, where n divides m. Each person is in of the rooms. Each minute, one person leave his/her room to the room which has the least number of people. Prove or disprove that eventually the number of people in all rooms are equal.

Title: Re: people in a building
Post by pex on Sep 17^th, 2008, 6:44am

Assuming that the person leaving his/her room is selected only from the room(s) where the number of people is not minimal, [hide]the minimum ~~increases in each minute~~ is nondecreasing and increases at least once every n-1 minutes, so it must eventually hit its upper bound of m/n.[/hide]

Title: Re: people in a building
Post by towr on Sep 17^th, 2008, 7:16am

Quote:

[hide]increases at least once every n-1 minutes[/hide]

Why? [hide]Say we have rooms A, B, C with 2 people in A, 1 in B and 0 in C, we might have the person in room B walking between B and C and back every minute.[/hide]

Title: Re: people in a building
Post by pex on Sep 17^th, 2008, 10:06am

on 09/17/08 at 07:16:55, towr wrote:

[hide]Say we have rooms A, B, C with 2 people in A, 1 in B and 0 in C, we might have the person in room B walking between B and C and back every minute.[/hide]

:-[ A bit too fast I guess... And your example disproves cool_joh's statement, as required.

Title: Re: people in a building
Post by Hippo on Sep 18^th, 2008, 6:05am

And if the statement would be changed ... from the room holding at least minumum + 2 persons ...

Easier proof would be ... sum of squares decreases each minute. And there is only finite number of them ... so the process must terminate. The only terminating state is when each room contains either k or k+1 persons. ... What had to be proven.

Title: Re: people in a building
Post by Grimbal on Sep 18^th, 2008, 2:31pm

on 09/18/08 at 06:05:27, Hippo wrote:

And if the statement would be changed ... from the room holding at least minumum + 2 persons ...

Then you can start with A=2, B=3 and C=4 people. One leaves B for A and back to B and so on.

Title: Re: people in a building
Post by towr on Sep 18^th, 2008, 2:59pm

on 09/18/08 at 14:31:21, Grimbal wrote:

Then you can start with A=2, B=3 and C=4 people. One leaves B for A and back to B and so on.

I think he meant to modify the rules such that a person might only leave his current room if there were at least two more people in it than in the room with the minimum (2). So no one from B would be allowed to leave; only someone from C would.

Title: Re: people in a building
Post by Grimbal on Sep 19^th, 2008, 2:27am

And I think you think right. "minimum + 2" was a bit ambiguous.

But then you need to prove a movement is always possible as long as the rooms don't have equal numbers of people.

Title: Re: people in a building
Post by towr on Sep 19^th, 2008, 2:49am

on 09/19/08 at 02:27:24, Grimbal wrote:

But then you need to prove a movement is always possible as long as the rooms don't have equal numbers of people.

Isn't that obvious? If there is only a difference of 1 between the maximum and the minimum, then the number of rooms can't divide the number of people.

Title: Re: people in a building
Post by Grimbal on Sep 19^th, 2008, 4:59am

It is obvious now that you explained why.

It took you one line, but that line was necessary to complete the proof.

Title: Re: people in a building
Post by Hippo on Sep 19^th, 2008, 3:27pm

on 09/19/08 at 04:59:19, Grimbal wrote:

It took you one line, but that line was necessary to complete the proof.

on 09/18/08 at 06:05:27, Hippo wrote:

The only terminating state is when each room contains either k or k+1 persons.

Yes, I originaly intended to write that means in the terminating state the number of rooms with k+1=http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/lfloor.gifm/nhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/rfloor.gif+1 persons is m mod n. What had to be proven.

But it seemed to be obvious ;)