In a galaxy far, far away there are $225$ inhabited planets. Between some pairs of inhabited planets there is a bidirectional space connection, and it is possible to reach any planet from any other (possibly with several transfers). The influence of a planet is the number of other planets with which this planet has a direct connection. It is known that if two planets are not connected by a direct space flight, they have different influences. What is the smallest number of connections possible under these conditions? Proposed by Arsenii Nikolaev, Bogdan Rublov
Problem
Source: Kyiv City MO 2023 Round 1, Problem 11.5
Tags: combinatorics, graph theory
25.12.2023 20:40
Bump... Anyone?
25.12.2023 22:23
The answer is $1593$ i think??? may be wrong lol Redefine a galaxy as a set of all planets with influence $i$ for some $i$. (We call the collection of all $225$ planets a universe.) Within each galaxy, all planets must be connected (otherwise the unconnected -> different influences is violated). A consequence of this is that in a galaxy where each planet has influence $i$, that galaxy has at most $i$ planets; if there were $i+1$ planets in that galaxy, since all planets are connected, each planet would have no more connections available to connect to other galaxy, violating the rule that the universe is a connected graph. We need at least $21$ galaxies since $20$ galaxies would afford at most $1 + 2 + \dots + 20 = 210$ planets. Since $225$ planets won't fill all $21$ galaxies, we need to choose how to distribute planets between galaxies – this is simple, we want to put as many planets in the lower-connection galaxies as possible. The best way to distribute the planets is thus as follows: $i$ planets in galaxy $i$ for $1 \leq i \leq 19$; $19$ planets in galaxy $20$ and $16$ planets in galaxy $21$. (We can't put $20$ planets in galaxy $20$ and $15$ planets in galaxy $21$, as that would result in the sum of all influences being odd.) Thus, we need at least \[ \frac{1 \cdot 1 + 2 \cdot 2 + \dots + 19 \cdot 19 + 20 \cdot 19 + 21 \cdot 16}{2} = 1593 \]connections.
26.12.2023 06:03
h y p i x e l b e d w a r s