|
Feladat: |
F.2872 |
Korcsoport: 18- |
Nehézségi fok: könnyű |
Megoldó(k): |
Barát János , Faragó Gergely , Futó Gábor , Imreh Csanád , Kerekes Balázs , Németh Ákos , Párniczky Benedek , Szeidl Ádám , Tóth Csaba D. , Ungár György |
Füzet: |
1992/május,
200 - 202. oldal |
PDF | MathML |
Témakör(ök): |
Összefüggések binomiális együtthatókra, Egészrész, törtrész függvények, Oszthatóság, Számelméleti függvények, Feladat |
Hivatkozás(ok): | Feladatok: 1991/november: F.2872 |
|
A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre. I. megoldás. Ha akkor az állítás az együtthatónak -ra való, ismert kiterjesztéséből következik. Legyen Ekkor és amiből
| | (1) | Mivel relatív prímek, a bal oldalon álló szorzat csak úgy lehet osztható -gyel, ha osztható -gyel. Megjegyzések 1. Az (1) azonosságot esetén nem írhatjuk fel, ezért kellett ezt az esetet külön megvizsgálni. 2. (1)-et a következőképpen is átrendezhetjük: Eszerint két egész szám különbsége. Megjegyzés. A számot az -edik Catalan-számnak nevezik. Többféle kombinatorikai jelentése van: ennyiféleképpen lehet zárójelezni egy -tagú összeget, ennyiféleképpen lehet egy konvex -szöget átló behúzásával háromszögekre bontani stb. Ha bevezetjük a jelölést, akkor teljesül a következő rekurzió: | | Az állítás ebből is következik, bár már a rekurzió bizonyítása is hosszabb, mint maga a megoldás. II. megoldás. Bebizonyítjuk, hogy tetszőleges prímszámra prímtényezős felbontásában a kitevője legalább akkora, mint az prímtényezős felbontásában. (Ez ekvivalens az állítással.) Legyen kitevője az felbontásában. Ismeretes, hogy kitevője illetve prímtényezős felbontásában
| | az egész részét jelöli.) Azt kell igazolnunk, hogy Ehhez megmutatjuk, hogy
Ha ezeket az egyenlőtlenségeket összeadjuk ( mindazon értékeire, amelyekre éppen -t kapjuk. Legyen Mivel osztója -nek, is osztója -nek. Legyen azaz Az előbbiek szerint egész szám, ezért
Ezzel (3)-at igazoltuk. Mivel pedig tetszőleges valós számra, (4) is igaz. Ezzel az állítást bebizonyítottuk.
Szeidl Ádám (Miskolc, Földes F. Gimn., II. o. t.) |
|