Kezdőlap


Feladat:	1547. matematika feladat	Korcsoport: 16-17	Nehézségi fok: nehéz
Füzet:	1968/szeptember, 14 - 16. oldal		PDF \| MathML
Témakör(ök):	Algebrai átalakítások, Kombinatorikai leszámolási problémák, Oszthatósági feladatok, Feladat
Hivatkozás(ok):	Feladatok: 1967/szeptember: 1547. matematika feladat

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. Az (1) szorzat minden egyes tényezője két további tényező szorzatára bontható, $i = 1,2, ..., n$ esetén

\begin{matrix} c_{m + i} - c_{k} & = (m + i) (m + i + 1) - k (k + 1) = \\ = [{(m + i)}^{2} - k^{2}] + [(m + i) - k] = \\ = (m - k + i) (m + k + i + 1) . & (3) \end{matrix}

Így maga az (1) alatti

P

szorzat is írható két szorzat,

P_{1}

és

P_{2}

szorzataként, ahol

P_{1}

-be soroljuk minden egyes (3) alakú felbontás első tényezőjét,

P_{2}

-be pedig a másodikat, vagyis

\begin{matrix} P_{1} & = (m - k + 1) (m - k + 2) ... (m - k + n), \\ P_{2} & = (m + k + 2) (m + k + 3) ... (m + k + n + 1) . \end{matrix}

A (2) alatti

Q

szorzat, minden egyes

c_{i}

tényezője helyére az értelmezés szerint

i (i + 1)

-et írva, majd az előbbihez hasonló átcsoportosítással ugyancsak

\begin{matrix} Q = c_{1} c_{2} ... c_{n} = [1 \cdot 2 \cdot ... \cdot (n - 1) \cdot n] \cdot [2 \cdot 3 \cdot ... \cdot n \cdot (n + 1)] = Q_{1} \cdot Q_{2}, \end{matrix}

ahol

Q_{1}

-gyel az első,

Q_{2}

-vel a második szögletes zárójelbeli szorzatot jelöltük. A faktoriális ismert jelével

Q_{1} = n!, Q_{2} = (n + 1)!

. Így azt kell megmutatnunk, hogy a következő hányados:

\begin{matrix} \frac{P}{Q} = \frac{P_{1} \cdot P_{2}}{Q_{1} \cdot Q_{2}} = \frac{P_{1}}{Q_{1}} \cdot \frac{P_{2}}{Q_{2}} \end{matrix}

egész szám. Ehhez belátjuk, hogy az utolsó alak mindkét tényezője egész.
II.

P_{1}

-ben

n

egymás utáni egész számot szorzunk össze. Állítjuk, hogy ez n!-sal osztva mindig egész számot ad hányadosul.
Ha

m + 1 \leq k \leq m + n

, akkor

P_{1}

tényezői között szerepel a

0

, így a

P_{1} / Q

, hányados

0

, állításunk igaz.

k < m + 1

esetén

P_{1} / Q_{1}

egész voltát úgy bizonyítjuk be, hogy megadunk egy feladatot, melynek megoldásáról egyrészt azt tudjuk, hogy egész szám, másrészt megmutatjuk, hogy egyenlő

P_{1} / Q_{1}

-gyel. Legyen

m - k + n = N

így a feltevés szerint

N \geq n

.
A feladat a következő. Egy verseny első fordulóján

N

résztvevő indul, közülük az első

n

jut be a második fordulóba. Hányféleképpen alakulhat a második forduló mezőnye?
A válasz nyilvánvalóan egész szám. Adjuk meg a keresett számot először a II. fordulóba bejutók helyezési sorrendjét is figyelembe véve (holtversenyt kizárva). Az 1. helyezett

N

-féleképpen adódhat, a 2. helyezett a maradó

N - 1

résztvevő közül

N - 1

-féleképpen, és így tovább, a

k + 1

-edik lépésben a

k + 1

-edik helyezett

N - k

-féleképpen adódhat, mert miután az első

k

díj már gazdát talált, a

k + 1

-edik díj gazdája a még nem díjazott

N - k

résztvevő közül kerül ki. így a II. forduló lehetséges helyezési sorrendjeinek száma

\begin{matrix} N (N - 1) ... (N - n + 1), \end{matrix}

(4)

ami

P_{l}

-gyel egyenlő.
Az eredeti kérdésre most már úgy adhatjuk meg a választ, hogy a talált sorrendeket csoportosítjuk, egy csoportba gyűjtjük azokat, amelyekben ugyanazok a versenyzők kapják az első

n

díjat; mindegyik csoport egyetlen lehetőséget ad a II. forduló mezőnyének kialakulására. Így minden egyes csoportba annyi sorrend jut, ahányféleképpen ugyanaz az a díjazott az

n

díjon megosztozhat. Számuk annyi, mintha az első változatban az első a díjat

n

résztvevő között kellene kiosztani, vagyis (4) értéke

N = n

esetére, ami

n! = Q_{1}

. Eszerint a csoportok száma

P_{1} / Q_{1}

és ez ‐ mint láttuk ‐ egész szám. Ezt akartuk bizonyítani.
Ha végül

k > m + n

, akkor

P_{1}

minden tényezője negatív egész szám, mindegyikből

(- 1)

-et kiemelve

n

egymás utáni természetes szám szorzatát kapjuk (csökkenő rendben), ezért

\begin{matrix} \frac{P_{1}}{Q_{1}} = {(- 1)}^{n} \frac{| P_{1} |}{Q_{1}}, \end{matrix}

egész szám.
III. A

P_{2} / Q_{2}

hányados egész voltának bizonyításához eredményünket

n

helyén

n + 1

-gyel alkalmazzuk a következő hányadosra:

\begin{matrix} \frac{(m + k + 1) \cdot P_{2}}{Q_{2}} = \frac{(m + k + 1) \cdot P_{2}}{(n + 1)!} . \end{matrix}

(5)

Ennek számlálója

n + 1

egymás utáni természetes szám szorzata, tehát a hányados egész. Így pedig

P_{2} / Q_{2}

is egész, mert a számláló első tényezője törzsszám, és nagyobb

n + 1

-nél, tehát nincs közös osztója

Q_{2}

egyik tényezőjével sem; ezért, ha

P_{2} / Q_{2}

tovább nem egyszerűsíthető alakjának nevezője nagyobb volna 1-nél, akkor ez maradna a nevezője (5) tovább nem egyszerűsíthető alakjának is.
Fenti tervünket teljesítettük, az állítást bebizonyítottuk.

Megjegyzés. A

P_{1} / Q_{1}

hányados egész voltát beláthatjuk úgy is, hogy gondolatban

P_{1}

et is,

Q_{1}

-et is különböző alapú törzsszámhatványok szorzataként előállítva minden egyes, az

n!

-ban fellépő törzsszámról megmutatjuk: a számlálóban legalább ugyanakkora kitevővel szerepel, mint a nevezőben.^{$^{*}$}

^{$^{*}$}Efféle gondolatmenet olvasható a következő helyen: Kürschák József ‐ Hajós György ‐ Neukomm Gyula ‐ Surányi János. Matematikai Versenytételek, I. rész, 3. kiadás, Tankönyvkiadó, Budapest, 1964, 124. o. 1925/2. feladat.