Matematické Fórum

Trab · 21. 03. 2015 18:04

Úloha z knihy od Donalda Knutha, Umění programování, kapitola celočíselné funkce a teorie čísel.

//forum.matweb.cz/upload3/img/2015-03/57233_ss.jpg

Máme úlohu zadanou jako "domácí úkol" do Diskrétní matematiky. Mám u těchto dokazovacích úloh problém s tím jak začít, nedokážu si představit, čeho bych chtěl využít atd., tak jestli k tomu máte nějakou obecnou radu. Když pak vidím postup řešení, tak mi to bývá víceméně jasné. Například u této konkrétní úlohy vůbec nevím od čeho se odpíchnout. Ocením myšlenku, řešení, cokoliv :)

vanok · 21. 03. 2015 19:24

Ahoj ↑ Trab:,
Mozno by bolo poucne, najprv vysetrit 2 jednoduchsie situacie
1) (m,n)=1, x=0
2) (m,n)=d, x=0

Trab · 22. 03. 2015 12:00 — Editoval Trab (22. 03. 2015 12:01)

↑ vanok:

v prvním případě jsem došel k rovnosti 0=0, v druhém případě $(d^2-d)/2=(d^2-d)/2$
zatim to můj myšlenkový pochod nenastartovalo :D, zřejmě by chtělo vymyslet, jak se v sumě zbavit dolní celé části, ale žádná úprava mě nenapadá.

vanok · 22. 03. 2015 14:25 — Editoval vanok (22. 03. 2015 14:25)

Ahoj
Ja som dostal v prvom pripade $\frac {(m-1)(n-1)}2$
V druhom $\frac {(m-1)(n-1)}2+ \frac {d-1}2$

Trab · 22. 03. 2015 14:53

↑ vanok:

hádám že zápisem (m,n) = 1 (d) je myšleno NSD(m,n) =1 (d). Moje chyba bral jsem to jako m=1 & n=1 ... Zkusim se nad tím, ještě zamyslet, jestli něco nevymyslím.

vanok · 22. 03. 2015 15:34 — Editoval vanok (22. 03. 2015 15:35)

↑ Trab:,
Ja som zacal pracovat na $\{ (x,y)| 1\le x \le n-1, 1\le y \le m-1\}$ .
Tiez som pozeral na to co sa deje na priamke $y=\frac mn x$ .
Tak dobre pokracovanie.

Trab · 22. 03. 2015 20:08 — Editoval Trab (22. 03. 2015 20:22)

↑ vanok:

Našel jsem k tomu návod, z toho to snad pude vykoukat. Jestli jsem to dobře pochopil tak:

$\frac{m(n-1)}{2} + x - S$ = té pravé straně ze zadání

Zítra to zkusim dodělat, dnes jsem KO.

//forum.matweb.cz/upload3/img/2015-03/51099_ma.jpg

vanok · 22. 03. 2015 20:33

↑ Trab:,
Dobre pokracovanie.

Trab · 23. 03. 2015 17:07

nemůžu se dostat přes to, jak z té sumy desetinných částí udělali součet řady.

//forum.matweb.cz/upload3/img/2015-03/26701_maa.jpg

Trab · 23. 03. 2015 17:31

↑ Trab:

víceméně nechápu ani ten další krok, tam hrozně přeskakujou v tom postupu nebo jsem hloupej? :D

vanok · 23. 03. 2015 17:47

Ak d je spolocny delitel, celych m,n tak t=n/d musi byt cele cislo. ... Potom to nezmeni {}.
No vsak oznacenie $t\perp u$ nepoznam .
(Ja som zatial dokazal tie dve jednoduche situacie. ↑ vanok:)

Kde si nasiel tvoje riesenie?

Trab · 23. 03. 2015 18:01

je to na konci té knížky, takovýhle pseudo návody. Tak jsem jí stáhnul (měl jsem jenom začátek knihy).

Trab · 26. 03. 2015 22:08

někdo nějaká pomoc? já to nedávám.

