Як даказаць $ \ налева \ lceil \ гидроразрыва {п} {т} \ права \ rceil = \ налева \ lfloor \ гидроразрыва {п + т-1} {т} \ права \ rfloor $?

ўсё, як я магу даказаць, што для натуральнага $ M $ і $ N $, $$ \ Налева \ lceil \ гидроразрыва {п} {т} \ права \ rceil = \ налева \ lfloor \ гидроразрыва {п + т-1} {т} \ права \ rfloor \; ? $$ Вялікі дзякуй.

10
Ці магу я лічыць, $ м $ і $ N $ з'яўляюцца натуральнымі лікамі?
дададзена аўтар simplename, крыніца
п і т у натуральным ліку
дададзена аўтар Moebius, крыніца

9 адказы

Калі мы робім невялікую алгебру на правай баку, мы атрымліваем:

$$ \ налева \ lfloor \ гидроразрыва {п + т-1} {т} \ направа \ rfloor = \ налева \ lfloor \ гидроразрыва {п-1} {т} \ права \ rfloor + 1 $$

Спадзяюся, усё павінна быць ясна, з гэтага моманту. :)

13
дададзена

Яркі канцэптуальная Доказ: $ \: $ Калі $ \ ет \: [а, Ь] \: $ ўтрымліваюць унікальнае цэлы лік $ \ ет \: к \: $ то, відавочна, $ \ ет \ \ lceil а \ rceil \: = \: к \: = \: \ lfloor б \ rfloor \ :. $

Гэта адносіцца і да $ \ тт \: \ а = п/м, \: \ Коммерсанта = (N + M-1)/т \ :. \: $ Звярніце ўвагу, што $ \ тт \: [а, Ь] \: $ змяшчае ўнікальны лік пачынаючы з $ \ тт \: т \: $ дзеліць роўна адзін з паслядоўнага $ \ тт \: т \: $ цэлых лікаў $ \ тт \: п \: п + 1, \: \ cdots, \: п + т-1 \ :. $

Note $\ $ This problem is exercise 3.12 in Graham; Knuth; Patashnik: Concrete Mathematics. Curiously they overlook this simple solution, instead giving essentially the solution in my other answer here.

7
дададзена
дзякуй за вашу кнігу, якая прадставіла
дададзена аўтар Moebius, крыніца

By the division algorithm $\rm\ n\: =\: k\ m + r,\ \ 0\le r < m\:.\:$ Substituting, the sought identity becomes

$$ \ тт \ налева \ lceil {\ к \ + \: \ гидроразрыва {г} т} \ \ права \ rceil \ = \ \ налева \ lfloor {\ к \ + \: \ гидроразрыва {г + м- 1} м \} \ права \ rfloor $$

Гэта дакладна, так як абодва бакі роўныя $ \ ГТ \: к \: $, калі $ \ ГТ \: г = 0 \: \: $ яшчэ роўны $ \ ГТ \: да + 1 \ $, калі $ \ ГТ \ 1 \ ль г \ ль т-1 \: $

4
дададзена

<�Моцны> ПОДСКАЗКА

We can always write $n = mk - r$ where $0 \leq r < m$ and hence $$\left \lceil \frac{n}{m} \right \rceil = k.$$ Try to argue from this what $\left \lfloor \frac{n+m-1}{m} \right \rfloor$ is.

4
дададзена

$ (П + т-1)/т = п/т + 1-1/м $. можа $ 1-1/м $ ў $ \ GEQ (м-п)/м = 1-н/м $?

\ BEGIN {выраўноўваюцца} \ Гидроразрыва {п + т-1} {т} = \ гидроразрыва {п} {т} + 1 \ гидроразрыва {1} {т} \ \ \ Можна даказаць: \ 1- \ гидроразрыва {1} {M} \ GEQ \ гидроразрыва {т-п} {т} = 1- \ гидроразрыва {N} {M} \ {Канец выраўнаваны}

3
дададзена

Зацвярджэнне ілжыва для рэальнага $ N $ і $ M $. Возьмем $ п = \ пі $ і $ M = -3 $ за контрпримера. Гэта не дакладна нават для цэлых $ N $ і $ M $. Возьмуць $ N = 3 $ і $ M = -3 $ за контрпримером.

