Középiskolai Matematikai és Fizikai Lapok
Informatika rovattal
Kiadja a MATFUND Alapítvány
Már regisztráltál?
Új vendég vagy?

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:

Az A. 839. feladat értékelése még nem fejeződött be.


A KöMaL 2022. decemberi matematika feladatai