A B. 5515. feladat (2026. február)

B. 5515. Fel lehet-e írni egy szabályos \(\displaystyle 1000\)-szög minden csúcsára egy-egy számjegyet úgy, hogy a \(\displaystyle 000\), \(\displaystyle 001\), \(\displaystyle 002\), \(\displaystyle \ldots\), \(\displaystyle 998\), \(\displaystyle 999\) számok mindegyike összeolvasható legyen valamely három egymást követő csúcsról az óramutató irányában haladva?

Beke Csongor (Cambridge) ötletéből

(5 pont)

A beküldési határidő 2026. március 10-én LEJÁRT.

Megoldás. A feladat során az első 100 természetes számot \(\displaystyle 00,01,...,99\) alakban ,,kiterjesztett'' kétjegyű számokként fogjuk kezelni, azaz például a \(\displaystyle 02\) szám tízes helyiértékén a \(\displaystyle 0\), az egyes helyiértékén pedig a \(\displaystyle 2\) számjegy szerepel. Készítsük el azt az irányított gráfot, amelynek 100 darab csúcsa a \(\displaystyle 00\), \(\displaystyle 01\), \(\displaystyle 02\), \(\displaystyle ...\), \(\displaystyle 98\) és \(\displaystyle 99\) számok, és az \(\displaystyle u=\overline{ab}\) csúcsból pontosan akkor mutat (irányított) él a \(\displaystyle v=\overline{cd}\) csúcsba (ahol \(\displaystyle a,b,c\) és \(\displaystyle d\) számjegyek), ha \(\displaystyle b=c\), azaz, ha az \(\displaystyle u\) csúcsnál lévő szám egyes helyiértékén lévő számjegy megegyezik a \(\displaystyle v\) csúcsnál lévő szám tízes helyiértékén lévő számjeggyel. Továbbá az éleket címkézzük meg az alábbi módon (kiterjesztett) háromjegyű számokkal: az \(\displaystyle \overline{ab}\)-ből a \(\displaystyle \overline{bc}\)-be mutató él címkéje legyen \(\displaystyle \overline{abc}\). Például, az \(\displaystyle u=15\) csúcsból minden olyan csúcsba vezet él, amelynél a tízes helyiértékén \(\displaystyle 5\) áll (\(\displaystyle 50,51,...,59\)), míg az \(\displaystyle u\)-ba azon csúcsokból vezet él, ahol az egyes helyiértéken \(\displaystyle 1\) áll (\(\displaystyle 01,11,...,91\)), továbbá például a \(\displaystyle 15\) csúcsból az \(\displaystyle 59\)-be mutató irányított él címkéje \(\displaystyle 159\).

A százcsúcsú gráfunkat megvizsgálva világos, hogy bármely csúcs befoka és kifoka is 10 (azaz bármely csúcsba pontosan 10 él vezet, és minden csúcsból 10 él vezet kifele is), ami páros szám. Valamint pontosan 1000 darab él van, a címkéik mind különböznek, és rendre a \(\displaystyle 000, 001,...,999\) számok. Továbbá bármely \(\displaystyle \overline{ab}\) csúcs esetén az \(\displaystyle \overline{ab}\) csúcsból legfeljebb kettő hosszú irányított úton elérhető bármely tőle különböző \(\displaystyle \overline{cd}\) csúcs az alábbi módon: \(\displaystyle \overline{ab} \rightarrow \overline{bc} \rightarrow \overline{cd}\) (és ez az út kettő helyett egy hosszú, ha \(\displaystyle b=c\)), így a gráfunk erősen összefüggő. Emiatt a gráfunkban van irányított Euler-kör(séta), azaz olyan kör(séta), amely a gráfunk minden egyes irányított élén pontosan egyszer megy át (egy-egy csúcson pedig pontosan tízszer).

Tekintsünk egy ilyen \(\displaystyle \overline{a_0a_1} \rightarrow \overline{a_1a_2} \rightarrow \overline{a_2a_3} \rightarrow ... \rightarrow \overline{a_{999}a_{0}} \rightarrow \overline{a_0a_1}\) Euler-kört, és írjuk fel az \(\displaystyle a_0, a_1,...,a_{999}\) számjegyeket ebben a sorrendben az 1000-szögünk egymást követő csúcsaira. Mivel az \(\displaystyle a_i, a_{i+1}, a_{i+2}\) számokat (az indexeket \(\displaystyle \pmod{1000}\) kezelve) ebben a sorrendben összeolvasva éppen az \(\displaystyle \overline{a_ia_{i+1}} \rightarrow \overline{a_{i+1}a_{i+2}} \) él címkéjét kapjuk ez az előzőek alapján azt jelenti, hogy valóban igaz az, hogy a \(\displaystyle 000\), \(\displaystyle 001\), ..., \(\displaystyle 999\) számok mindegyike összeolvasható a kívánt módon. Ezzel a feladatot megoldottuk.

Statisztika:

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

A KöMaL 2026. februári matematika feladatai