Uloha 3.1 Kombinatorika

[JaroslavPetrucha]

Úloha 3.1. Dokážte, že:
a) V ľubovoľnom poli platí $(a+b)^m= a^m + \binom m1 \times a^{m-1}b + \binom m2 \times a^{m-2}b^2+ \ldots + \binom m{m-1} ab^{m-1} + b^m$. (Súčet na pravej strane sa zvykne označovať takto: $\sum_{k=0}^m \binom mk \times a^{m-k}b^k$.)
b) V poli $\mathbb Z_p$ platí: $(a\oplus b)^p=a^p \oplus b^p$.


a) Podme si to dokazat indukciou :

Pre potreby dokazu sa nam bude hodit prepisat cely vyraz takym sposobom, ze pred prvy clen este napiseme "$\binom{m}{0} \times$" a pred posledny clen "$\binom{m}{m} \times$", pricom vieme, ze obe su rovne 1 (ak by bolo treba ukazat, mozem).

Z definicie vieme, ze $(a + b)^0 = 1$, cize $(a + b)^1 = 1(a + b)$ , z distributivnosti, kedze ide o pole, $1(a + b) = 1a + 1b = a + b = \binom{1}{0} \times a^1 + \binom{1}{1} \times b^1$, cim sme si dokazali prvy krok.
Pre kazdy dalsi teda mozme predpokladat, ze $(a + b)^k = \binom{k}{0} \times a^k + \binom{k}{1} \times a^{k-1}b^1 + \cdots + \binom{k}{k} \times b^k$.
$(a + b)^{k+1} = (a + b)^k(a + b) = \Big(\binom{k}{0} \times a^k + \binom{k}{1} \times a^{k-1}b^1 + \cdots + \binom{k}{k} \times b^k\Big)\Big(a+b\Big)$
Dalej aplikujeme zoparkrat distributivny zakon (a niekolkokrat aj komutativnost operacie .).

$\Big(\binom{k}{0} \times a^k + \binom{k}{1} \times a^{k-1}b^1 + \cdots + \binom{k}{k} \times b^k\Big)\Big(a+b\Big) = a\Big(\binom{k}{0} \times a^k + \binom{k}{1} \times a^{k-1}b^1 + \cdots + \binom{k}{k} \times b^k\Big) + b\Big(\binom{k}{0} \times a^k + \binom{k}{1} \times a^{k-1}b^1 + \cdots + \binom{k}{k} \times b^k\Big) =$
$= \bigg(\Big(\binom{k}{0} \times a^k\Big)a + \Big(\binom{k}{1} \times a^{k-1}b^1\Big)a + \cdots + \Big(\binom{k}{k} \times b^k\Big)a\bigg) + \bigg(\Big(\binom{k}{0} \times a^k\Big)b + \Big(\binom{k}{1} \times a^{k-1}b^1\Big)b + \cdots + \Big(\binom{k}{k} \times b^k\Big)b\bigg)$

Tu nas caka mala odbocka, chceme dokazat, ze $(z \times x^y)x = z \times x^{y+1}$ K tomu si staci len uvedomit, ze $z \times x^y = (z - 1) \times x^y + x^y$, cize
$(z \times x^y)x = ((z - 1) \times x^y + x^y)x = ((z - 1) \times x^y)x + x^{y+1}$, co uz hadam zjavne indukciou lahko ukazeme, ze vyplyva z definicie.
Dalsia mala odbocka do buducnosti bude dokaz $x \times z + y \times z = (x + y) \times z$, kde si ale treba uvedomit, ze scitanie $(x + y)$ je to, na ktore sme zvyknuti v $\mathbb{N}$.
Opat nic zlozite, staci si uvedomit $x \times z + y \times z = (x - 1) \times z + z + y \times z = (x - 1) \times z + (y + 1) \times z$, co sa opat da lahko dokazat indukciou.

Vratme sa teda k povodnej rovnosti.
$\bigg(\Big(\binom{k}{0} \times a^k\Big)a + \Big(\binom{k}{1} \times a^{k-1}b^1\Big)a + \cdots + \Big(\binom{k}{k} \times b^k\Big)a\bigg) + \bigg(\Big(\binom{k}{0} \times a^k\Big)b + \Big(\binom{k}{1} \times a^{k-1}b^1\Big)b + \cdots + \Big(\binom{k}{k} \times b^k\Big)b\bigg) =$
$= \bigg(\Big(\binom{k}{0} \times a^{k+1}\Big) + \Big(\binom{k}{1} \times a^{k}b\Big) + \cdots + \Big(\binom{k}{k} \times ab^k\Big)\bigg) + \bigg(\Big(\binom{k}{0} \times a^kb\Big) + \Big(\binom{k}{1} \times a^{k-1}b^2\Big) + \cdots + \Big(\binom{k}{k} \times b^{k + 1}\Big)\bigg) = $
$= \bigg(\binom{k}{0} \times a^{k+1} + \Big(\binom{k}{1} + \binom{k}{0}\Big) \times a^{k}b + \cdots + \Big(\binom{k}{k} + \binom{k}{k - 1}\Big) \times ab^k + \binom{k}{k} \times b^{k+1}\bigg)$

