Az A. 839. feladat (2022. december)

A. 839. Adott egy véges, egyszerű, irányítatlan gráf. Anna minden élre pozitív valós számokat ír úgy, hogy bármely csúcsra a csúcsba befutó élekre írt számok összege kisebb egynél. Balázs szeretné úgy megszámozni a csúcsokat nemnegatív valós számokkal, hogy ha tetszőleges \(\displaystyle v\) csúcsra a \(\displaystyle v_0\) számot írta, és a csúcsból kiinduló élekre Anna rendre az \(\displaystyle e_1,e_2, \dots, e_k\) számokat írta, továbbá ezen élek másik végein rendre a \(\displaystyle v_1, v_2, \dots, v_k\) számok szerepelnek, akkor \(\displaystyle v_0=\sum\limits_{i=1}^{k}e_iv_i+2022\) teljesüljön. Mutassuk meg, hogy Balázs mindig meg tudja így számozni a csúcsokat függetlenül a gráftól és az Anna által megadott számozástól.

Javasolta: Varga Boldizsár (Verőce)

(7 pont)

A beküldési határidő 2023. január 10-én LEJÁRT.

Egészítsük ki a gráfot úgy, hogy minden \(\displaystyle v\) csúcshoz felveszünk egy új \(\displaystyle v'\) pontot, és behúzzuk a \(\displaystyle vv'\) élet. Írjuk erre az élre azt a pozitív valós \(\displaystyle e_v\) számot, mellyel a \(\displaystyle v\) csúcsból induló éleken lévő számok összege éppen \(\displaystyle 1\) lesz. Továbbá a \(\displaystyle v'\) csúcshoz rendeljük hozzá a \(\displaystyle c_{v'}=\frac{2022}{e_v}\) értéket. Jelölje az eredeti csúcsok halmazát \(\displaystyle V\), az újonnan felvett csúcsok halmazát pedig \(\displaystyle V'\).

Vegyünk egy tetszőleges \(\displaystyle v \in V\) csúcsot, és tekintsük a következő véletlen bolyongást. Kezdetben a \(\displaystyle v\) csúcsból indulunk, és minden lépésben ha egy \(\displaystyle V'\)-beli csúcsban vagyunk, akkor véget ér a bolyongás, különben pedig átmegyünk egy szomszédos csúcsba a belőle kiinduló éleken lévő valószínűségek szerint. Ez értelmes a kiegészített gráfban, mivel minden \(\displaystyle u \in V\) csúcsban \(\displaystyle 1\) a belőle induló éleken lévő számok összege. A bolyongás végén megkapjuk az befejező \(\displaystyle u' \in V'\) csúcshoz rendelt \(\displaystyle c_{u'}\) értéket. Jelölje \(\displaystyle x_v\) a \(\displaystyle v\)-ből induló bolyonás végén kapott mennyiség várható értékét. Azt állítjuk, hogy ha Balázs minden csúcsba az \(\displaystyle x_v\) értéket írja, akkor megfelelő hozzárendelést kap.

Először is gondoljuk meg, hogy ez a definíció értelmes, és az \(\displaystyle x_v\) várható értékek tényleg léteznek. (Ez nem magától értetődő, például ha a bolyongás pozitív valószínűséggel nem ér véget véges sok lépés alatt, akkor nem értelmes a definíció.) Rögzítsük a \(\displaystyle v \in V\) kiinduló csúcsot. Legyen \(\displaystyle a\) a minimális érték az \(\displaystyle e_u\) számok közül (\(\displaystyle u \in V\)). A feladat feltétele szerint \(\displaystyle e_u\) pozitív minden \(\displaystyle u \in V\) esetén, így \(\displaystyle a>0\). A bolyongás minden lépésében legalább \(\displaystyle a\) valószínűséggel véget ér, így annak a valószínűsége, hogy több, mint \(\displaystyle k\) lépésig tart legfeljebb \(\displaystyle (1-a)^k\). Ez tart 0-hoz, ahogy \(\displaystyle k\) egyre nagyobb, így 1 valószínűséggel véges sok lépésben véget ér a bolyongás. Ekkor meg tudjuk határozni, hogy melyik \(\displaystyle u' \in V'\) csúcsra mekkora a valószínűsége, hogy ott fejeződik be a séta, azaz tényleg értelmes az \(\displaystyle x_v\) várható értéket.

Induljunk ki a \(\displaystyle v\) csúcsból, legyenek \(\displaystyle v_1\), \(\displaystyle v_2,\ldots\), \(\displaystyle v_l\) a \(\displaystyle v\) csúcs \(\displaystyle V\)-beli szomszédai, és legyen rendre \(\displaystyle e_1\), \(\displaystyle e_2,\ldots\), \(\displaystyle e_l\) a \(\displaystyle v\)-t velük összekötő élen lévő érték. Vizsgáljuk meg az \(\displaystyle x_v\) várható értéket egy lépés után. \(\displaystyle e_v\) valószínűséggel \(\displaystyle v'\)-be lépünk, ekkor biztosan \(\displaystyle c_{v'}\)-t kapunk. Ha pedig valamelyik \(\displaystyle v_i\) csúcsra lépünk (\(\displaystyle 1 \leq i \leq l\)), aminek \(\displaystyle e_i\) a valószínűsége, akkor várhatóan \(\displaystyle x_{v_i}\)-t fogunk kapni. Ezek alapján

\(\displaystyle x_v=e_vc_{v'}+e_1x_1+e_2x_2+\ldots+e_lv_l=2022+\sum_{i=1}^{l}e_ix_i,\)

és éppen ezt akartuk bizonyítani.

Statisztika:

14 dolgozat érkezett.
7 pontot kapott:	Diaconescu Tashi, Lovas Márton, Móricz Benjámin, Nádor Benedek, Németh Márton, Seres-Szabó Márton, Sida Li, Simon László Bence, Szakács Ábel, Sztranyák Gabriella, Varga Boldizsár, Wiener Anna.
6 pontot kapott:	Molnár-Szabó Vilmos.
4 pontot kapott:	1 versenyző.

A KöMaL 2022. decemberi matematika feladatai