Cím:	Gyertek bizonyítsuk be Csebisev tételét 3.
Szerző(k):	Kalmár László
Füzet:	1948/szeptember, 176 - 182. oldal	PDF  |  MathML
Témakör(ök):	Szakmai cikkek

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. A 4. számban kitűzött feladatok megoldása.   1. Bontsuk fel prímtényezőkre $10!$-t és $20!$-t, anélkül, hogy előbb elvégeznők a szorzást.   Megoldás: ${\displaystyle \begin{array}{cc}\hfill {\displaystyle 10!}& {\displaystyle =1\cdot 2\cdot 3\cdot 4\cdot 5\cdot 6\cdot 7\cdot 8\cdot 9\cdot 10=2\cdot 3\cdot 2^2\cdot 5\cdot \left(2\cdot 3\right)\cdot 7\cdot 2^3\cdot 3^2\cdot \left(2\cdot 5\right)=}\hfill \\ \hfill {\displaystyle }& {\displaystyle =2^8\cdot 3^4\cdot 5^2\cdot \mathrm{7,}}\hfill \\ \hfill {\displaystyle 20!}& {\displaystyle =10!\cdot 11\cdot 12\cdot 13\cdot 14\cdot 15\cdot 16\cdot 17\cdot 18\cdot 19\cdot 20=}\hfill \\ \hfill {\displaystyle }& {\displaystyle =\left(2^8\cdot 3^4\cdot 5^2\cdot 7\right)\cdot 11\cdot \left(2^2\cdot 3\right)\cdot 13\cdot \left(2\cdot 7\right)\cdot \left(3\cdot 5\right)\cdot 2^4\cdot 17\cdot \left(2\cdot 3^2\right)\cdot 19\cdot \left(2^2\cdot 5\right)=}\hfill \\ \hfill {\displaystyle }& {\displaystyle =2^{18}\cdot 3^8\cdot 5^4\cdot 7^2\cdot 11\cdot 13\cdot 17\cdot 19.}\hfill \end{array}}$   Gacsályi Sándor (Debreceni gyakorló gimn. VIII. o.)   2. Határozzuk meg $100!$ prímtényezős felbontásában $2$, $3$, $5$ és $7$ kitevőjét.   Megoldás: $100!$-t már nemhogy kiszámítani, de még felírni sem volna türelmünk. Mégis el tudjuk képzelni, hogy ha felírnók az első $100$ pozitív egész szám szorzataként, akkor úgy kaphatnók meg prímtényezős felbontását, hogy minden egyes (összetett) tényezője helyébe beírnók annak prímtényezős felbontását és a $2$, $3$, $5$, $7$ s a többi prímszámok hatványait összegyűjtve, kitevőiket összeadnók. Így pl. $2$ kitevője azon számok száma $1$-től $100$-ig, amelyekben a $2$ az első hatványon szerepel, hozzáadva azon számok számának kétszeresét, amelyekben a $2$ a második hatványon szerepel, meg azon számok számának háromszorosát, amelyekben a harmadik hatványon szerepel, stb. A $2$ csak azoknak a számoknak a prímtényezős felbontásában szerepel, amelyek párosak; ilyen van $100$-ig $50$. De ezek közül $25$ osztható $4$-gyel, tehát csak a többi $25$-ben szerepel az első hatványon a $2$. A $25$ $4$-gyel osztható szám közül $12$ osztható $8$-cal is, tehát csak a többi $13$-ban szerepel a második hatványon a $2$. A $12$ $8$-cal osztható szám közül $6$ osztható $16$-tal is, ezek közül $3$ $32$-vel is, ezek közül $1$ $64$-gyel is, úgy hogy $6$ olyan szám van, amelyik a harmadik, $3$ olyan, amelyik a negyedik, $2$ olyan, amelyik az ötödik és $1$ olyan (t. í. 64), amelyik a hatodik hatványon tartalmazza prímtényezős felbontásában a $2$-t. Eszerint $2$ kitevője a $100!$ prímtényezős felbontásában: $\begin{array}{c}{\displaystyle 25+2\cdot 13+3\cdot 6+4\cdot 3+5\cdot 2+6\cdot 1=97.}\end{array}$ Hasonlóan, minthogy $100$-ig $33$ $3$-mai osztható szám van, ezek közül $11$ osztható $9$-cel (tehát a többi $22$ tartalmazza a $3$-at az első hatványon), $3$ osztható $27$-tel (tehát a többi $8$ tartalmazza a második hatványon), $1$ osztható $81$-gyel (tehát a többi $2$ tartalmazza a $3$-mat a harmadik, ez az $1$ pedig a negyedik hatványon), ezért $3$ kitevője $100!$ felbontásában $\begin{array}{c}{\displaystyle 22+2\cdot 8+3\cdot 2+4\cdot 1=48.}\end{array}$ Minthogy $100$-ig $20$ $5$-tel osztható és ezek között $4$ $25$-tel osztható szám van, tehát $16$ tartalmazza az $5$-öt az első, $4$ pedig a második hatványon, továbbá, minthogy $100$-ig $14$ $7$-tel és ezek között $2$ $49$-cel osztható szám van, tehát $12$ tartalmazza a $7$-et az első, $2$ pedig a második hatványon, ezért $5$ kitevője $16+2\cdot 4=24$, $7$-é pedig $12+2\cdot 2=16$ a $100!$ prímtényezős felbontásában. Eszerint ez a felbontás így kezdődik: $\begin{array}{c}{\displaystyle 100!=2^{97}\cdot 3^{48}\cdot 5^{24}\cdot 7^{16}\text{...}}\end{array}$ Gaál István (Szegedi ,,Dugonics András'' gimn. VII. o.)   3. Hány $0$-ra végződik $100!$? Hát $1000!$?   Megoldás: Minden szám annyi $0$-ra végződik, ahányadik hatványával még osztható a $10$-nek. ${10}^k$ prímtényezős felbontása $2^k\cdot 5^k$, tehát egy szám akkor és csak akkor osztható vele, ha prímtényezős felbontásában $2$ is, $5$ is legalább a $k$-adik hatványon szerepel. A legnagyobb ilyen $k$ a kérdéses szám prímtényezős felbontásában a $2$ és az $5$ kitevője közül a kisebbik (ha véletlenül egyenlők, akkor közös értékük). Mivel $100!$ felbontásában a $2$ kitevője $97$, az $5$-é pedig $24$, ezért $100!$ $24$ $0$-ra végződik. $1000!$ prímtényezős felbontásában az $5$ kitevője $249$, mert $1000$-ig $200$ $5$-tel, $40$ $25$-tel, $8$ $125$-tel és $1$ $625$-tel osztható szám van, tehát $160$ tartalmazza az $5$-öt az első, $32$ a második, $7$ a harmadik és $1$ a negyedik hatványon és $160+2\cdot 32+3\cdot 7+4\cdot 1=249$. A $2$ kitevője nagyobb ennél, hiszen $1000$-ig $500$ páros szám van s ezek mindegyike legalább első hatványon tartalmazza a $2$-t. Ezért $1000!$ $249$ $0$-ra végződik.   4. Határozzuk meg $\left(2^n\right)!$ és $\left(2^n-1\right)!$ prímtényezős felbontásában a $2$ kitevőjét.   Megoldás: Az $1$, $2$, $3$, $\text{...}$, $2^n$ számok között $2^{n-1}$ páros van, ezek között $2^{n-2}$ $4$-gyel osztható, $2^{n-3}$ $8$-cal, $2^{n-4}$ $16$-tal, $\text{...}$, végül egyetlen egy $2^n$-nel osztható. Így közülük $2^{n-1}-2^{n-2}$ tartalmazza a $2$-t az első, $2^{n-2}-2^{n-3}$ a második $2^{n-3}-2^{n-4}$ a harmadik, $\text{...}$, végül egy az $n$-edik hatványon. Eszerint a $2$ kitevője a $\left(2^n\right)!$ prímtényezős felbontásában ${\displaystyle \begin{array}{cc}\hfill {\displaystyle 2^{n-1}}& {\displaystyle -2^{n-2}+\left(2^{n-2}-2^{n-3}\right)+3\left(2^{n-3}-2^{n-4}\right)+\text{...}+n\cdot 1=}\hfill \\ \hfill {\displaystyle }& {\displaystyle =2^{n-1}-2^{n-2}+2\cdot 2^{n-2}-2\cdot 2^{n-3}+3\cdot 2^{n-3}-\text{...}-\left(n-1\right)\cdot 1+n\cdot 1=}\hfill \\ \hfill {\displaystyle }& {\displaystyle =2^{n-1}+2^{n-2}+2^{n-3}+\text{...}+1=2^n-1.}\hfill \end{array}}$ Minthogy $\left(2^n-1\right)!=\left(2^n\right)!:2^n$, azért prímtényezős felbontásában a $2$ kitevője $n$-nel kevesebb, mint $\left(2^n\right)!$-éban, vagyis $2^n-n-1$.   5. Fejezzük ki az algebra nyelvén, hogyan határozhatjuk meg $n!$ prímtényezős felbontásában a $p$ prímszám kitevöjét.   Megoldás: Az $1$, $2$, $3$, $\text{...}$, $n$ számok között annyi $p$-vel osztható van, ahányszor a $p$ megvan az $n$-ben, azaz $\left[\frac{n}{p}\right]$, annyi $p^2$-tel osztható, ahányszor a $p^2$ megvan az $n$-ben, azaz $\left[\frac{n}{p^2}\right]$, hasonlóan $p^3$-nel $\left[\frac{n}{p^3}\right]$ számú osztható, s. i, t.; végül, ha $p^k\le n>p^{k+1}$, akkor $p^k$-nal $\left[\frac{n}{p^k}\right]$ számú osztható, $p$ magasabb hatványával azonban egy sem. Eszerint az $1$, $2$, $3$, $\text{...}$, $n$ számok között $\left[\frac{n}{p}\right]-\left[\frac{n}{p^2}\right]$ számúnak a prímtényezős felbontása tartalmazza a $p$-t az első hatványon, $\left[\frac{n}{p^2}\right]-\left[\frac{n}{p^3}\right]$ számúé a másodikon, $\left[\frac{n}{p^3}\right]-\left[\frac{n}{p^4}\right]$ számúé a harmadikon, s. i. t.. $\left[\frac{n}{p^{k-1}}\right]-\left[\frac{n}{p^k}\right]$ számúé a $\left(k-1\right)$-ediken és $\left[\frac{n}{p^k}\right]$ számúé a $k$-adikon. Így az $n!$ prímtényezős felbontásában a $p$ kitevője ${\displaystyle \begin{array}{cc}\hfill {\displaystyle }& {\displaystyle \left[\frac{n}{p}\right]-\left[\frac{n}{p^2}\right]+2\left(\left[\frac{n}{p^2}\right]-\left[\frac{n}{p^3}\right]\right)+3\left(\left[\frac{n}{p^3}\right]-\left[\frac{n}{p^4}\right]\right)+\text{...}+\left(k-1\right)(\left[\frac{n}{p^{k-1}}\right]-}\hfill \\ \hfill {\displaystyle }& {\displaystyle -\left[\frac{n}{p^k}\right])+k\left[\frac{n}{p^k}\right]=\left[\frac{n}{p}\right]-\left[\frac{n}{p^2}\right]+2\left[\frac{n}{p^2}\right]-2\left[\frac{n}{p^3}\right]+3\left[\frac{n}{p^3}\right]-\text{...}-}\hfill \\ \hfill {\displaystyle }& {\displaystyle -\left(k-1\right)\left[\frac{n}{p^k}\right]+k\left[\frac{n}{p^k}\right]=\left[\frac{n}{p}\right]+\left[\frac{n}{p^2}\right]+\left[\frac{n}{p^3}\right]+\text{...}+\left[\frac{n}{p^k}\right]=}\hfill \\ \hfill {\displaystyle }& {\displaystyle =\left[\frac{n}{p}\right]+\left[\frac{n}{p^2}\right]+\left[\frac{n}{p^3}\right]+\text{...}\mathrm{,}}\hfill \end{array}}$ ahol az összeg az $\left[\frac{n}{p^k}\right]$ tagon túl is folytatható, hiszen a többi tagja úgy is $0$. Az eredményt utólag még így is igazolhatjuk: $\left[\frac{n}{p}\right]$ jelenti az $1$, $2$, $3$, $\text{...}$, $n$ számok közül a $p$-vel oszthatók, $\left[\frac{n}{p^2}\right]$ a $p^2$-tel, $\left[\frac{n}{p^3}\right]$ a $p^3$-nel oszthatók számát, s. i. t. Ha tehát egy szám $p$-vel osztható, de $p^2$-tel nem, akkor az $\left[\frac{n}{p}\right]+\left[\frac{n}{p^2}\right]+\left[\frac{n}{p^3}\right]+\text{...}$ összegben csak egyszer vettük számba, t. i. az első tagban; ha $p^2$-tel osztható, de $p^3$-nel nem, akkor kétszer vettük számba, t. i. az első és a második tagban; ha $p^3$-nel is osztható, de $p^4$-nel nem, akkor háromszor vettük számba, t. i. az első, második és harmadik tagban, s így tovább; így minden számot annyiszor vettünk számba, amennyi a prímtényezős felbontásában a $p$ kitevője, így az összeg e kitevők összege, vagyis $n!$ felbontásában $p$ kitevője.   Megjegyzések: A $p^k\le n<p^{k+1}$ egyenlőtlenség $k\le \frac{\text{log}n}{\text{log}p}{=}^p\text{log}n<k+1$ alakban írható; tehát az ennek eleget tevő egész szám $k=\left[\frac{\text{log}n}{\text{log}p}\right]={[}^p\text{log}n]\mathrm{.}$   Buzi Károly (Szegedi ,,Dugonics András'' gimn. VI. o.) Czipszer János (Budapesti ,,Kölcsey'' gimn. VII. o.)   Numerikusan adott $n$ és $p$ esetén célszerűbb a számítást így berendezni: legyen $\left[\frac{n}{p}\right]=n_1$, $\left[\frac{n_1}{p}\right]=n_2$, $\left[\frac{n_2}{p}\right]=n_3$, $\text{...}$; akkor a $p$ prímszám kitevője $n!$ prímtényezős felbontásában $n_1+n_2+n_3+\text{...}+n_k$. Ugyanis $\begin{array}{c}{\displaystyle \left[\frac{n}{p^2}\right]=\left[\frac{\frac{n}{p}}{p}\right]=\left[\frac{\left[\frac{n}{p}\right]}{p}\right]=\left[\frac{n_1}{p}\right]=n_2\mathrm{,}}\end{array}$ $\begin{array}{c}{\displaystyle \left[\frac{n}{p^3}\right]=\left[\frac{\frac{n}{p^2}}{p}\right]=\left[\frac{\left[\frac{n}{p^2}\right]}{p}\right]=\left[\frac{n_2}{p}\right]=n_3\mathrm{,}\text{...}\mathrm{,}}\end{array}$ mert általában $\left[\frac{x}{p}\right]=\left[\frac{\left[x\right]}{p}\right]$. (85. feladat, 49. o.) Gehér László (Zalaegerszegi gimn. VII. o.) Fried Ervin (Budapesti ,,Kemény Zs.'' gimn. VII. o.)   Többen úgy fogalmazták a megoldást, hogy az 1‐4. feladatokban hivatkoztak az 5. feladat megoldására Aki előbb jött rá az 5. feladat megoldására, azután a többire, jól tette. De azt gondolom, a legtöbb megoldó számára megkönnyítette az 5. feladat megoldását, hogy előbb az első négyen gondolkodhatott (hiszen ezért bocsátottam azokat előre). Megoldásukon ez mégsem látszik. Helyes, ha nem szószerint úgy írjuk le a megoldást, ahogy (esetleg nagy kerülővel) rátaláltunk, hanem érthetőbb alakba igyekszünk önteni. Csak azt ne higyjük, hogy érthetőbb lesz a gondolatmenetünk, ha eltakarjuk azt az utat, amin rá lehet jönni. Lehet, hogy nekünk, akik már megjártuk ezt az utat, így is világos, de annak, aki még nem járta végig, érthetetlenné lesz ezáltal. Akkor is, ha mégoly logikusnak véljük az átfogalmazott megoldást; mert hiszen az érthetőség nemcsak logika, hanem pszichológia dolga is. Sokak számára azért érthetetlen a matematika, mert a matematikusok szeretik magukat bámultatni a ,,laikusokkal'', milyen zseniális ötletek pattannak ki az agyukból (mint a görög mítosz szerint Pallasz Athéné Zeüsz fejéből) ‐ ahelyett, hogy bevallanák, nem készen pattan ki az ilyen ötlet és megmutatnák másoknak is az utat, amin ilyen ötletekhez juthatni. Kérem olvasóimat, ne tanulják el ezt a matematikus-hibát, hiszen valamennyiünk célja, ugye, hogy minél több diáktársunkkal megértessük és megszerettessük a matematikát.   A Csebysev-tétel felé vezető új feladatok.   Emlékezzünk, azért kezdtünk $\left(\genfrac{}{}{0ex}{}{2n}{n}\right)$-nel foglalkozni, mert azt reméltük, ez a szám megérzi, hogy vannak prímszámok $n$ és $2n$ között; vagyis, ha feltételezzük, hogy $n$ és $2n$ között nincs prímszám, akkor $\left(\genfrac{}{}{0ex}{}{2n}{n}\right)$ prímtényezős felbontásából kisebb érték adódik $\left(\genfrac{}{}{0ex}{}{2n}{n}\right)$ számára, mint amekkora valójában. Nézzük meg hát most, milyen egyenlőtlenség adódik $\left(\genfrac{}{}{0ex}{}{2n}{n}\right)$ számára a 9. és 10. feladatok megoldásával bebizonyított tételek segítségével.   11. Tegyük fel, hogy $n$ és $2n$ között nincs prímszám. Mutassuk meg, hogy akkor $\left(\genfrac{}{}{0ex}{}{2n}{n}\right)$ nem lehet nagyobb, mint $2n$-nek annyiadik hatványa, ahány prímszám van $\sqrt[]{2n}$-ig, megszorozva a $2n/3$-ig terjedő prímszámok szorzatával. Ha az így kapott egyenlőtlenséget sikerül megcáfolnunk, akkor bebizonyítottuk, lehetetlen, hogy ne legyen $n$ és $2n$ között prímszám. Igen ám, de a kapott egyenlőtlenségben még két ismeretlen valami szerepel: a prímszámok száma $\sqrt[]{2n}$-ig és a prímszámok szorzata $2n/3$-ig. Ezekre próbáljunk olyan egyenlőtlenségeket megállapítani, amiknek segítségével a 11. feladatban szereplő egyenlőtlenségből egyszerűbb (de még mindig megcáfolható) egyenlőtlenséget kaphatunk.   12. Mutassuk meg, hogy $n\ge 14$ esetén $n$-ig ($n$-et is beleértve, ha prímszám) legfeljebb $\left(n/2\right)-1$ számú prímszám van. (Az $1$ nem számít prímszámnak. A prímszámok szorzatának vizsgálatára megint a $\left(\genfrac{}{}{0ex}{}{2n}{n}\right)$-et vesszűk igénybe. Hiszen ez osztható az $n$ és $2n$ közötti prímszámokkal, tehát azok szorzatával is.   13. Mutassuk meg, hogy ha $n$ legalább $5$, akkor $\left(\genfrac{}{}{0ex}{}{2n}{n}\right)<4^{n-1}$.   14. Mutassuk meg, hogy ha egyáltalában van $n$ és $2n$ között prímszám, akkor az ilyen prímszámok szorzata kisebb, mint $4^{n-1}$. (Itt az $n=1$ eset kivétel.)   15. Jelöljük $P_n$-nel az $n$ számig terjedő prímszámok szorzatát. Mutassuk meg, hogy $P_n\le 4^n$.   16. Tegyük fel ismét, bogy $n$ és $2n$ között nincs prímszám. Mutassuk meg, hogy akkor $\left(\genfrac{}{}{0ex}{}{2n}{n}\right)$ nem lehet nagyobb mint ${\left(2n\right)}^{\frac{\sqrt[]{2n}}{2}}\cdot 4^{\frac{2n}{3}}$, feltéve, hogy $n\ge 100$.