2014 dxdy logo

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

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


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


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



Начать новую тему Ответить на тему
 
 Минимум целочисленной функции двух переменных
Сообщение09.01.2018, 02:00 
Аватара пользователя


05/11/11
91
Пусть задано число $a \in \mathbb{N}$.

При каком $b \in \mathbb{N} \cap [1, a]$ функция $\displaystyle h(a, b) = \frac{a^2+b^2}{\text{НОД}(a, b)}$ достигает минимального значения?

Моё предположение: $b = a$. Тогда $h_{min} = 2a$. Но оно основано просто на вычислениях для разных чисел. Доказать его не могу. В какую сторону думать?

 Профиль  
                  
 
 Re: Минимум целочисленной функции двух переменных
Сообщение09.01.2018, 02:32 
Заслуженный участник
Аватара пользователя


22/06/12
2129
/dev/zero
qx87
Указание: рассмотреть функцию $a^2 + b^2 - 2 a \text{НОД} (a, b)$.

 Профиль  
                  
 
 Re: Минимум целочисленной функции двух переменных
Сообщение09.01.2018, 05:37 
Заслуженный участник


18/01/15
3075
StaticZero
Не в обиду Вам будь сказано, Ваше "указание" совершенно неправильное.

qx87
Не знаю даже что написать, больно уж задача простая. Такой намек. Предположим, мы знаем, что $a=1000$, плюс-минус десять процентов. И еще знаем, что ${\rm GCD}(a,b)=700$, тоже плюс-минус десять процентов. Про само же $b$ ничего не знаем. Вопрос (риторический): может ли такое быть?
(GCD --- это Greatest Common Divisor, НОД; почему-то русские буквы не пропечатались).

 Профиль  
                  
 
 Re: Минимум целочисленной функции двух переменных
Сообщение09.01.2018, 08:06 
Заслуженный участник


18/01/15
3075
vpb в сообщении #1282562 писал(а):
StaticZero
Не в обиду Вам будь сказано, Ваше "указание" совершенно неправильное.

Я был неправ. StaticZero прислал мне по этому поводу ЛС. Однако, тот способ решения, который использовал StaticZero, не очень естественный и до него догадаться трудно, имхо.

 Профиль  
                  
 
 Re: Минимум целочисленной функции двух переменных
Сообщение09.01.2018, 09:18 
Аватара пользователя


05/11/11
91
Прежде всего, поскольку $a$ фиксировано, всё-таки нужно считать $h$ функцией одной переменной.

StaticZero
Так, ну.
Пусть $y(b) = a^2 + b^2 - 2 a \text{НОД} (a, b)$.
Поскольку $\text{НОД}(a,b) \leqslant b, \; y(b) \geqslant (a-b)^2 \geqslant 0$. Получаем, что $y(b)$ достигает минимума при $b=a$, как я и предполагал.

Нашу функцию можно получить из этой с помощью сжатия и сдвига на фиксированное $2a$:
$h(b) = \frac{y(b)}{\text{НОД}(a,b)} + 2a$, поэтому обе функции достигают минимумов одновременно. ЧТД.

Всё верно, нет ошибок?

vpb
Нет, конечно. НОД будет либо 1000, либо 500 тогда уж. Плюс-минус 10%. Но что это даёт доказательству, не понимаю.

 Профиль  
                  
 
 Re: Минимум целочисленной функции двух переменных
Сообщение09.01.2018, 10:40 


08/08/16
50
qx87

$\text{НОД}=\frac{a}{n}$, где $n$-натуральное. Если подставить и поделить, сразу видно минимум достигается при $n=1$ :D

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

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



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

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


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

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