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
24060
Кронштадт
Представьте $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
24060
Кронштадт
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
24060
Кронштадт
IgorSukharev в сообщении #1535293 писал(а):
В свете этого тождество становится очевидным.
Именно.

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

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



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

Сейчас этот форум просматривают: нет зарегистрированных пользователей


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

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