Posledne kozmeticke upravy, ktore treba spravit:
- $\binom{k}{k} \times b^{k+1} = \binom{k+1}{k+1} \times b^{k+1}$, lebo obe tie kombinacne cisla su rovne 1;
- $\binom{k}{a} + \binom {k}{a - 1} = \binom{k+1}{a}$, co je zakladna vec z kombinatoriky, ktoru snad netreba dokazovat (pripadne mozem dodokazat)

Akonahle spravime tie, dostavame sa k rovnosti $(a + b)^{k+1} = \binom{k+1}{0} \times a^{k+1} + \binom{k+1}{1} \times a^kb + \cdots + \binom{k+1}{k+1} \times b^{k+1}$, cim sme dokazali krok indukcie, cize cela indukcia plati.


b)Pouzijeme rozpisanie pomocou a):
$(a \oplus b)^p = a^p + \binom{p}{1} \times a^{p-1}b + \cdots + b^p$

Teraz si dokazeme, ze $\forall x, y \in \mathbb{Z}_p\ :\ p|x \Rightarrow x \times y = 0$, postup moze byt napriklad taky, ze si dokazeme, ze $q \times w = (q \bmod p) \bigodot w$, napriklad indukciou:
$0 \times w = 0 = 0 \bigodot w$
$k \times w \oplus w = k \bigodot w \oplus w = k \bigodot (w \oplus 1)$ (pomocou distributivneho zakona)
Je zrejme, ze $x \bmod p = 0$, cize $x \times y = 0$.

Co nam teda treba dokazat je $\forall p \in \mathbb{N}\ \forall i \in \mathbb{N}; 0 < i < p\ :\ p | \binom {p}{i}$
K tomu si mozme vypozicat prepis $\binom {p}{i} = \frac {p!} {i! (p-i)!}$.
Kedze $p$ je prvocislo a ziadne cislo mensie ako $p$ nemoze delit $p$, tak naozaj plati $p | \binom {p}{i}$

Z toho dovodu bude akykolvek clen z $a^p + \binom{p}{1} \times a^{p-1}b + \cdots + b^p$ okrem prveho a posledneho po uprave 0, cize neutralny prvok na $(\mathbb{Z}, \oplus)$, takze naozaj plati to, co sme chceli dokazat.

[Martin Sleziak]

Riešenie je fajn, značí si 1 bod.

Len zosumarizujem, že sme vlastne dokázali, že binomická veta sa dá používať v každom poli. (A dôkaz vlastne ani nie je veľmi odlišný od dôkazu pre reálne čísla.)

Drobná poznámka k označeniu:

Tu nas caka mala odbocka, chceme dokazat, ze $(z \times x^y)x = z \times x^{y+1}$ K tomu si staci len uvedomit, ze $z \times x^y = (z - 1) \times x^y + x^y$, cize
$(z \times x^y)x = ((z - 1) \times x^y + x^y)x = ((z - 1) \times x^y)x + x^{y+1}$, co uz hadam zjavne indukciou lahko ukazeme, ze vyplyva z definicie.
Dalsia mala odbocka do buducnosti bude dokaz $x \times z + y \times z = (x + y) \times z$, kde si ale treba uvedomit, ze scitanie $(x + y)$ je to, na ktore sme zvyknuti v $\mathbb{N}$.
Opat nic zlozite, staci si uvedomit $x \times z + y \times z = (x - 1) \times z + z + y \times z = (x - 1) \times z + (y + 1) \times z$, co sa opat da lahko dokazat indukciou.

Možno by bolo lepšie používať napríklad $x$, $y$, $z$ pre prvky poľa a $k$, $l$, $m$, $n$ pre prirodzené čísla (alebo niečo podobné, každopádne nezaškodí udržať si to konzistentne v celom dôkaze.) Je to prehľadnejšie pre čitateľa.
Napríklad tu u vás $x$ raz vystupovalo ako prvok poľa (vo výraze $x^y$) a o dva riadky nižšie je to prirodzené číslo $x\times z$. Samozrejme, každý si z kontextu domyslí, čo znamená $x$ v jednotlivých prípadoch, ale možno takto to môže pre niekoho byť mätúce.

Azda poznamenám aj to, že keby ste tieto veci prehlásili za jasné, tak by som to bez problémov zobral.

Co nam teda treba dokazat je $\forall p \in \mathbb{N}\ \forall i \in \mathbb{N}; 0 < i < p\ :\ p | \binom {p}{i}$
K tomu si mozme vypozicat prepis $\binom {p}{i} = \frac {p!} {i! (p-i)!}$.
Kedze $p$ je prvocislo a ziadne cislo mensie ako $p$ nemoze delit $p$, tak naozaj plati $p | \binom {p}{i}$

Pre istotu skúsim ešte vysvetliť detailnejšie. Prvá vec, ktorú treba mať na pamäti je, že $\binom pi$ je celé číslo. (Takže má zmysel hovoriť o tom, či to je deliteľné číslom $p$.
V uvedenom zápise $\binom {p}{i} = \frac {p!} {i! (p-i)!}=\frac{p(p-1)\dots)(p-i+1)}{i!}$ máme tento binomický koeficient prepísaný ako zlomok, kde v čitateli vystupuje číslo $p$. Súčasne sa $p$ nevyskytuje v menovateli. (Toto je miesto, kde využívame, že platí $i>0$ a $i<p$.)
Takže prvočíslo $p$ sa nemá s čím vykrátiť a zostane v prvočíselnom rozklade čísla $\binom pi$.

Pridám ešte linku na Wikipédiu: Freshman's dream