Хай $ N $ і $ M $ з'яўляюцца станоўчыя цэлыя лікі . Хай $ \ хі _ {\ ч, X} (х) $ пазначым характарыстычнай функцыю $ X _ {\ ФТ} $ вызначаецца як $ 1 $, калі $ х \ ў X _ {\ ФТ} $ і $ 0 $ у адваротным выпадку. запіс \ {Пачаць выраўноўваць} \ Lceil \ tfrac {п} {т} \ rceil = \ tfrac {N} {M} - \ lbrace \ tfrac {п} {т} \ rbrace + \ хі _ {+ \ mathbb {R}, \ setminus \ mathbb { Z}} (\ tfrac {п} {т}) \ Канец {} Align і, аналагічна, \ {Пачаць выраўноўваць} \ Lfloor \ tfrac {п + т - 1} {т} \ rfloor = \ tfrac {п} {т} + 1 - \ tfrac {1} {т} - \ lbrace \ tfrac {п-1} {т} \ rbrace \ Канец {} Align ад $ 1 $ -периодичности функцыі дробавай часткі. Калі патрабаванне, каб быць праўдай, то гэта павінна быць, \ {Пачаць выраўноўваць} \ Lbrace \ tfrac {п} {т} \ rbrace - \ lbrace \ tfrac {п - 1} {т} \ rbrace = \ tfrac {1} {м} + \ хі _ {+ \ mathbb {R}, \ setminus \ mathbb {Z}} (\ tfrac {п} {т}) - 1. \ Канец {} Align якая сапраўды ідэнтычнасць. Дадатковыя фактары, апрацоўваюць выпадак, калі $ м $ дзеляць $ N $, у гэтым выпадку \ {Пачаць выраўноўваць} \ Lbrace \ tfrac {п} {т} \ rbrace - \ lbrace \ tfrac {п - 1} {т} \ rbrace = \ tfrac {1} {т} + 0 - 1. \ Канец {} Align

1
дададзена
п і т у N. Дзякуй
дададзена аўтар Moebius, крыніца

Гэта ў асноўным рашэнне Біла, я ўспомніў даволі добры спосаб напісання яго:

дазваляць

$ F: {\ mathbb Z} _ + \ RightArrow {\ mathbb R} $ вызначаецца

$$ F (X) = \ налева \ lceil \ гидроразрыва {х} {т} \ направа \ rceil - \ злева \ lfloor \ гидроразрыва {х + м-1} {т} \ права \ rfloor \, $$.

тады

$$ F (х + т) = \ налева \ lceil \ гидроразрыва {х + т} {т} \ права \ rceil - \ злева \ lfloor \ гидроразрыва {х + 2m-1} {т} \ права \ rfloor = \ левая \ lceil \ гидроразрыва {х} {т} \ права \ rceil + 1 \ налева \ lfloor \ гидроразрыва {х + м-1} {т} \ направа \ rfloor -1 = F (X) $$

Такім чынам, $ F $ з'яўляецца перыядычным з перыядам $ M $.

Акрамя таго $ F (0) = 0 $, і для ўсіх $ 1 \ Leq х \ Leq м-1 \ ,; \, F (X) = 1-1 = 0 $.

Так як $ F $ з'яўляецца перыядычным і тоесна нуля на перыяд, $ F $ з'яўляецца нулявы функцыяй.

І апошняе, але не ў апошнюю чаргу, лёгка бачыць, што калі замяніць $ х \ у {\ mathbb Z} $ на $ х $ станоўчае лік, адзіны крок, які трывае няўдачу ў тым, што $ е (х) \ NEQ 0 $ для $ х \ у (0,1) $.
Так што, калі я не зрабіў памылку роўнасць мае месца на $ [0, \ infty) \ зваротны слэш [(0,1) + {\ mathbb Z}] $.

0
дададзена

Акрамя таго, мы можам даказаць гэта з дапамогай $$ (0) \; \; \; р = д \; \ эквив \; \ Лангле \ FORALL да :: к \ Leq р \ эквив к \ Leq д \ rangle $$ якія я даведаўся ад адказу Біла на іншы паверх пытанне .

