Matematické Fórum

Andrejka3

Ahoj fórumáci.
Narazila jsem na hezký příklad, se kterým bych se ráda s Vámi podělila. Hledala jsem, jestli tady už je, ale myslím, že ne.

Zadání a návod

Autor skryl část textu. Zobrazit/skrýt!

Porozumění (pro ty, kteří neznají binomická čísla)

Autor skryl část textu. Zobrazit/skrýt!

Řešení pro $j=3$

Autor skryl část textu. Zobrazit/skrýt!

To je pro mě kouzelný výsledek. Dokonce mě bavilo postupně dosazovat malá čísla $n$ a ověřovat, že to skutečně funguje. Samozřejmě se nabízí otázka, zda to funguje pro každé přirozené $j$ .
Prvočísla

Autor skryl část textu. Zobrazit/skrýt!

Proč to píšu:
Napadne Vás nějaké zadání slovní úlohy, které by vedlo k tomuto příkladu? Asi lze napsat obecný postup, jak spočítat tyto vztahy pro libovolné $j$ přirozené (Frobenius-Stickelberger?). Kdybyste věděli, jak na to, těším se na odpovědi.

check_drummer · 26. 02. 2012 19:57

↑ Andrejka3:
Ahoj, velmi pěkné. Každý vztah, kde figuruje reálná funkce a přirozená čísla jako hodnoty je pěkný. :-)
Jakou máš na mysli slovní úlohu - samo zadání "najděte počet podmnožin..." není slovní úloha?

Andrejka3 · 26. 02. 2012 20:13

↑ check_drummer:
Ahoj, no spíš bych ráda něco více "ze života" :D
Něco, co by mohlo třeba zaujmout puberťáky.

vanok · 27. 02. 2012 00:49 — Editoval vanok (27. 02. 2012 00:51)

Ahoj ↑ Andrejka3:,
toto sa ti zda ake?
V jednej triede ucitel vymyslel takuto matematicku aktivitu:
do jedneho klobuka dal 64 papierikov a na kazdy napisal jednu inu podmnozinu mnoziny
$A= \{1;2;3;4;5;6 \}$
Pripravil 2 krabice
na jednu napisal pocet prvkov je delitelny 3
na pocet prvkov je nedelitelny 3

A dal taketo otazky
1) napisal vsetki podmnoziny mnoziny A?
2) ak rozdelime tie papieriky do nasich 2 krabic, ktora bude mat viacej papierikov
3) da sa to dokazat?

......
ATD....

Ale neviem ci je to zo zivota, ako si chcela? Ale je to mozno pouzitelne v nejakom matematickom kruzku.

Andrejka3 · 27. 02. 2012 07:05

↑ vanok:
Díky za nápad. Určitě to je pro nematematiky lepší.

PS: A co si myslíte o obecnějším případě pro libovolné přirozené $j$ ? Že lze vždy vymyslet, jak ty rovnice vynásobit a posčítat?

Andrejka3

Pokračování první zprávy:
Pozorování
Díky symetriím problému (názorné v Gaussově rovině) platí $\forall n \in \mathbb{N}: \; \sum_{j=0}^{n-1}e^{i 2 \pi \frac{j}{n} }=0$ , tedy také

$\sum_{j=1}^{n-1}e^{i 2 \pi \frac{j}{n} }=-1 \;.$ (12)

Z toho je patrné, že $y$ z důkazu pro $j=p$ prvočíslo je rovno jedné.
Dále je patrné, že grupy řešení rovnice (2) jsou cyklické a tedy, máme-li prvočíselný rozklad, $j= \Pi_{l=1}^{m} p_l^{\nu_l}$ (různá prvočísla), pak grupa kořenů příslušné rovnice (2) je izomorfní aditivní grupě $\times_{l=1}^{m}\mathbb{Z}_{p_l^{\nu_l}}$ . (Nejsem si tímto jistá.)
V následujícím textu zkouším dokázat, proč návod funguje pro čísla ve tvaru součinu dvou prvočísel, $j=pq$ . Je to sice jen 'malá třída' čísel a opět jen speciální případ, ale myslím, že zobecnění na širší případy se pak nabídne samo.

$j=pq$

Autor skryl část textu. Zobrazit/skrýt!

edit: doplněno.
Zbývá přemýšlet o obecném případě, nebo aspoň součinu prvních mocnin konečně mnoha prvočísel, pak třeba druhá mocnina jednoho prvočísla a nakonec to možná zapadne a bude to.
Napsat hezky obecně pravou stranu?