Trab · 28. 03. 2015 15:11

Nevím jak dospět k S.

Shrnutí návodu:
//forum.matweb.cz/upload3/img/2015-03/51665_sass.jpg

Zde je vidět, že to funguje:

Brano · 28. 03. 2015 17:34

takze si to ujasnime:
to co si nakopiroval sem ↑ Trab: podla mna nie je navod, ale (skoro) cele riesenie - chyba tam len posledne dosadenie a uprava (ale to si vpohode zvladol sam ako vidiet z predchadzajuceho prispevku)

tak skus este raz presne napisat co nie je jasne a skusim to potom dovysvetlit.

Trab · 28. 03. 2015 18:02

↑ Brano:

nevím jak jsme se od té sumy desetinných částí, dostali k tomu výslednému S. Nedokážu prohlédnout ty úpravy v tom návodu.

Brano · 28. 03. 2015 20:17 — Editoval Brano (28. 03. 2015 20:29)

Tak skusme to takto:
$(m,n)=d$ - to je NSD cize $m=d.u$ a $n=d.t$ pricom $(u,t)=1$ . To $x\text{ mod }d$ oznacme $y$ a je to vlastne $y=d\{x/d\}$ cize $x=y+a.d$ kde $a$ je cele cislo. Cize potom mame
$\{\frac{mk+x}{n}\}=\{\frac{duk+y+ad}{dt}\}=\{\frac{y}{n}+\frac{uk+a}{t}\}=\{\frac{y}{n}+\frac{uk+a}{t}-b\}$ kde v poslednom vyraze si mozes zvolit za $b$ lubovolne cele cislo, lebo ta desatinna cast ho zabije.
Teraz si vsimnime vyraz $\frac{uk+a}{t}-b=\frac{uk+a-bt}{t}$ a ked zvolis vhodne $b$ tak sa ti to upravi na $\frac{(uk+a)\text{ mod }t}{t}=:\frac{f(k)}{t}$ .
Plati $0\le f(k)\le t-1$ a $0\le y<d$ cize $\frac{y}{n}+\frac{f(k)}{t}<1$ a teda $\{\frac{y}{n}+\frac{f(k)}{t}\}=\frac{y}{n}+\frac{f(k)}{t}$ .
Podme sa teraz pozriet na to ako sa sprava $f(k)$ - pre aku dvojicu $k,l$ sa mozu zhodovat. $uk+a=ul+a\mod t$ prave vtedy ked $t|u(k-l)$ ale kedze $(t,u)=1$ tak to je prave vtedy ked $t|(k-l)$ to znamena, ze ked beries $k$ od $0$ po $t-1$ tak $f(k)$ nadobuda rozne hodnoty, lenze tie mozu byt iba z rozsahu $0$ az $t-1$ takze su tam vsetky a ked beries $k$ od $0$ po $n-1$ tak sa tam $d$ -krat zopakuju. Teda
$S=\sum_{0\le k<n}\{\frac{y}{n}+\frac{f(k)}{t}\}=\sum_{0\le k<n}\left(\frac{y}{n}+\frac{f(k)}{t}\right)=y+\sum_{0\le k<n}\frac{f(k)}{t}=$
$=y+d\sum_{0\le k<t}\frac{f(k)}{t}=y+\frac{d}{t}\sum_{0\le k<t}k=y+d\frac{t-1}{2}$ .

Trab · 28. 03. 2015 22:43

↑ Brano:

moc děkuju za odpověď. jsem venku, zítra na to hned vlétnu.

Trab · 29. 03. 2015 11:48

↑ Brano:

tak vše pochopeno, dávám určitě plusko a uzavírám.

vanok · 29. 03. 2015 18:09 — Editoval vanok (29. 03. 2015 20:18)

Pozdravujem ↑ Brano:,
Mozes ma poucit prosim?
Co znamena zapis $t\perp u$
A tiez x mod d ked x je réal ne cislo?
Dakujem.

Trab · 29. 03. 2015 19:30

