If You are the Smartest Person in the Room, You are in the Wrong Room

Abstract If taken seriously, the advice in the title leads to interesting combinatorics. Consider N people moving between M rooms as follows: at each step, simultaneously, the smartest person in each room moves to a different room of their choice, while no one else moves. The process repeats. In this paper we determine which configurations are reachable, from which other configurations, and provide bounds on the number of moves. Namely, let G ( N , M ) be the directed graph with vertices representing all $$M^N$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msup> <mml:mi>M</mml:mi> <mml:mi>N</mml:mi> </mml:msup> </mml:math> configurations and edges representing possible moves. We prove that the graph G ( N , M ) is weakly connected, and that it is strongly connected if and only if $$M\ge N+1$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>M</mml:mi> <mml:mo>≥</mml:mo> <mml:mi>N</mml:mi> <mml:mo>+</mml:mo> <mml:mn>1</mml:mn> </mml:mrow> </mml:math> (one extra room for maneuvering is both required and sufficient). For $$M\le N$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>M</mml:mi> <mml:mo>≤</mml:mo> <mml:mi>N</mml:mi> </mml:mrow> </mml:math> , we show that the graph has a giant strongly connected component with $$\Theta (M^N)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>Θ</mml:mi> <mml:mo>(</mml:mo> <mml:msup> <mml:mi>M</mml:mi> <mml:mi>N</mml:mi> </mml:msup> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> vertices and diameter $$\mathcal {O}(N^2)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>O</mml:mi> <mml:mo>(</mml:mo> <mml:msup> <mml:mi>N</mml:mi> <mml:mn>2</mml:mn> </mml:msup> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> .