check_drummer · 01. 03. 2012 20:09

↑ Andrejka3:
Ahoj. Já jsem si říkal, že by tam to y mohlo být "zbytečně". :-) Bohužel nemám teď tolik času se více zamyslet, tak jen krátce - pro případ j prvočíslo tedy dáváš jen "návod" jak daný vzorec sestavit, ovšem nikoli explicitní vzorec, protože je poněkud obtížně takto jedním vzorcem vystihnout všechna taková j - mám pravdu?
Bylo by zajímavé najít "společný" explicitní vzorec pro všechna j, tedy pokud vůbec existuje. Na druhou stranu, pokud existuje pro každé j, pak jistě existuje v poněkud komplikovaném tvaru - nechť je tento počet pro každé j dán výrazem K(j). Potom pro libovolné m je dán tento vzorec např. výrazem $\sum_i{(1-|sign(m-i)|)K(i)}$ .

Andrejka3 · 01. 03. 2012 20:30

check_drummer napsal(a):
↑ Andrejka3:
...
Na druhou stranu, pokud existuje pro každé j, pak jistě existuje v poněkud komplikovaném tvaru - nechť je tento počet pro každé j dán výrazem K(j). Potom pro libovolné m je dán tento vzorec např. výrazem $\sum_i{(1-|sign(m-i)|)K(i)}$ .

Ahoj. Díky za odpověď.
Ano, dávám jen návod, jak vzorec sestavit. Spočítala jsem vždy jen levou stranu (explicitně), ale pravou s tou Moivre větou jsem se nezabývala prozatím. Přesně, jak píšeš. Ráda bych našla nějaký vzorec obecný. :D
Bohužel nerozumím tomu dalšímu, co píšeš. V diskrétce toho ještě moc nevím.

check_drummer · 01. 03. 2012 21:43

↑ Andrejka3:
Já už tam ale žádnou další myšlenku nemám. :-)

Andrejka3

Zobecnění pro $j=\Pi_{l=1}^m p_l$ , kde $p_l$ jsou různá prvočísla:

Pozorování 2
$\Psi_k$ definované v (13) je endomorfismem na grupě řešení rovnice (2) (díky komutativitě).
Platí: $j|k \Rightarrow \Psi_k$ je triviální endomorfismus.
Zobrazení $\Psi_k$ budu úžit na menší podmnožiny (podgrupy).

Vyšetřujme koeficienty u členu ${n \choose k}$ pro $k=0, \dots,n$ (poté, co podle návodu dosadíme řešení (2) do (1) a rovnice sečteme).
1) Pro $j|k \Rightarrow \Psi_k$ triviální a koeficient je $j$ .
2) Pro $j \nmid k$ BÚNO $p_1 \nmid k,\dots, p_d \nmid k$ a zbytek, $p_{d+1} |k, \dots, p_m|k$ .
Potom $\Psi_k$ zúženo na $\varphi(\mathbb{Z}_{p_1} \times \dots \times \mathbb{Z}_{p_d} \times \{0\} \times \dots \times \{0\})$ ,

Autor skryl část textu. Zobrazit/skrýt!

je automorfismus, protože

Autor skryl část textu. Zobrazit/skrýt!

Je tedy $\forall (a_{d+1},\dots, a_m) \in \mathbb{Z}_{p_{d+1}} \times \dots \times \mathbb{Z}_{p_m}$ pevné
součet prvků množiny $\Psi_k(\varphi(\mathbb{Z}_{p_1} \times \dots \times \mathbb{Z}_{p_d} \times \{a_{d+1}\} \times \dots \times \{a_m\}))$ roven nule (Pozorování).
Celkem sčítáme $\Pi_{i=d+1}^m p_i$ takových nul, což je nula :)
V případě, že $d=m$ , máme nulu jednu :)
Levá strana je ve tvaru
$j \sum_{\substack{k=0\\j|k}}^n {n \choose k}$ (14)

Andrejka3 · 05. 03. 2012 17:30

$j=p^{\nu}$ ,
kde $p$ je prvočíslo a $\nu \in \mathbb{N}$ .
Multiplikativní grupa řešení rovnice (2) (značme ji $\mathbb{C}_j$ ) je cyklická a její řád je $p^{\nu}$ . Má celkem $\nu+1$ podgrup, $\mathbb{C}_{p^i},i=0,\dots,\nu$ . Zároveň platí následující řetězec inkluzí:

$\mathbb{C}_1 \subset \mathbb{C}_{p} \subset \dots \subset \mathbb{C}_{p^{\nu}}$ (15)
Postupujme jako u jiných případů. Již jsme dosadili řešení (2) do (1) a rovnice sečetli, upravujeme levou stranu a zkoumáme koeficienty u čísla ${n \choose k}$ pro každou mocninu $k=0,\dots,n$ . Budeme označovat, podobně jako dříve, $\Psi_k: x \in \mathbb{C}_{p^{\nu}} \mapsto x^k$

Pokud $p^{\nu}|k$ , pak $\Psi_k$ je triviální endomorfizmus a před členem ${n \choose k}$ dostaneme $j=p^{\nu}$ .
Pokud $\mathrm{D}(k,p^{\nu})=1$ , tedy jsou nesoudělná, pak $\Psi_k$ je automorfizmus. (Důkaz prostoty vede na rovnici $\left(xy^{-1}\right)^k=1$ , jež má v tomto případě jediné řešení.) Díky Pozorování je koeficient u ${n \choose k}$ nulový.
Pokud nakonec $\mathrm{D}(k,p^{\nu})=p^m$ pro nějaké pevné $m \in \{1,\dots, \nu-1\}$ , pak můžeme psát: $k = p^mq$ , kde $q$ je nesoudělné s $p^{\nu}$ . Také je zřejmě $\Psi_k= \Psi_{p^m} \circ \Psi_q$ . $\Psi_q$ je automorfizmus a tedy se můžeme rovnou zabývat $\Psi_{p^m}$ . $\Psi_{p^m}: \mathbb{C}_{p^{\nu}} \rightarrow \mathbb{C}_{p^{\nu-m}}$ a to na. Surjektivnost je zřejmá: volme $y \in {p^{\nu-m}}$ . Rovnice $x^{p^m}=y$ má v $\mathbb{C}$ právě $p^m$ řešení a protože pro každé takové řešení $x$ je také $x^{p^{\nu}}=y^{p^{\nu-m}}=1$ , je $x \in \mathbb{C}_{p^{\nu}}$ . Dostaneme tedy součet prvků podgrupy $\mathbb{C}_{p^{\nu-m}}$ celkem $p^m$ -krát, což je $p^m$ -krát nula.

Teď ale zbývá vyřešit obecný případ... ach jo.

check_drummer · 05. 03. 2012 19:25

↑ Andrejka3:
Ahoj, trošku mimo: Ne zas tak špatný odhad tohoto počtu je triviální: $\frac{2^n}{j}$ . Přemýšlel jsem, zda porovnáním blízkých binomických koeficientů není možné tento odhad nějak vylapšit nebo dokonce získat přesný hledaný počet, ale nic mě zatím nenapadlo.

Andrejka3 · 05. 03. 2012 19:38

↑ check_drummer:
Ahoj. To jo. :)
Jsem ráda, že tu píšeš.

Andrejka3

$j=\Pi_{i=1}^m p_i^{\nu_i}$ ,
kde $p_i$ jsou navzájem různá prvočísla.
$\mathbb{C}_j \simeq \times_{i=1}^m \mathbb{C}_{p_i^{\nu_i}}$ a $\Psi_k: x \in \mathbb{C}_j \mapsto x^k$ pro nějaké pevné $k \in \{0, \dots , n\}$ je endomorfizmus, který lze přirozeně rozdělit na $m$ endomorfismů působících na jednotlivých komponentách direktního součtu,
$\Psi_{k,i}:x_i \in \mathbb{C}_{p_i^{\nu_i}} \mapsto x_i^k$ . Tyto jsme vyřešili v předchozích případech.
Zapíšeme-li $k=a\Pi_{i=1}^m p_i^{\mu_i}$ , kde $\mathrm{D}(a,\Pi_{i=1}^m p_i^{\nu_i})=1$ a označíme-li $\alpha_i:=\max \{0,\nu_i-\mu_i\}$ , pak
$\Psi_{k,i}: \mathbb{C}_{p_i^{\nu_i}} \rightarrow \mathbb{C}_{p^{\alpha}}$ a to na a každý obraz má právě $\min \{p^{\nu_i},p^{\mu_i}\}$ vzorů.

Pozn.: Takto bych měla opravit i případ pro $j= \Pi_{i=1}^m p_i$ .

