2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


Посмотреть правила форума



Начать новую тему Ответить на тему
 
 Тождество n div k^2 = (n div k) div k
Сообщение18.10.2021, 00:33 
Аватара пользователя


18/10/21
4
Здравствуйте! При разработке одного алгоритма я использовал нижеприведённое тождество как заведомо истинное. Сейчас понимаю, что нужно его доказать, но у меня недостаточно навыков для этого.
Тождество. Для любых целых положительных чисел $n$ и $k$ верно:
$n \operatorname{div} k^2 = (n \operatorname{div} k) \operatorname{div} k$,
где $\operatorname{div}$ — оператор деления нацело (как в Паскале).
Прошу помочь с доказательством.

 Профиль  
                  
 
 Re: Тождество n div k^2 = (n div k) div k
Сообщение18.10.2021, 00:37 
Заслуженный участник


09/05/12
25179
Представьте $n$ как $n=a \cdot k^2 + b \cdot k + c$ (какими могут быть коэффициенты?) и проверьте, чему равны обе части равенства.

 Профиль  
                  
 
 Re: Тождество n div k^2 = (n div k) div k
Сообщение18.10.2021, 01:58 
Аватара пользователя


18/10/21
4
Спасибо! Вот мои выкладки.
Представим $n$ в виде $ak^2 + bk + c$, где $a, b, c$ — целые неотрицательные числа.
Найдём максимально возможное $a$, при котором возможно такое представление. Так как $n \geqslant ak^2$, то
$a_{\max} = n \operatorname{div} k^2$.
При $a = a_{\max}$ найдём максимально возможное $b$, при котором возможно такое представление. Так как $n \geqslant ak^2 + bk$, то
$bk \leqslant n - ak^2 = n \operatorname{mod} k^2$,
$b_{\max} = (n \operatorname{mod} k^2) \operatorname{div} k$.
При $a = a_{\max}, b = b_{\max}$
$c = n \operatorname{mod} k$,
так как $n = (ak + b)k + c$, а если $c \geqslant k$, то из $с$ можно вычесть $k$ и добавить $1$ к $b$, что противоречит условию $b = b_{\max}$.

Итого,
$$n = (n \operatorname{div} k^2)k^2 + ((n \operatorname{mod} k^2) \operatorname{div} k)k + n \operatorname{mod} k.$$
Поделив на $k$ нацело, получим:
$$n \operatorname{div} k = (n \operatorname{div} k^2)k + ((n \operatorname{mod} k^2) \operatorname{div} k,$$
так как $n \operatorname{mod} k$ не делится на $k$.
Поделив на $k$ нацело ещё раз, получим:
$$\fbox{(n \operatorname{div} k) \operatorname{div} k = n \operatorname{div} k^2},$$
так как
$n \operatorname{mod} k^2 < k^2$,
$((n \operatorname{mod} k^2) \operatorname{div} k < k$,
а значит, $((n \operatorname{mod} k^2) \operatorname{div} k$ не делится на $k$.
Мы получили искомое тождество.

 Профиль  
                  
 
 Re: Тождество n div k^2 = (n div k) div k
Сообщение18.10.2021, 02:16 
Заслуженный участник


09/05/12
25179
IgorSukharev в сообщении #1535289 писал(а):
Найдём максимально возможное $a$, при котором возможно такое представление.
А зачем, собственно? Я уж не говорю о том, что найти его не получится...

В основном-то вы сделали все нормально, но только представить это можно намного проще. Эти коэффициенты - попросту разряды в представлении $n$ в системе счисления с основанием $k$ ($b$ и $c$ - без каких-либо оговорок, $a$ - с оговорками, поскольку в него простоты ради "засунуты" заодно и все более старшие разряды). Отсюда сразу же следует существование и единственность такого представления, а заодно то, что $0 \leqslant b < k$ и $0 \leqslant c < k$.

 Профиль  
                  
 
 Re: Тождество n div k^2 = (n div k) div k
Сообщение18.10.2021, 05:19 
Аватара пользователя


18/10/21
4
Если представить $a$ в $k$-ичной позиционной системе счисления, то получится число $\overline{\dots a_2 a_1 a_0}_k$. Как известно,
$\overline{\dots a_{n+1} a_n \dots a_1 a_0}_k \operatorname{div} k^n = \overline{\dots a_{n+1} a_n}_k.$
В свете этого тождество становится очевидным.

 Профиль  
                  
 
 Re: Тождество n div k^2 = (n div k) div k
Сообщение18.10.2021, 12:02 
Заслуженный участник


09/05/12
25179
IgorSukharev в сообщении #1535293 писал(а):
В свете этого тождество становится очевидным.
Именно.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 6 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: Mikhail_K, YandexBot [bot]


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group