Salvato in:
| Autore principale: | |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | https://arxiv.org/abs/2407.08042 |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866914063022292992 |
|---|---|
| author | Sclosa, Davide |
| author_facet | Sclosa, Davide |
| contents | 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$ 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\geq N+1$ (one extra room for maneuvering is both required and sufficient). For $M\leq N$, we show that the graph has a giant strongly connected component with $Θ(M^N)$ vertices and diameter $\mathcal O(N^2)$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2407_08042 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | If you are the smartest person in the room, you are in the wrong room Sclosa, Davide Combinatorics 05C20, 05C57 (Primary) 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$ 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\geq N+1$ (one extra room for maneuvering is both required and sufficient). For $M\leq N$, we show that the graph has a giant strongly connected component with $Θ(M^N)$ vertices and diameter $\mathcal O(N^2)$. |
| title | If you are the smartest person in the room, you are in the wrong room |
| topic | Combinatorics 05C20, 05C57 (Primary) |
| url | https://arxiv.org/abs/2407.08042 |