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 <InlineEquation ID="IEq1"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2963_Article_IEq1.gif" Format="GIF" Height="17" Rendition="HTML" Resolution="72" Type="Linedraw" Width="31" /> </InlineMediaObject> <EquationSource Format="TEX">$M^N$</EquationSource> <EquationSource Format="MATHML"><math> <msup> <mi>M</mi> <mi>N</mi> </msup> </math></EquationSource> </InlineEquation> 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 <InlineEquation ID="IEq2"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2963_Article_IEq2.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="86" /> </InlineMediaObject> <EquationSource Format="TEX">$M\ge N+1$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>M</mi> <mo>≥</mo> <mi>N</mi> <mo>+</mo> <mn>1</mn> </mrow> </math></EquationSource> </InlineEquation> (one extra room for maneuvering is both required and sufficient). For <InlineEquation ID="IEq3"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2963_Article_IEq3.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="59" /> </InlineMediaObject> <EquationSource Format="TEX">$M\le N$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>M</mi> <mo>≤</mo> <mi>N</mi> </mrow> </math></EquationSource> </InlineEquation>, we show that the graph has a giant strongly connected component with <InlineEquation ID="IEq4"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2963_Article_IEq4.gif" Format="GIF" Height="21" Rendition="HTML" Resolution="72" Type="Linedraw" Width="56" /> </InlineMediaObject> <EquationSource Format="TEX">$\Theta (M^N)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="normal">Θ</mi> <mo stretchy="false">(</mo> <msup> <mi>M</mi> <mi>N</mi> </msup> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> vertices and diameter <InlineEquation ID="IEq5"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2963_Article_IEq5.gif" Format="GIF" Height="20" Rendition="HTML" Resolution="72" Type="Linedraw" Width="50" /> </InlineMediaObject> <EquationSource Format="TEX">$\mathcal {O}(N^2)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="script">O</mi> <mo stretchy="false">(</mo> <msup> <mi>N</mi> <mn>2</mn> </msup> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>.

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

期刊论文
出版模式：

开放获取
发表日期：

2025年9月19日

查看全文

Davide Sclosa

摘要

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$ $M^{N}$ 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$ $M \geq N + 1$ (one extra room for maneuvering is both required and sufficient). For $M\le N$ $M \leq N$ , we show that the graph has a giant strongly connected component with $\Theta (M^N)$ $Θ (M^{N})$ vertices and diameter $\mathcal {O}(N^2)$ $O (N^{2})$ .