Az A. 851. feladat (2023. április)

A. 851. Legyenek $\displaystyle k$, $\displaystyle l$ és $\displaystyle m$ pozitív egész számok. Legyen $\displaystyle ABCDEF$ egy olyan középpontosan szimmetrikus hatszög, melynek szögei mind $\displaystyle 120^{\circ}$-osak, oldalainak hosszai pedig $\displaystyle AB=k$, $\displaystyle BC=l$ és $\displaystyle CD=m$. Jelölje $\displaystyle f(k,l,m)$ azt, hogy hányféle módon lehet az $\displaystyle ABCDEF$ hatszöget átfedés nélkül lefedni olyan egységoldalú rombuszokkal, melyek egyik szöge $\displaystyle 120^{\circ}$.

Bizonyítsuk be, hogy rögzített $\displaystyle l$ és $\displaystyle m$ mellett létezik olyan $\displaystyle g_{l,m}$ polinom, melyre minden pozitív egész $\displaystyle k$ esetén $\displaystyle f(k,l,m)=g_{l,m}(k)$, és állapítsuk meg $\displaystyle g_{l,m}$ fokát $\displaystyle l$ és $\displaystyle m$ függvényében.

Javasolta: Gyenes Zoltán (Budapest)

(7 pont)

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

Tegyük fel, hogy ki van parkettázva valahogy a hatszög, és tekintsük a két szemközti, $\displaystyle k$ hosszú oldalt. Látható, hogy van $\displaystyle k$ darab út az egyik oldalról a másikra úgy, hogy a rombuszok azon középvonalain haladunk végig, melyek két olyan szemközti felezőpontot kötnek össze, amik párhuzamosak a $\displaystyle k$ hosszú oldallal. Ezek az utak nem keresztezhetik egymást, így minden ilyen út éppen $\displaystyle l$-szer lép az egyik, és $\displaystyle m$-szer a másik irányba. Tekintsünk úgy a hatszögre, hogy a $\displaystyle k$ hosszú oldal vízsintes, és nevezzük az utakon a kétféle irányú lépéseket jobb (J) és bal (B) lépéseknek, ahol mindig $\displaystyle l$ darab J lépés van. Ekkor az, hogy nem metszik egymást éppen azt jelenti, hogy ha tekintünk egy utat, akkor minden $\displaystyle t$-re az első $\displaystyle t$ lépésben ez az út legfeljebb annyiszor léphet jobbra, mint a tőle jobbra lévő út. Azaz ha egy $\displaystyle k$ soros és $\displaystyle l+m$ oszlopos táblázat soraiba egymás alá beírjuk a J-B sorozatokat, amik leírják az utakat, akkor tetszőleges két sorra és $\displaystyle t$ számra igaznak kell lennie, hogy a lentebbi sorban legalább annyi J van az első $\displaystyle t$ helyen, mint a fentebbiben. Megfordítva, könnyen látható, hogy egy ilyen táblázathoz olyan utak tartoznak, amik nem metszik egymást, és ilyen utak egyértelműen meghatároznak egy romboszukkal parkettázást. Így a feladat ekvivalens azzal, hogy az ilyen táblázatok számáról bizonyítsuk be, hogy polinom $\displaystyle k$-ban.

Tekintsük azokat a $\displaystyle l+m$ hosszú J-B sorozatokat, melyekben pontosan $\displaystyle l$ darab J van. Definiáljunk ezeken egy részbenrendezést, egy sorozat akkor kisebb, mint egy másik, ha a táblázatban kerülhet fölé (azaz tetszőleges kezdőszeletben legfeljebb annyi J van, mint a másikban). Világos, hogy ez a tulajdonság tranzitív. Legyen $\displaystyle P$ az így kapott részbenrendezett halmaz. Ekkor a megfelelő táblázatokat le tudjuk számolni a következőképpen: Vegyünk egy tetszőleges nem üres $\displaystyle L$ láncot $\displaystyle P$-ből, tegyük fel, hogy $\displaystyle s_L$ elemből áll. Ekkor azon táblázatok, amikben pontosan ezek a sorok szerepelnek éppen $\displaystyle \binom{k-1}{s_L-1}$, mivel a részbenrendezés megadja, hogy milyen sorrendben következnek a sorok, így csak azt dönthetjük el, hogy melyikből hány legyen, így $\displaystyle s_L-1$ elválasztó vonalat kell behúznunk a $\displaystyle k$ sor közé. A feltétel szerint láncnak kell lennie azon J-B sorozatok halmazának $\displaystyle P$-ben, amik egy táblázatban szerepelnek, így az összes $\displaystyle P$-beli $\displaystyle L$ láncra összegezve a fenti $\displaystyle \binom{k-1}{s_L-1}$ kifejezést éppen a keresett mennyiséget kapjuk.

Mivel $\displaystyle l$ és $\displaystyle m$ fix, így rögzített mennyiségű $\displaystyle \binom{k-1}{s_L-1}$ alakú tagot adunk össze, amik $\displaystyle k$-ban $\displaystyle s_L-1$ fokú polinomok. Így $\displaystyle f(k,l,m)$ valóban polinom $\displaystyle k$-ban, melynek foka a leghosszabb lánc hossza $\displaystyle P$-ben mínusz 1. Minden sorozathoz rendeljük hozzá, hogy hány (J,B) pár van, melyre a J megelőzi a B-t. Ez az $\displaystyle m$ darab B-vel kezdődő sorozatra 0, és az $\displaystyle m$ darab B-re végződő sorozatra $\displaystyle lm$, minden más sorozatra ezek közé esik. Látható, hogy ha egy sorozat $\displaystyle P$-ben nagyobb, mint egy másik, akkor ez a hozzárendelt érték is nagyobb, így egy lánc hossz legfeljebb $\displaystyle lm+1$ lehet. Ez pedig tényleg el is érhető, például ha kiindulunk az $\displaystyle m$ darab B-vel kezdődő sorozatból, majd a jobb oldali B-t egyesével a végére toljuk, utána a következő B-t, és így tovább, míg el nem jutunk addig, hogy minden B a sorozat végén van. Tehát $\displaystyle lm+1$ a leghosszabb lánc hossza $\displaystyle P$-ben, így $\displaystyle f(k,l,m)$ egy $\displaystyle lm$ fokú polinom $\displaystyle k$-ban.

Statisztika:

5 dolgozat érkezett.
7 pontot kapott:	Sida Li, Varga Boldizsár.
5 pontot kapott:	1 versenyző.
2 pontot kapott:	1 versenyző.
0 pontot kapott:	1 versenyző.

A KöMaL 2023. áprilisi matematika feladatai