Problem A. 722. (April 2018)
A. 722. The Hawking Space Agency operates \(\displaystyle n-1\) space flights between the \(\displaystyle n\) habitable planets of the Local Galaxy Cluster. Each flight has a fixed price which is the same in both directions, and we know that using these flights, we can travel from any habitable planet to any habitable planet.
In the headquarters of the Agency, there is a clearly visible board on a wall, with a portrait, containing all the pairs of different habitable planets with the total price of the cheapest possible sequence of flights connecting them. Suppose that these prices are precisely \(\displaystyle 1,2,\dots,\binom n2\) monetary units in some order. Prove that \(\displaystyle n\) or \(\displaystyle n-2\) is a square number.
(5 pont)
Deadline expired on May 10, 2018.
Sorry, the solution is available only in Hungarian. Google translation
Megoldás. Készítsünk egy gráfot, melynek csúcsai a bolygók és melynek éleire a bolygók közötti járatok árait írjuk. Ez egy \(\displaystyle n\) csúcsú, \(\displaystyle n-1\) élű összefüggő gráf lesz, vagyis fa, és az élekre írt számokat súlyoknak nevezzük.
Azt mondjuk, hogy \(\displaystyle x\) és \(\displaystyle y\) csúcs \(\displaystyle d(x,y)\) távolsága az őket összekötő utak minimális súlyösszege. Gráfok nyelvén a feladat: igazoljuk, hogy ha egy \(\displaystyle n\) csúcsú súlyozott fában (természetesen nemnegatív súlyokat feltételezve) a csúcspárok távolságai éppen \(\displaystyle 1,2,\dots,\binom n2\), akkor \(\displaystyle n\) vagy \(\displaystyle n-2\) négyzetszám.
A bizonyítandó állítás egy másodfokú egyenletből adódik, amit egy szorzatból kapunk, ami a gráf csúcsainak két színnel való színezésével írható fel. Nevezetesen, a fának egy \(\displaystyle v\) csúcsát rögzítve, jelölje \(\displaystyle V_0\) és \(\displaystyle V_1\) rendre a \(\displaystyle v\)-től páros, illetve páratlan távolságú csúcsok halmazát.
Lemma. Ha \(\displaystyle x,y,z\) a fa csúcsai, akkor \(\displaystyle d(x,y)+d(y,z)+d(z,x)\) páros.
Bizonyítás. Tekintsük a megfelelő \(\displaystyle x\)-ből \(\displaystyle y\)-ba, \(\displaystyle y\)-ból \(\displaystyle z\)-be, \(\displaystyle z\)-ből \(\displaystyle x\)-be vezető út egymásutánját, melyek együttes súlyosszege \(\displaystyle d(x,y)+d(y,z)+d(z,x)\). Ezek egy kört alkotnak (ami egy csúcsot akár többször tartalmazhat). Többet is belátunk annál, hogy egy körnek a súlyösszege mindig páros.
A kör éleinek száma szerinti teljes indukcióval belátjuk, hogy egy fában bármely kör minden élt páros sokszor tartalmaz. (Ez egy nyilvánvaló indoklás precízzé tétele lesz.) Ha \(\displaystyle 0\) élből áll a kör, ez világos. Legyenek a körön egymás után következő csúcsok valahonnan indulva \(\displaystyle v_0,v_1,v_2,\dots\), és legyen \(\displaystyle v_k\) az első, amely valamely korábbi csúccsal egyezik. Ekkor \(\displaystyle k\ge 2\) és \(\displaystyle v_k\neq v_{k-1}\). Ha \(\displaystyle v_k\neq v_{k-2}\), akkor találtunk egy legalább \(\displaystyle 3\) hosszú kört. Ilyen nem lehet, hisz akkor eltörölve egy élt a gráfból, továbbra is összefüggő marad (ha egy \(\displaystyle x_1\)-ből \(\displaystyle x_2\)-be utazás áthaladt az élen, a körön megkerülve még mindig el lehet \(\displaystyle x_1\)-ből \(\displaystyle x_2\)-be jutni), márpedig \(\displaystyle n-2\) élű, \(\displaystyle n\) csúcsú összefüggő gráf nincsen: \(\displaystyle <2n\) fokszámösszeg miatt van \(\displaystyle 1\) fokú csúcs; azt eltörölve \(\displaystyle n-3\) élű, \(\displaystyle n-1\) csúcsú összefüggő gráfot kapunk, s a törölgetést folytatva \(\displaystyle 0\) élű, \(\displaystyle 2\) csúcsú összefüggő gráfot kapunk, de ilyen nem létezik. Tehát csak \(\displaystyle v_k=v_{k-2}\) lehet. De ekkor a körből a \(\displaystyle (v_{k-2},v_{k-1})\), \(\displaystyle (v_{k-1},v_k)\) éleket eltörölve, rövidebb körhöz jutunk; az indukciós feltevés szerint a rövidebb körben minden él páros sokszor fordul elő, s mivel két azonos élt töröltünk el, ez a hosszabb körre is teljesül. \(\displaystyle \blacksquare\)
Ha tehát \(\displaystyle x\in V_i\) és \(\displaystyle y\in V_j\), akkor \(\displaystyle 0\equiv d(v,x)+d(x,y)+d(y,v)\equiv i+d(x,y)+j\pmod{2}\) miatt a páros távolságú csúcspárok azonos \(\displaystyle V_i\)-ben, a páratlan távolságúak különböző \(\displaystyle V_i\)-ben találhatók. A páratlan távolságú párokat kétféleképpen megszámolva
\(\displaystyle |V_0|\cdot |V_1|=\sum_{1\le 2k+1\le \binom n2}1=:s.\)
Ha \(\displaystyle |V_0|=m\), akkor innen
\(\displaystyle m(n-m)=s\quad\implies\quad 0=m^2-nm+s\quad\implies\quad \sqrt{D}=\sqrt{n^2-4s}\in\mathbb{Q}.\)
Tehát \(\displaystyle n^2-4s\) négyzetszám. Ha \(\displaystyle \binom{n}{2}\) páros (vagyis \(\displaystyle n\equiv 0,1\pmod{4}\)), akkor \(\displaystyle s=\frac12\binom{n}{2}\) miatt \(\displaystyle n^2-4s=n^2-n(n-1)=n\). Ha pedig \(\displaystyle \binom{n}{2}\) páratlan (vagyis \(\displaystyle n\equiv 2,3\pmod{4}\)), akkor \(\displaystyle s=\frac12(\binom{n}{2}+1)\) miatt \(\displaystyle n^2-4s=n^2-n(n-1)-2=n-2\).
Tehát \(\displaystyle n\) vagy \(\displaystyle n-2\) négyzetszám.
Statistics:
3 students sent a solution. 5 points: Gáspár Attila, Matolcsi Dávid, Schrettner Jakab.
Problems in Mathematics of KöMaL, April 2018