 |
A B. 4997. feladat (2018. december) |
B. 4997. Tekintsük egész együtthatós polinomok következő \(\displaystyle p_n(x)\) sorozatát: legyen \(\displaystyle p_0(x)=0\), \(\displaystyle p_1(x)=1\), és minden \(\displaystyle n\ge 2\) esetén
\(\displaystyle p_n(x)=p_{n-1}(x)+x\cdot p_{n-2}(x). \)
Bizonyítsuk be, hogy ha valamilyen \(\displaystyle n\), \(\displaystyle m\) pozitív egészekre egy \(\displaystyle f(x)\) polinom osztója a \(\displaystyle p_n(x)\) és \(\displaystyle p_m(x)\) polinomnak, akkor a \(\displaystyle p_{(m,n)}(x)\) polinomnak is osztója.
(\(\displaystyle (n,m)\) jelöli az \(\displaystyle n\) és \(\displaystyle m\) legnagyobb közös osztóját. A \(\displaystyle P(x)\) polinom osztója a \(\displaystyle Q(x)\) polinomnak, ha van olyan \(\displaystyle R(x)\) valós együtthatós polinom, amelyre \(\displaystyle Q(x)= P(x)R(x)\).)
(6 pont)
A beküldési határidő 2019. január 10-én LEJÁRT.
Megoldás. Először néhány egyszerű észrevételt igazolunk.
Teljes indukcióval adódik a rekurzió segítségével, hogy \(\displaystyle n\geq 1\) esetén \(\displaystyle p_n(x)\) olyan egész együtthatós polinom, melynek konstans tagja 1.
Mivel \(\displaystyle 0<n\)-re \(\displaystyle p_n\) konstans tagja 1, ezért ekkor \(\displaystyle x\nmid p_n(x)\). Ebből teljes indukcióval következik, hogy két, a sorozatban egymást követő polinom mindig relatív prím: legnagyobb közös osztójuk konstans polinom. Ha ugyanis \(\displaystyle f(x)\mid p_{n-1} (x)\) és \(\displaystyle f(x)\mid p_{n}(x)\), akkor a rekurzió alapján \(\displaystyle f(x)\mid xp_{n-2}(x)\), amiből \(\displaystyle x\nmid f(x)\) miatt (ami teljesül, hiszen \(\displaystyle x\) nem osztja a \(\displaystyle p_n(x)\) polinomokat \(\displaystyle n>1\) mellett) \(\displaystyle f(x)\mid p_{n-2}\) következik. Ezt a lépést ismételgetve pedig végül \(\displaystyle f(x)\mid p_1(x)=1\)-hez jutunk. Tehát a sorozat szomszédos tagjainak legnagyobb közös osztója konstans.
Először megmutatjuk, hogy \(\displaystyle 2\leq k\leq n-1\) esetén
| \(\displaystyle p_n(x)=p_{k}(x)p_{n-k+1}(x)+(p_{k+1}(x)-p_k(x))p_{n-k}(x). \) | \(\displaystyle {(*)}\) |
Ha \(\displaystyle k=2\), akkor a feltétel a megadott rekurzió alapján teljesül, hiszen \(\displaystyle p_3(x)=x+1\), és így valóban
\(\displaystyle p_{2}(x)p_{n-1}(x)+(p_{3}(x)-p_2(x))p_{n-2}(x)=p_{n-1}(x)+xp_{n-2}(x)=p_n(x).\)
Ha az állítást \(\displaystyle k\)-ra már igazoltuk, akkor a rekurziót használva
\(\displaystyle p_n(x)=p_{k}(x)p_{n-k+1}(x)+(p_{k+1}(x)-p_k(x))p_{n-k}(x)=\)
\(\displaystyle =p_{k}(x)(p_{n-k}(x)+xp_{n-k-1}(x))+(p_{k+1}(x)-p_k(x))p_{n-k}(x)=\)
\(\displaystyle =p_{k+1}(x)p_{n-k}(x)+xp_k(x)p_{n-k-1}(x)=p_{k+1}(x)p_{n-k}(x)+(p_{k+2}(x)-p_{k+1}(x))p_{n-k-1}(x),\)
vagyis az állítás \(\displaystyle k+1\)-re is teljesül. Tehát indukcióval következik, hogy minden \(\displaystyle 2\leq k\leq n-1\) mellett teljesül a \(\displaystyle (*)\) állítás.
Most megmutatjuk, hogy ha \(\displaystyle f(x)\) osztója a \(\displaystyle p_n(x)\) és \(\displaystyle p_m(x)\) polinomoknak, és mondjuk \(\displaystyle n\geq m\), akkor \(\displaystyle f(x)\) osztója a \(\displaystyle p_{n-m}(x)\) polinomnak is. Innen az állítás már következik, ugyanis az euklideszi algoritmust követve ilyen lépésekkel előbb-utóbb eljutunk oda, hogy \(\displaystyle f(x)\) osztója a \(\displaystyle p_{(m,n)}(x)\) polinomnak is.
Írjuk fel \(\displaystyle (*)\)-ot \(\displaystyle k=n-m\) választással:
\(\displaystyle p_n(x)=p_{n-m}(x)p_{m+1}(x)+(p_{n-m+1}(x)-p_{n-m}(x))p_{m}(x).\)
Ebből leolvasható, hogy \(\displaystyle f(x)\) osztója a \(\displaystyle p_n(x)\) és \(\displaystyle p_m(x)\) polinomoknak, akkor \(\displaystyle f(x)\) osztója a \(\displaystyle p_{n-m}(x)p_{m+1}(x)\) polinomnak is.
Most felhasználjuk, hogy \(\displaystyle p_m\) és \(\displaystyle p_{m+1}\) relatív prímek, és így \(\displaystyle f(x)\mid p_m(x)\) miatt \(\displaystyle f\) és \(\displaystyle p_{m+1}\) is azok: legnagyobb közös osztójuk konstans. Így \(\displaystyle f(x)\mid p_{n-m}(x)p_{m+1}(x)\) oszthatóságból következik, hogy \(\displaystyle f(x)\mid p_{n-m}(x)\) is teljesül.
Ebből pedig a korábbiak szerint az euklideszi algoritmust követve adódik, hogy \(\displaystyle f(x)\) valóban osztója \(\displaystyle p_{(m,n)}(x)\) polinomnak is.
Statisztika:
24 dolgozat érkezett. 6 pontot kapott: Baski Bence, Beke Csongor, Bencsik Ádám, Dobák Dániel, Győrffi Ádám György, Kerekes Anna, Kovács 129 Tamás, Nagy Nándor, Pooya Esmaeil Akhoondy, Soós 314 Máté, Stomfai Gergely, Szabó 417 Dávid, Szabó 991 Kornél, Tóth 827 Balázs, Velich Nóra, Weisz Máté, Zsigri Bálint. 5 pontot kapott: Várkonyi Zsombor. 4 pontot kapott: 2 versenyző. 3 pontot kapott: 1 versenyző. 2 pontot kapott: 2 versenyző. 0 pontot kapott: 1 versenyző.
A KöMaL 2018. decemberi matematika feladatai