 |
A B. 5454. feladat (2025. április) |
B. 5454. Az \(\displaystyle a_1\), \(\displaystyle a_2\), \(\displaystyle a_3\), \(\displaystyle \ldots\), \(\displaystyle a_{2024}\), \(\displaystyle a_{2025}\) pozitív egészeket úgy választottuk ki, hogy az \(\displaystyle \frac{a_1}{a_2}\), \(\displaystyle \frac{a_2}{a_3}\), \(\displaystyle \frac{a_3}{a_4}\), \(\displaystyle \ldots\), \(\displaystyle \frac{a_{2024}}{a_{2025}}\) törtek páronként különböző értékűek legyenek. Legalább hány különböző van a kiválasztott számok között?
Javasolta: Sztranyák Attila (Budapest)
(4 pont)
A beküldési határidő 2025. május 12-én LEJÁRT.
Megoldás. Jelölje \(\displaystyle n\) az \(\displaystyle a_1, a_2, \ldots, a_{2025}\) sorozatban előforduló különböző értékek számát (másképp mondva az \(\displaystyle \{ a_1, a_2, \ldots a_{2025} \}\) halmaz elemszámát). Hányféle lehet egy \(\displaystyle \frac{a_i}{a_j}\) tört értéke? Ha \(\displaystyle a_i \neq a_j\), akkor az \(\displaystyle n\)-féleképpen választható \(\displaystyle a_i\)-hoz \(\displaystyle (n-1)\)-féleképpen választhatunk \(\displaystyle a_j\)-t. Ha \(\displaystyle a_i = a_j\), akkor \(\displaystyle \frac{a_i}{a_j} = 1\). Tehát legfeljebb \(\displaystyle n(n-1)+1\) különböző értéket vehet fel egy \(\displaystyle \frac{a_i}{a_j}\) tört.
Következésképpen \(\displaystyle n(n-1)+1 \geq 2024\) (ennyi törtet soroltunk fel), azaz \(\displaystyle n \geq 46\).
Az alábbiakban megmutatjuk, hogy \(\displaystyle n = 46\) lehetséges.
Legyenek \(\displaystyle p_1,p_2,\ldots,p_{46}\) különböző prímszámok (lehetnek mind az első 2025 pozitív egész közül, hiszen 306 prímszám van 1 és 2025 között, ld. pl. https://en.wikipedia.org/wiki/List_of_prime_numbers).
Legyen \(\displaystyle G\) egy 46 csúcsú teljes irányított gráf (azaz bármely két csúcs között húzzunk be mindkét irányba egy-egy élt, így összesen \(\displaystyle 46 \cdot 45 = 2070\) éle lesz a gráfnak), melynek csúcsaihoz hozzárendeltük a \(\displaystyle p_1,p_2,\ldots,p_{46}\) prímeket.
Tekintsük azon \(\displaystyle a_1,a_2,\ldots,a_{t}\) sorozatokat, amelynek minden eleme a \(\displaystyle \{p_1,\ldots,p_{46} \}\) halmazból való, méghozzá úgy, hogy \(\displaystyle a_i\) és \(\displaystyle a_{i+1}\) semmilyen \(\displaystyle i\)-re ne egyezzen meg. Az ilyen sorozatokat a \(\displaystyle G\) gráfban könnyen reprezentálhatjuk egy sétával. (Egy irányított gráfban sétának olyan \(\displaystyle v_1,v_2, \ldots, v_t\) csúcssorozatot nevezünk, ahol minden \(\displaystyle i\)-re \(\displaystyle v_i\)-ből \(\displaystyle v_{i+1}\)-be vezet egy irányított él – ilyenkor a séta élei a \(\displaystyle v_i \rightarrow v_{i+1}\) irányított élek. A \(\displaystyle v_1,v_2,\ldots,v_n\) sorozatban többször is szerepelhet ugyanaz a csúcs.)
A feladatban megfogalmazott feltétel, mely szerint az \(\displaystyle \frac{a_1}{a_2},\frac{a_2}{a_3},\frac{a_3}{a_4},\ldots,\frac{a_{2024}}{a_{2025}}\) törtek páronként különböző értékűek, éppen annak felel meg a gráf nyelvén, hogy minden élt legfeljebb egyszer használunk ebben a sétában. Itt fontos, hogy különböző élek mindig különböző értékű törteket reprezentálnak: ez azért teljesül, mert a csúcsok különböző prímszámoknak felelnek meg.
Elegendő tehát találnunk a \(\displaystyle 46\) csúcsú teljes irányított gráfban egy legalább \(\displaystyle 2025\) csúcsú (azaz \(\displaystyle 2024\) élű) sétát, amely minden élt legfeljebb egyszer használ.
Ténylegesen meg is konstruálhatunk egy ilyen sétát, vagy akár az irányított gráfok bejárásaira vonatkozó Euler-féle tételre hivatkozva is beláthatjuk a létezését.
Konstrukció. Sokféle lehetséges konstrukció közül mutatunk egyet. Az alábbi módon sétáljunk:
$$\begin{eqnarray*} \underbrace{p_1 \rightarrow p_3 \rightarrow p_1 \rightarrow p_4 \rightarrow p_1 \rightarrow \ldots \rightarrow p_1 \rightarrow p_{46} \rightarrow p_1}_{1.~\text{ fázis}} \rightarrow \underbrace{ p_2 \rightarrow p_4 \rightarrow p_2 \rightarrow \ldots \rightarrow p_2 \rightarrow p_{46} \rightarrow p_2}_{2.~\text{ fázis}} \rightarrow \underbrace{p_3 \rightarrow \ldots \rightarrow p_3}_{3.~\text{ fázis}} \rightarrow \ldots \\ \ldots \rightarrow \underbrace{p_{43} \rightarrow p_{45} \rightarrow p_{43} \rightarrow p_{46} \rightarrow p_{43}}_{43.~\text{ fázis}} \rightarrow \underbrace{p_{44} \rightarrow p_{46} \rightarrow p_{44}}_{44.~\text{ fázis}} \rightarrow p_{45} \end{eqnarray*}$$A \(\displaystyle k\)-edik fázis úgy épül fel, hogy, \(\displaystyle i \in \{k+2,k+3\ldots 46\}\)-ra egymás után fűzzük a \(\displaystyle p_k \rightarrow p_i \rightarrow p_k\) oda-vissza élpárokat.
Így tetszőleges \(\displaystyle p_i \rightarrow p_j\) irányított él sorra kerül egyszer az \(\displaystyle i.\) és a \(\displaystyle j.\) fázis egyikében (a kisebb indexűben), kivéve azok, amelyekre \(\displaystyle |i-j| = 1\). A 90 darab kivételes élből is sorra kerül 43 a fázisok közti átmeneteknél, és még 1 a végén, így csak 46 él marad ki. Így a séta során \(\displaystyle 46\cdot45 - 46 = 46 \cdot 44 = 45^2-1 = 2024\) élt érintettünk. (A megadott séta végéhez fűzve a \(\displaystyle p_{45} \rightarrow p_{46} \rightarrow p_{45} \rightarrow p_{44} \rightarrow \ldots p_{2} \rightarrow p_1\) sorozatot a gráf összes élét be tudnánk járni.)
Bizonyítás Euler-körsétával. A \(\displaystyle G\) gráf minden csúcsába 45 irányított él érkezik és \(\displaystyle 45\) irányított él indul onnan, azaz befoka és kifoka is 45. Ismert tétel, hogy ha egy összefüggő irányított gráfban minden csúcs befoka megegyezik a kifokával, akkor van benne úgynevezett Euler-körséta, azaz olyan séta, amely a gráf összes élét pontosan egyszer használja. A gráfnak összesen \(\displaystyle 46 \cdot 45 = 2070 \geq 2024\) éle van, tehát így bőven elég hosszú sétát találtunk.
Megjegyzés. Az Euler-körséta elnevezés a königsbergi hidak problémájával való rokonságra utal. Az általunk használt tétel bizonyítása Euler koránál későbbi: Carl Hierholzer német matematikus 1873-ban publikálta a tétel irányítatlan verzióját bizonyító eljárást, amely könnyen alkalmazható az irányított gráfokra is, ld. pl. https://en.wikipedia.org/wiki/Eulerian_path.
Statisztika:
A KöMaL 2025. áprilisi matematika feladatai