 |
Az A. 722. feladat (2018. április) |
A. 722. A Hawking Űrtársaság a Lokális Galaxiscsoport \(\displaystyle n\) élhető bolygója között \(\displaystyle n-1\) darab rögzített árú járatot üzemeltet (az ár oda és vissza mindig megegyezik). Tudjuk, hogy e járatokkal bármelyik élhető bolygóról bármelyik élhető bolygóra el lehet jutni.
Az Űrtársaság központjának falán egy jól látható tábla található, melyen egy arckép mellett fel van tüntetve bármely két különböző élhető bolygóhoz az őket összekötő legolcsóbb járatsorozat ára. Tegyük fel, hogy ezen a táblán éppen az \(\displaystyle 1,2,\dots,\binom n2\) egységnyi pénzmennyiségek szerepelnek valamilyen sorrendben. Igazoljuk, hogy \(\displaystyle n\) vagy \(\displaystyle n-2\) négyzetszám.
(5 pont)
A beküldési határidő 2018. május 10-én LEJÁRT.
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.
Statisztika:
3 dolgozat érkezett. 5 pontot kapott: Gáspár Attila, Matolcsi Dávid, Schrettner Jakab.
A KöMaL 2018. áprilisi matematika feladatai