↑ vanok:
$t\perp u$ znamená nesoudělné a x mod d = x - d* [x/d] kde [] = dolní celá část, aspoň co já vim :D

vanok · 31. 03. 2015 14:49 — Editoval vanok (31. 03. 2015 14:51)

Ahoj ↑ Trab:,
Nasiel som iny hint.
$[nx]= [x]+[\frac 1n +x]+...+[\frac {n-1}n +x]$
Zda sa, podla dokazu co som urobil, ze ani netreba pouzit funkciu {}.

byk7 · 31. 03. 2015 16:57

↑ vanok: To jsem se pokoušel použít, ale nepovedlo se mi to, jak to tedy udělat?

vanok · 31. 03. 2015 20:21

Ahoj ↑ byk7:,
Len co budem mat cas ti to tu napisem.
Ale aby som nemusel pisat kilometrove vzorce, ukazem to v pripade ked
m=6 a n=4. ( co staci na pochopenie principu dokazu).

vanok · 03. 04. 2015 02:44 — Editoval vanok (07. 04. 2015 18:01)

Ako som to slubil dokazem tento vzorec
$\sum_{0\le k<n}^{}[\frac{mk +x }n]=\frac {(m-1)(n-1)}2+ \frac {d-1}2+d[\frac xd]$ ( detaily v prvom prispevku)
v pripade ak n=4 a m=6.
Najprv poznamenajme, ze
$[nx]= [x]+[\frac 1n +x]+...+[\frac {n-1}n +x]$
je envivalentne z
$[x]=[\frac xn]+[\frac {x+1} n]+... +[\frac {x+n-1}n]$ Co moze byt uzitocne v dokaze.
Vysetrime teraz
$\sum_{0\le k<4}^{}[\frac{mk +x }4]=[\frac x4]+[\frac {x+m}4] +[\frac {x+2m}4]+[\frac {x+3m}4]$
Co nam napr. pre m formy $m=4i+1$ da cele cislo $\frac {m-1}4$ a
$\sum_{0\le k<4}^{}[\frac{mk +x }4]=[\frac x4]+[\frac {x+1}4] +\frac {m-1}4 +[\frac {x+2}4]+2\frac {m-1}4+[\frac {x+3}4]+3\frac {m-1}4 =\\ [ x]+\frac {3m}2-\frac 32$
Podobne pre m formy $m=4i+2$ dostaneme cele cislo $\frac {m-2}4$ a po podobnom vypocte
$\sum_{0\le k<4}^{}[\frac{mk +x }4]=[\frac x4]+[\frac {x+1}4] +\frac {m-2}4 +[\frac {x+2}4]+2\frac {m-2}4+[\frac {x+3}4]+3\frac {m-2}4 =\\ 2[\frac x4] +2[\frac{x +2}4] +\frac {3m} 2 -1= 2([\frac {(\frac x2)}2]+ [\frac {(\frac x2+ 1)}2]) +\frac {3m} 2 -1=2[\frac x2] +\frac {3m} 2 -1$
Ak najviac $m=6$ , dostaneme $2[\frac x2]+ 8$
Co je v sulade z hladanym vysledkom
$\sum_{0\le k<n}^{}[\frac{mk +x }n]=\frac {(m-1)(n-1)}2 + \frac {d-1}2 +d[\frac xd]$
Édit.
Mozno, nasledujuca jednoducha poznamka ukaze tym, co este neveria tomuto dokazu, ze vlastne cely dokaz, je ozaj jednoduchy.
V uvedenych upravach sa pouzili vlasnosti najvädcieho spolocneho delitela d cisiel m,n: presnejsie, cisla $0, m,2 m, ...,m(d-1)$ su vsetki rozne,. Tiez je to tak v pre kazdich d nasledujucich clenov postupnosti $mk$ . To znamena, ak n=da, tak v postupnosti $0, m,2m,...,m( n-1)$ kazde z cisiel $0, m,2 m, ...,m(d-1)$ sa opakuje a krat modulo n.