Pak na levé straně (po dosazení všech řešení (2) do (1) a sečtení rovnic) dostaneme pro pevné $k$ u členu ${n \choose k}$ součet všech prvků grupy $\times_{i=1}^m \mathbb{C}_{p_i^{\alpha_i}}$ , celkem $\Pi_{i=1}^m p_i^{\min \{\mu_i,\nu_i\}}$ -krát. Tedy stejněkrát nulu, pokud $j \nmid k$ a tolikrát jedničku, pokud $j|k$ .
Na levé straně zůstane
$j \sum_{\substack{k=0\\j|k}}^n {n \choose k}$ .

Andrejka3

Pokud to je správně, zbývá vyřešit pravou stranu. Spočítat výrazy
$\exp(i\frac{2\pi}{j}l)+1$ stačí pro $l=0,\dots ,\lfloor j/2\rfloor$ , kde $\lfloor \cdot \rfloor$ značí dolní celou část čísla. Velikost těchto komplexních čísel bych asi vyjádřila pomocí úhlu, ještě nevím, jak přesně. Argument bude zřejmě poloviční, tj. $\frac{\pi}{j}l$ . Pak dostaneme postupně součty tohoto typu: $? \cdot 2\cos\left(\frac{\pi}{j}l\right)$ .

Andrejka3

Pravá strana.
Označme $\alpha_l=\frac{2\pi}{j}l$ , pro $l=1,\dots,\lfloor j/2 \rfloor$ . Tyto argumenty/úhly jsou menší nebo rovny $\pi$ . Stačí mi vzít tyto, protože zbylé jsou od čísel k nim komplexně sdružených. Ty, které nemají komplexně sdruženého partnera - jednička a minus jednička: jedničku dám zvlášť, minus jednička pak vytvoří nulu, takže ji můžu zahrnout v dalším počítání, totiž:
$1+\exp(i\alpha_l)$ chci umocnit na $n$ a pak sečíst s cpx sdruženým, tj. vzít 2 krát reálnou část.
Po nakreslení obrázku mi vychází
$|1+\exp(i\alpha_l)|=2\cos\left(\frac{\alpha_l}{2}\right)$ .
Argument součtu je $\alpha_l/2$ .
Po umocnění, $\left(1+\exp(i\alpha_l)\right)^n=\left(2\cos\left(\frac{\alpha_l}{2}\right)\right)^n\exp\left(in\alpha_l\right)$ a vezmeme-li dvakrát reálnou část a dosadíme za $\alpha_l$ , dostaneme
$2\left(2\cos\left(\pi \frac{l}{j}\right)\right)^n\cos\left(n\pi \frac{l}{j}\right)$ .
Pravá strana vychází
$2^n+2\sum_{l=1}^{\lfloor j/2 \rfloor }\left(2\cos\left(\pi \frac{l}{j}\right)\right)^n\cos\left(n\pi \frac{l}{j}\right)$ a tedy
$\sum_{\substack{k=0\\j|k}}^n{n \choose k}=\frac{2^n}{j}+\frac{2^{n+1}}{j}\sum_{l=1}^{\lfloor j/2 \rfloor }\cos^n\left(\pi \frac{l}{j}\right)\cos\left(n\pi \frac{l}{j}\right)$ .
Jak psal kolega check_drummer, je tam vidět první odhad $2^n/j$ a pak nějaké opravy.
Kdybyste našli chyby, měli připomínky, nebo jste došli ke stejnému výsledku, budu moc ráda, když napíšete.
edit: o neco hezci zapis posledniho vztahu.

check_drummer · 07. 03. 2012 20:25

↑ Andrejka3:
Ahoj, stačí si přečíst tento příspěvek a pak všechny níže nebo jsou důležité pro celkové řešení všechny? Děkuji.

Andrejka3

↑ check_drummer:
Ahoj, podstatné jsou ↑ 10:,↑ 11:,↑ 15:,↑ 17:.
Přemýšlím o tom, že to přepíšu do kupy. Cestou jsem možná našla lepší způsoby, jak na to - aspoň se mi zdá, že pozdější příspěvky jsou hezčí (a kratší).
Edit: možná, že pro ty, kteří znají dobře cyklické grupy to je zbytečně rozvláčné, ale pro mě to bylo docela objevné...

Andrejka3

