Kezdőlap


Feladat:	N.29	Korcsoport: 18-	Nehézségi fok: nehéz
Megoldó(k):	Braun Gábor , Csörnyei Marianna , Pap Gyula
Füzet:	1995/február, 100 - 101. oldal		PDF \| MathML
Témakör(ök):	Összefüggések binomiális együtthatókra, Indirekt bizonyítási mód, Legnagyobb közös osztó, Nehéz feladat
Hivatkozás(ok):	Feladatok: 1994/április: N.29

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.

Feltételezhetjük, hogy $k$ és $l$ nem nagyobbak $\frac{n}{2}$ -nél, ugyanis $k$ -t
$(n - k)$ -ra, $l$ -et pedig $(n - l)$ -re cserélhetjük ellenkező esetben.
Könnyen ellenőrizhető, hogy

\begin{matrix} (\binom{n}{k}) \cdot (\binom{n - k}{l}) = (\binom{n}{l}) (\binom{n - l}{k}) . \end{matrix}

(1)

(Például úgy, hogy

\begin{matrix} \begin{matrix} (\binom{n}{k}) helyére \frac{n (n - 1) ... (n - k + 1)}{k!} -t, \\ (\binom{n - k}{l}) helyére \frac{(n - k) ... (n - k - l + 1)}{l!} -t stb. írunk.) \end{matrix} \end{matrix}

(\binom{n - k}{l})

és

(\binom{n - l}{k})

binomiális együtthatók értelmesek, mert

k

l \leq \frac{n}{2}

miatt

l \leq n - k

és

k \leq n - l

.
Ugyanakkor az is igaz, hogy

\begin{matrix} (\binom{n - l}{k}) < (\binom{n}{k}) . \end{matrix}

(2)

(Ez szintén ellenőrizhető az előbbi behelyettesítéssel:

\begin{matrix} \frac{(n - l) (n - l - 1) ... (n - l - k + 1)}{k!} < \frac{n (n - 1) ... (n - k + 1)}{k!} .) \end{matrix}

Az (1) bal oldala osztható

(\binom{n}{k})

-val. Ha jobb oldalán az

(\binom{n}{l})

tényező ehhez relatív prím lenne, akkor a másik tényezőnek,

(\binom{n - l}{k})

-nak kellene

(\binom{n}{k})

-val oszthatónak lenni. De egy pozitív egész nem lehet egy nála nagyobb számnak többszöröse, ez tehát ellentmondás.
Tehát

(\binom{n}{k})

és

(\binom{n}{l})

nem lehetnek relatív prímek.