Author |
Topic: people in a building (Read 1235 times) |
|
cool_joh
Newbie
Gender: 
Posts: 50
|
 |
people in a building
« on: Sep 17th, 2008, 5:40am » |
 Quote  Modify
|
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.
|
|
 IP Logged |
MATH PRO
|
|
|
pex
Uberpuzzler
Gender:
Posts: 880
|
|
Re: people in a building
« Reply #1 on: Sep 17th, 2008, 6:44am » |
Quote Modify
|
Assuming that the person leaving his/her room is selected only from the room(s) where the number of people is not minimal, 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.
|
| « Last Edit: Sep 17th, 2008, 6:45am by pex » |
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: people in a building
« Reply #2 on: Sep 17th, 2008, 7:16am » |
Quote Modify
|
Quote:| increases at least once every n-1 minutes |
|
Why? 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.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
pex
Uberpuzzler
Gender:
Posts: 880
|
|
Re: people in a building
« Reply #3 on: Sep 17th, 2008, 10:06am » |
Quote Modify
|
on Sep 17th, 2008, 7:16am, towr wrote: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.
|
|
 A bit too fast I guess... And your example disproves cool_joh's statement, as required.
|
|
IP Logged |
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: people in a building
« Reply #4 on: Sep 18th, 2008, 6:05am » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: people in a building
« Reply #5 on: Sep 18th, 2008, 2:31pm » |
Quote Modify
|
on Sep 18th, 2008, 6:05am, 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.
|
| « Last Edit: Sep 18th, 2008, 2:31pm by Grimbal » |
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: people in a building
« Reply #6 on: Sep 18th, 2008, 2:59pm » |
Quote Modify
|
on Sep 18th, 2008, 2:31pm, 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.
|
| « Last Edit: Sep 18th, 2008, 3:00pm by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: people in a building
« Reply #7 on: Sep 19th, 2008, 2:27am » |
Quote Modify
|
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.
|
| « Last Edit: Sep 19th, 2008, 2:29am by Grimbal » |
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: people in a building
« Reply #8 on: Sep 19th, 2008, 2:49am » |
Quote Modify
|
on Sep 19th, 2008, 2:27am, 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.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: people in a building
« Reply #9 on: Sep 19th, 2008, 4:59am » |
Quote Modify
|
It is obvious now that you explained why.
It took you one line, but that line was necessary to complete the proof.
|
| « Last Edit: Sep 19th, 2008, 4:59am by Grimbal » |
IP Logged |
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: people in a building
« Reply #10 on: Sep 19th, 2008, 3:27pm » |
Quote Modify
|
on Sep 19th, 2008, 4:59am, Grimbal wrote:
It took you one line, but that line was necessary to complete the proof. |
|
on Sep 18th, 2008, 6:05am, 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= m/n +1 persons is m mod n. What had to be proven.
But it seemed to be obvious 
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print