Kezdőlap


Feladat:	Pontversenyen kívüli P.38	Korcsoport: 14-15	Nehézségi fok: nehéz
Megoldó(k):	Füredi Zoltán , Göndőcs Ferenc , Lempert László , Pál Jenő , Papp Zoltán , Prőhle Tamás
Füzet:	1970/február, 72 - 74. oldal		PDF \| MathML
Témakör(ök):	Binomiális együtthatók, Oszthatósági feladatok, Prímtényezős felbontás, Szorzat, hatvány számjegyei, Teljes indukció módszere, Pontversenyen kívüli probléma
Hivatkozás(ok):	Feladatok: 1969/szeptember: Pontversenyen kívüli P.38

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. Fel fogjuk használni azt, hogy $l$ egymás utáni természetes szám szorzata osztható $l!$ -sal. Ugyanis

\begin{matrix} \frac{(r + 1) (r + 2) \cdot ... \cdot (r + l)}{l!} = (\binom{r + l}{l}) \end{matrix}

és a binomiális együtthatók egész számok (ez a kombinatorikai értelmezésből nyilvánvaló).
A feladat megoldására térve, először megállapítjuk, hogy

n!

törzstényezős felbontásában

p

hányadik hatványon fordul elő. Ez az

m

kitevő nyilván előállítható az

\begin{matrix} m = m_{1} + m_{2} + ... + m_{i} + ... + m_{u} \end{matrix}

alakban, ahol

m_{i}

jelöli az

1

-től

n

-ig terjedő számok közül a

p^{i}

-nel oszthatók számát. Így ugyanis minden

p^{i}

-nel osztható, de

p^{i + n}

-nel már nem osztható tényezőt

i

-szer veszünk számításba. Eszerint

\begin{matrix} m_{i} = [\frac{n}{p^{i}}], \end{matrix}

és

\begin{matrix} m = [\frac{n}{p}] + [\frac{n}{p^{2}}] + ... + [\frac{n}{p^{u}}], \end{matrix}

ahol

\begin{matrix} p^{u} ≧ n < p^{u + 1} . \end{matrix}

Feltevésünk szerint

p^{k} ∣ n!

így

\begin{matrix} k ≦ [\frac{n}{p}] + [\frac{n}{p^{2}}] + ... + [\frac{n}{p^{u}}], \end{matrix}

A jobb oldalt így alakítjuk:

\begin{matrix} [\frac{n}{p}] + [\frac{n}{p^{2}}] + ... + [\frac{n}{p^{u}}] ≦ \frac{n}{p} + \frac{n}{p^{2}} + ... + \frac{n}{p^{u}} = \\ = n \frac{p^{u} - 1}{p^{u} (p - 1)} = \frac{n}{p - 1} (1 - \frac{1}{p^{u}}) ≦ \frac{n}{p - 1}, \end{matrix}

tehát

\begin{matrix} k ≦ \frac{n}{p - 1}, \end{matrix}

vagyis

\begin{matrix} k (p - 1) ≦ n . \end{matrix}

Ezért az

1 \cdot 2 \cdot 3 \cdot ... \cdot n

szorzatot felbontva egymás utáni tényezőiből alakított

p - 1

tagú csoportokra, legalább

k

csoport képezhető. Minden ilyen csoport az előrebocsátott megjegyzés szerint osztható

(p - 1)!

-sal. Tehát

{((p - 1)!)}^{k} ∣ n!

Másrészt

p^{k}

és

{((p - 1)!)}^{k}

relatív prímek, így a feltevés alapján szorzatuk is osztója

n!

-nak, tehát

{(p!)}^{k} ∣ n!

Pál Jenő (Kaposvár, Táncsics M.Gimn., IV. o. t.)

Füredi Zoltán (Budapest, Móricz Zs. Gimn., II. o. t.)

II. megoldás.

n!

prímfelbontásában egy

p

prímszám kitevője úgy határozható meg, hogy a

p

-vel osztható tényezőkből kiemeljük

p

legmagasabb hatványát, amivel osztható, és kitevőiket összeadjuk. A

p

-vel osztható tényezők

p,2 p, ..., m p

, ahol

\begin{matrix} m p ≦ n < (m + 1) p, azaz m = [\frac{n}{p}] . \end{matrix}

Ennek alapján

n!

így bontható fel:

\begin{matrix} n! = {1 \cdot 2 \cdot ... \cdot (p - 1)} \cdot {(p + 1) (p + 2) \cdot ... \cdot (p + (p - 1))} \cdot ... \cdot \\ \cdot {((m - 1) p + 1) \cdot ... \cdot ((m - 1) p + (p - 1))} \cdot {(m p + 1) \cdot ... \cdot n} \cdot m! p^{m} . \end{matrix}

(Itt az utolsó kapcsos zárójelben levő szorzat nem lép fel, ha

p ∣ n

, viszont csak az áll a jobb oldalon, ha

n < p

.) Ez a felbontás teljes indukciós bizonyítást sugall.
Ha

n < p

, akkor

k

csak

0

lehet, és az állítás nyilvánvalóan igaz.
Tegyük most fel, hogy

n ≧ p

, és az állítás igaz az

n

-nél kisebb természetes számokra. Ekkor a fenti felbontás kapcsos zárójelben levő szorzatai oszthatók

(p - 1)!

-sal, szorzatuk tehát

{((p - 1)!)}^{m}

-nel. Az állítás tehát ismét igaz, ha

k ≦ m

. Ha viszont

k = m + k'

, és

k' ≧ 1

, akkor előrebocsátott megjegyzésünk szerint

p^{k'}

m!

osztója kell hogy legyen. Mivel

m < n

, így rá feltétel szerint igaz az állítás,

m!

osztható

{(p!)}^{k'}

-nel is. így

n!

-nak osztója

\begin{matrix} {((p - 1)!)}^{m} {(p!)}^{k'} p^{m} = {(p!)}^{m + k'} = {(p!)}^{k} . \end{matrix}

Az állítás tehát minden

n

-re érvényes.

Fried Ervin