Starting at the most complex side of the equality, we calculate for all $\;k\;$: \begin{align} & k \le \left \lfloor \frac{n+m-1}{m} \right \rfloor \\ \equiv & \qquad \text{"basic property of floor, allowed since $\;k\;$ is integer"} \\ & k \le \frac{n+m-1}{m} \\ \equiv & \qquad \text{"arithmetic -- to get closer to the shape of the LHS of our equality"} \\ & k \le \frac{n}{m} - \frac{1}{m} + 1 \\ \equiv & \qquad \text{"we may add $\;\frac{1}{m}\;$ if we change $\;\le\;$ to $\;\lt\;$: $\;k\;$ is integer and $\;0 < \frac{1}{m}< 1\;$"} \\ & k \lt \frac{n}{m} + 1 \\ \equiv & \qquad \text{"basic property of ceiling, allowed since $\;k\;$ is integer"} \\ & k \le \left \lceil \frac{n}{m} \right \rceil \\ \end{align}

Да $ (0) $ гэта даказвае роўнасць.

0
дададзена

што пра матэматычнай індукцыі даказаць: п і т гэта натуральны лік:

\ Пачынаюцца {выраўнаваны} т = 1 \ RightArrow \ злева \ lfloor \ гидроразрыва {1 + п-1} {1} \ права \ rfloor = \ налева \ lceil \ гидроразрыва {п} {1} \ права \ rceil \ RightArrow дакладна \ {канец выраўнаваны}

\ Пачынаюцца {выраўнаваны} т = 2 \ RightArrow \ злева \ lfloor \ гидроразрыва {2 + п-1} {2} \ права \ rfloor = \ налева \ lceil \ гидроразрыва {N} {2} \ права \ rceil \ RightArrow дакладна \ {канец выраўнаваны}

\ {Пачынаюцца выраўнаваны} \ налева \ lceil \ гидроразрыва {N} {2} \ права \ rceil = \ {пачынаюць Bmatrix} \ Гидроразрыва {N} {2} \ п \ \ нават \ \ \ Гидроразрыва {п + 1} {2} \ п \ \ няцотных \ Канец {Bmatrix} \ {Канец выраўнаваны}

\ BEGIN {выраўноўваюцца} калі \ т = к \ RightArrow \ налева \ lfloor \ гидроразрыва {да + п-1} {да} \ направа \ rfloor = \ налева \ lceil \ гидроразрыва {п} {да} \ права \ rceil \ {Канец выраўнаваны}

\ BEGIN {выраўноўваюцца} даказаць \ т = да + 1 \ Rightarrow \ левай \ lfloor \ гидроразрыва {да + 1 + п-1} {да + 1} \ права \ rfloor = \ налева \ lceil \ гидроразрыва {п} {да + 1} \ направа \ rceil \ {Канец выраўнаваны}

\ BEGIN {выраўноўваюцца} \ Налева \ lfloor \ гидроразрыва {п-1} {да + 1} + 1 \ справа \ rfloor = \ налева \ lceil \ гидроразрыва {п} {да + 1} \ права \ rceil \ {Канец выраўнаваны}

\ BEGIN {выраўноўваюцца} \ Налева \ lfloor \ гидроразрыва {п-1} {да + 1} \ права \ rfloor + 1 = \ налева \ lceil \ гидроразрыва {п} {да + 1} \ права \ rceil \ {Канец выраўнаваны} ...?

0
дададзена
Тры заўвагі: 1) Ваш апошні крок такі ж, алгебраічная маніпуляцыя, як мой адказ. 2) Я адчуваю, што вы яшчэ не скончылі працэс індукцыі. 3) Вы можаце ці не можаце ведаць гэта, але гэта, як правіла, лічыцца ветлівым прымаць адказы на зададзеныя пытанні (хоць вы не павінны прымаць найбольш высока прагаласаваў адказ).
дададзена аўтар BradS, крыніца
[Хіхіканне] Я не засмучаны. Ці мае ваш настаўнік не прымае іншыя адказы, дадзеныя?
дададзена аўтар BradS, крыніца
Мне вельмі шкада засмучаць і. мой настаўнік вельмі строгі чалавек і не прымае ваш адказ. не злосць у адносінах да мяне.
дададзена аўтар Moebius, крыніца