$2017$ people move from $123$ rooms. Prove that they end up in the same room.

Question

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.

Answer 1

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.

Answer 2

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

Answer 3

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.

Answer 4

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.