Shrnutí:
Potřebujeme binomickou větu ve tvaru
$(\forall n \in \mathbb{N})(\forall x \in \mathbb{C}): \sum_{k=0}^n {n \choose k} x^k = (1+x)^n$ . (i=1)
Pro pevné $j \in \mathbb{N}$ je množina všech řešení rovnice
$x^j=1$ (ii=2)
tato: $\{\exp\left(i \frac{2\pi}{j}l\right);\; l \in \{0,1,\dots,j-1\}\}$ . Tato množina spolu s operací násobení tvoří cyklickou grupu, kterou budeme značit $\mathbb{C}_j$ .
Dosadíme postupně všechny její prvky do (i), vzniklých $j$ rovnic sečteme a výsledná rovnice bude mít levou stranu ve tvaru součtu kombinačních čísel přenásobených nějakými koeficienty a pravá je součtem nějakých komplexních čísel. Budu-li dál psát o "levé/pravé" straně rovnice a nebude jasné které, budu mít na mysli tuto rovnici.
Úprava "levé strany":

Autor skryl část textu. Zobrazit/skrýt!

Úprava "pravé strany" a konečný výsledek je ↑ tady:.

Andrejka3 · 18. 02. 2014 20:41

Po delším čase jsem se vrátila k tomuto příkladu, abych si ho zapsala do poznámek v TeXu. Přitom jsem snad zjednodušila některé argumentace, i když podstata je stejná:
//forum.matweb.cz/upload3/img/2014-02/52132_subsets.png
$\nu_p(a)\stackrel{\text{\tiny def}}{=}\max\{n\in\mathbb{N}_0;\:p^n\mid a\}$

Matematické Fórum

#1 26. 02. 2012 10:12 — Editoval Andrejka3 (26. 02. 2012 10:28)

Počet podmnožin, jejichž velikost je dělitelná daným číslem

#2 26. 02. 2012 19:57

Re: Počet podmnožin, jejichž velikost je dělitelná daným číslem

#3 26. 02. 2012 20:13

Re: Počet podmnožin, jejichž velikost je dělitelná daným číslem

#4 27. 02. 2012 00:49 — Editoval vanok (27. 02. 2012 00:51)

Re: Počet podmnožin, jejichž velikost je dělitelná daným číslem

#5 27. 02. 2012 07:05

Re: Počet podmnožin, jejichž velikost je dělitelná daným číslem

#6 01. 03. 2012 19:01 — Editoval Andrejka3 (01. 03. 2012 19:49)

Re: Počet podmnožin, jejichž velikost je dělitelná daným číslem

#7 01. 03. 2012 20:09

Re: Počet podmnožin, jejichž velikost je dělitelná daným číslem

#8 01. 03. 2012 20:30

Re: Počet podmnožin, jejichž velikost je dělitelná daným číslem

check_drummer napsal(a):

#9 01. 03. 2012 21:43

Re: Počet podmnožin, jejichž velikost je dělitelná daným číslem

#10 02. 03. 2012 12:19 — Editoval Andrejka3 (02. 03. 2012 12:21)

Re: Počet podmnožin, jejichž velikost je dělitelná daným číslem

#11 05. 03. 2012 17:30

Re: Počet podmnožin, jejichž velikost je dělitelná daným číslem

#12 05. 03. 2012 19:25

Re: Počet podmnožin, jejichž velikost je dělitelná daným číslem

#13 05. 03. 2012 19:38

Re: Počet podmnožin, jejichž velikost je dělitelná daným číslem

#14 05. 03. 2012 19:42 — Editoval Andrejka3 (05. 03. 2012 20:26) Příspěvek uživatele Andrejka3 byl skryt uživatelem Andrejka3. Důvod: skryto pro blbost.

#15 06. 03. 2012 10:01 — Editoval Andrejka3 (08. 03. 2012 09:59)

Re: Počet podmnožin, jejichž velikost je dělitelná daným číslem

#16 06. 03. 2012 10:09 — Editoval Andrejka3 (06. 03. 2012 16:14)

Re: Počet podmnožin, jejichž velikost je dělitelná daným číslem

#17 06. 03. 2012 16:08 — Editoval Andrejka3 (10. 03. 2012 16:48)

Re: Počet podmnožin, jejichž velikost je dělitelná daným číslem

#18 07. 03. 2012 20:25

Re: Počet podmnožin, jejichž velikost je dělitelná daným číslem

#19 07. 03. 2012 21:02 — Editoval Andrejka3 (07. 03. 2012 21:43)

Re: Počet podmnožin, jejichž velikost je dělitelná daným číslem

#20 08. 03. 2012 08:00 — Editoval Andrejka3 (08. 03. 2012 09:58)

Re: Počet podmnožin, jejichž velikost je dělitelná daným číslem

#21 18. 02. 2014 20:41

Re: Počet podmnožin, jejichž velikost je dělitelná daným číslem

Zápatí