4
$\begingroup$

Suppose $2017$ people reside in the rooms of a $123$ room mansion. Each minute, so long as not all the people are in the same room, somebody walks from one room into a different room with at least as many people in it. Prove that eventually all people end up in the same room.

I really have no idea what to do.

Plus I need help with tagging it.

$\endgroup$

4 Answers 4

5
$\begingroup$

HINT: The key is in " somebody walks from one room into a different room with at least as many people in it". So each minute one room gets fuller, one gets emptier, and there's a finite number of people. The numbers 2017 and 123 aren't really significant here.

$\endgroup$
3
  • $\begingroup$ Because 2017 is prime, you can't arrange the rooms so that rooms each have the same amount of people in them, so it is significant. $\endgroup$
    – u8y7541
    May 13, 2017 at 21:42
  • 4
    $\begingroup$ not sure. Even if number of people in each room are all the same, a person can move because of the words "at least" $\endgroup$
    – sku
    May 13, 2017 at 21:46
  • $\begingroup$ You haven't really shown that there can't be a cycle that returns to the starting point. In that case we wouldn't ever get all the people in one room. $\endgroup$ May 13, 2017 at 22:47
3
$\begingroup$

Hint: Consider the number of pairs of people that are all in the same room. Show that it always increases.

$\endgroup$
2
$\begingroup$

At the beginning, some rooms will have more people than others. Since $2017$ is a prime number, there is no way to arrange people in rooms so that some rooms will have $0$ people and other rooms will each have the same amount of people in them. Turns out that the number $2017$ is significant.

Given that some rooms will have more and others will have less, we know that the rooms with less people will feed people into rooms with more people.

It should be easier to solve from here.

$\endgroup$
1
  • 1
    $\begingroup$ The fact that 2017 is prime does not matter. Say there were twelve people, three each in four rooms. You can still have somebody leave a room (leaving two) and enter another (making four). $\endgroup$ May 13, 2017 at 22:46
2
$\begingroup$

Starting with $t=0$ let $P(j,t)$ be the number of people in room #$j$ after $t$ minutes. Let $S(t)=(P(1,t),...,P(123,t)).$

Let $S^*(t)=(s^*(1,t),...,s^*(123,t))$ be the sequence $S(t)$ re-arranged into non-increasing order .E.g. $s^*(1,t)=\max (P(1,t),...P(123,t)).$

Define $S(t_1)<^*S(t_2)$ iff $S^*(t_1)\ne S^*(t_2),$ and for the least $n$ such that $s^*(n,t_1)\ne s^*(n,t_2)$ we have $s^*(n,t_1)<s^*(n,t_2).$ In other words, $S(t_1)<^* S(t_2)$ iff $S^*(t_1)$ is lexicographically less than $S^*(t_2).$

(1). Note that if $S(t_1)<^*S(t_1)$ then $S(t_1)\ne S(t_2).$ Caution : $<^*$ may not a linear order on the set of all possible $S(t)$. We may have $S(t_1)\ne S(t_2)$ with $S^*(t_1)=S^*(t_2)$.

(2).Prove that $[S(t_1)<^*S(t_2) \land S(t_2)<^*S(t_3)] \implies S(t_1)<^*S(t_3).$

(3). Prove that if $S(t)\neq S(t+1)$ then $S(t)<^*S(t+1).$

We cannot have $S(t)<^*S(t+1)$ for every $t,$ else by (1),(2),and (3), $\{S(t)\}_{t\geq 0}$ would be an infinite sequence of distinct "states", but there are only finitely many possible $S(t).$ Therefore, by (3) there exists $t$ such that $S(t)=S(t+1).$

Now $S(t)=S(t+1)$ iff one room contains all the residents.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.