2014 dxdy logo

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

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


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


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



Начать новую тему Ответить на тему
 
 Семейство диофантовых уравнений (обобщение).
Сообщение28.06.2019, 11:19 


03/03/12
1380
Задача.
Найти алгоритм решения в натуральных числах семейства диофантовых уравнений:
$$xy^2-Hy-mx^3=0$$
при $x>1$, $m\ge1$, $H\ge1$.
(Это обобщение задачи из "Олимпиадного раздела". Там она решена пока только для $m=1$.)
Прошу проверить мою попытку решения этой задачи. (Получается очень просто. Может, ошиблась.)
Решение.
$y^2>mx^2$ $\to$ $y>\sqrt m\cdot x$

$y(xy-H)-mx^3=0$

$\sqrt m\cdot x(xy-H)-mx^3<0$

$y<\frac{H+\sqrt m\cdot x^2}{x}<H+\sqrt m$

$H+\sqrt m\cdot x^2<Hx+\sqrt m\cdot x$

$\sqrt m\cdot x(x-1)<H(x-1)$

1). Т.е. получили, что при $\sqrt m\cdot x<H$ $\to$ $y<H+\sqrt m$.

2). Остаётся рассмотреть $x>\frac{H}{\sqrt m}$.
Покажем, что тогда $y\le\sqrt m(x+1)$.

$\sqrt m\cdot Hy=\sqrt m\cdot x(y^2-mx^2)$

Т.к. $\sqrt m\cdot x>H$, то

$\sqrt m\cdot y>y^2-mx^2$ $\to$ $x^2>\frac{y^2-\sqrt m\cdot y}{m}$

$x\cdot x>\frac{y}{\sqrt m}\cdot\frac{y-\sqrt m}{\sqrt m}$

Т.к. $x<\frac{y}{\sqrt m}$, то $x>\frac{y-\sqrt m}{\sqrt m}$

$\frac{y-\sqrt m}{\sqrt m}<x<\frac{y}{\sqrt m}$

Замечание.
При $m=1$ получим $(y-1)<x<y$. Т.е. в итоге $y<H+1$. Оценка немного хуже, чем в источнике, но для алгоритма перебора это не столь важно. Главное, что метод обобщается для любого натурального $(m)$.

Получили, что $y<\sqrt m\cdot x+\sqrt m$ или $y<\sqrt m(x+1)$.

Далее, из делимости следует, что должно быть $Hy=kx$. Тогда получим, что

$H\cdot\sqrt m(x+1)>kx$

$k<\frac{H\cdot\sqrt m(x+1)}{x}$

Получили, что

$k<mH$ при $x\ge3$

$x=\frac{Hy}{k}$ подставляем в исходное уравнение. Получим $y^2=\frac{k^3}{k^2-mH^2}$ при $H\le k\le mH$. Здесь имеем простой ограниченный перебор при конкретных значениях $(m)$ и $(H)$. Плюс остаётся рассмотреть отдельно случай $x\le2$ и учесть перебор при $y\le H+\sqrt m$.
Получили, что всё решается ограниченным перебором?

 Профиль  
                  
 
 Re: Семейство диофантовых уравнений (обобщение).
Сообщение28.06.2019, 17:18 
Заслуженный участник


20/12/10
8858
TR63 в сообщении #1402010 писал(а):
Получается очень просто.
Это если не задумываться о сложности (количестве "элементарных" действий) предлагаемого алгоритма решения. Под "элементарным" действием в данном случае следует понимать решение обычного (с одним неизвестным) уравнения в целых числах. Например, предлагаемый Вами перебор по $y$ подразумевает решение некоторого количества кубических уравнений относительно $x$. Это количество у Вас оценено как $H+\sqrt{m}$ и, таким образом, зависит как от $H$, так и от $m$. Между тем, можно предложить такой алгоритм решения семейства диофантовых уравнений $x(y^2-mx^2)-Hy=0$ (где $m$ и $H$ --- натуральные числа), при котором потребуется решить всего лишь $O(H^{2/3})$ обычных уравнений, причем только квадратных. Более того, константа в $O$-большом не зависит от $m$, т.е. количество решаемых уравнений будет зависеть только от $H$.

 Профиль  
                  
 
 Re: Семейство диофантовых уравнений (обобщение).
Сообщение28.06.2019, 18:22 


03/03/12
1380
nnosipov в сообщении #1402057 писал(а):
Например, предлагаемый Вами перебор по $y$ подразумевает решение некоторого количества кубических уравнений относительно $x$.

Нет. Решать кубическое уравнение не надо. В равенство
TR63 в сообщении #1402010 писал(а):
$y^2=\frac{k^3}{k^2-mH^2}$ при $H\le k\le mH$
, которое должно выполняться при конкретных наперёд заданных $(H;m)$, подставляем перебором значения (k) из указанного диапазона, полученного логическим путём (количество значений ограниченно; оно не может быть произвольным, это доказано, если что-то непонятно изложено, спрашивайте, что именно; если бы это не было доказано, тогда надо решать кубические уравнения; здесь у нас с Вами расхождение, плюс Ваше количество кубических уравнений $y<H+\sqrt m$, у меня это относится к первому случаю, не понимаю, какое отношение первый случай имеет ко второму ; тогда, пожалуйста, укажите ошибку; я её пока не вижу; может, т.к. $(k)$ зависит от $(x)$, то кубические уравнения решать надо, но это, если переменная принимает неограниченное количество значений или я ошибаюсь? ). Если равенство выполняется, значит есть решение и его можно вычислить. Равенство может не выполняться вообще; далее делаем перебор ($(H;m)$ у нас заданны) при $y\le H+\sqrt m$(это уже относится к первому случаю).
И, хотя бы для $m=1$ доказательство верно?

 Профиль  
                  
 
 Re: Семейство диофантовых уравнений (обобщение).
Сообщение28.06.2019, 19:08 
Заслуженный участник


20/12/10
8858
TR63
У Вас, как обычно, довольно мутный текст, который можно понять по-разному. Сформулируйте более конкретно, по пунктам, Ваш алгоритм решения, чтобы можно было понять, какие операции в нем производятся.

 Профиль  
                  
 
 Re: Семейство диофантовых уравнений (обобщение).
Сообщение28.06.2019, 20:43 


03/03/12
1380
Хорошо, распишу более подробно.
Задача.
Найти алгоритм решения в натуральных числах семейства диофантовых уравнений:
$$xy^2-Hy-mx^3=0$$
при $x>1$, $m\ge1$, $H\ge1$.
Будет рассмотрено два случая:
1). $\sqrt m\cdot x<H$
Будет показано, что для существования решений необходимо выполнение условия:
$y\le H+\sqrt m$.
2). $x\ge\frac{H}{\sqrt m}$.
Будет показано, что для существования решения в этом случае необходимо выполнение равенства
$y^2=\frac{k^3}{k^2-mH^2}$ при $H\le k\le mH$.
(Здесь просто подставляем ограниченным перебором $(k)$ в равенство и смотрим, выполняется оно или нет; если выполняется, то обратной процедурой находим $(x;y)$ и делаем дополнительно проверку.)
Вывод: алгоритм решения (перебора) состоит из двух частей. Имеется верхняя граница для перебора $y\le H+\sqrt m$ (здесь $\sqrt m\cdot x<H$, но фактически перебирается большее количество $(x)$, $x\le y$;думаю, это не криминал)
и перебор в выполнении равенства $y^2=\frac{k^3}{k^2-mH^2}$ при $H\le k\le mH$. (Здесь $x\ge\frac{H}{\sqrt m}$.)

Если замечаний по схеме не будет, то распишу промежуточные выкладки подробнее (при необходимости).

 Профиль  
                  
 
 Re: Семейство диофантовых уравнений (обобщение).
Сообщение29.06.2019, 05:58 
Заслуженный участник


20/12/10
8858
TR63
Как я понял, в п. 1) предполагается перебор пар $(x,y)$ при условиях $x<H/\sqrt{m}$, $y<H+\sqrt{m}$ и проверка выполнения равенства $x(y^2-mx^2)-Hy=0$. Так? А что делается в п. 2)? Сформулируйте точно, я так и не понял (что перебираем, что при этом проверяем/делаем).

 Профиль  
                  
 
 Re: Семейство диофантовых уравнений (обобщение).
Сообщение29.06.2019, 09:25 


03/03/12
1380
nnosipov в сообщении #1402118 писал(а):
в п. 1) предполагается перебор пар $(x,y)$ при условиях $x<H/\sqrt{m}$, $y<H+\sqrt{m}$ и проверка выполнения равенства $x(y^2-mx^2)-Hy=0$. Так?

Да, так.

TR63 в сообщении #1402010 писал(а):
2). Остаётся рассмотреть $x>\frac{H}{\sqrt m}$.
Покажем, что тогда $y\le\sqrt m(x+1)$.

Здесь, в случае знака равенства в неравенстве, будем иметь уравнение от одной переменной (простой случай; я его не рассматриваю).
TR63 в сообщении #1402010 писал(а):
При $m=1$ получим $(y-1)<x<y$. Т.е. в итоге $y<H+1$

TR63 в сообщении #1402060 писал(а):
для $m=1$ доказательство верно?


Далее, по второму пункту будем считать, что доказана необходимость неравенства (знак равенства в нём пока не рассматриваем, т.к. это просто)
$y<\sqrt m(x+1)$ при $x\ge\frac{H}{\sqrt m}$.
Для существования решения необходимо выполнение условия $Hy=kx$. Тогда, с учётом необходимости неравенства, доказанного выше, необходимо выполнение неравенства
TR63 в сообщении #1402010 писал(а):


$H\cdot\sqrt m(x+1)>kx$

$k<\frac{H\cdot\sqrt m(x+1)}{x}$


Здесь решили неравенство относительно переменной $(k)$. Из последнего неравенства следует, что
TR63 в сообщении #1402010 писал(а):

$k<mH$ при $x\ge3$

TR63 в сообщении #1402010 писал(а):

$x=\frac{Hy}{k}$ подставляем в исходное уравнение. Получим $y^2=\frac{k^3}{k^2-mH^2}$


Знаменатель должен быть больше нуля. Т.е. $k\cdot k>m\cdot H\cdot H$. Т.к. $k<mH$ то должно быть $k>H$, чтобы выполнялось условие положительности знаменателя. Получаем, что натуральная переменная $(k)$ может принимать только ограниченное количество значений, заключённых в диапазоне $H\le k\le mH$. Т.е. имеем не уравнение, а серию равенств, которые должны выполняться (правая часть должна быть полным квадратом). Вот и проверяем их. Здесь, хотя переменная $(x)$ неограниченная, но $(k)$ ограниченная. Поэтому перебор ограничен. Если равенство выполняется при некотором значении $(k)$, то получаем после подстановки $(x)$ в исходное уравнение уравнение от одной переменной $(y)$ (это просто; не рассматриваю).

 Профиль  
                  
 
 Re: Семейство диофантовых уравнений (обобщение).
Сообщение29.06.2019, 09:51 
Заслуженный участник
Аватара пользователя


21/11/12
1870
Санкт-Петербург
nnosipov в сообщении #1402118 писал(а):
... что перебираем, что при этом проверяем/делаем

А это как карта ляжет. Что-то ведь нам известно! Что не известно, то и подбираем )

TR63 давайте для начала решим уравнение относительно $y=\dfrac{H\pm \sqrt{H^2+4mx^4}}{2x}.$ Перепишем это так $(2xy-H)^2=H^2+4mx^4.$ Обозначив выражение в скобочках буквой $D$, получаем $$D^2-4mx^4=H^2$$
Вот уже видно, что для фиксированной пары произвольных аргументов $(m,H)$ такое уравнение не факт что разрешимо, и условия разрешимости я бы не взялся сформулировать. А тем более для тройки аргументов, тут уж подбирай, не подбирай... Если же аргументами назначить пару $(m,x)$, то конечно найдутся $D,H$ такие, что $4mx^4=D^2-H^2$, и целое $y=\dfrac{\pm D+H}{2x}$. И нечего тут подбирать. Да, кстати, а почему семейство?

PS при составном $x$ целое $y$ найдется не для любых пар $(D,H)$, но для некоторых найдется.

 Профиль  
                  
 
 Re: Семейство диофантовых уравнений (обобщение).
Сообщение29.06.2019, 12:45 


03/03/12
1380
Andrey A, я не решала задачу об условиях разрешимости Вашего уравнения, хотя исходное к нему сводится. У меня $(m;H)$ любые конечные фиксированные. Здесь у нас, по-моему, разное понимание ситуации. Смотрите, например, есть задача: при любом конечном фиксированном $(n)$ выяснить, существует ли решение у уравнения $x^n+y^n=z^n$. И есть задача: при любом ли фиксированном $(n)$ (что эквивалентно "любое натуральное") существует решение у уравнения $x^n+y^n=z^n$. Задачи похожие, но по сложности решения разные.
Andrey A, посмотрите, пожалуйста, мой алгоритм (там выкладки все элементарные). Если найдёте ошибку, укажите, где именно она находится. Я её пока не вижу.

 Профиль  
                  
 
 Re: Семейство диофантовых уравнений (обобщение).
Сообщение29.06.2019, 12:54 
Заслуженный участник
Аватара пользователя


21/11/12
1870
Санкт-Петербург
TR63 в сообщении #1402159 писал(а):
... об условиях разрешимости Вашего уравнения

Почему моего? Уравнение Ваше
TR63 в сообщении #1402085 писал(а):
$xy^2-Hy-mx^3=0$
А где тут аргументы Вы не сообщаете, вот и приходится гадать.

 Профиль  
                  
 
 Re: Семейство диофантовых уравнений (обобщение).
Сообщение29.06.2019, 16:44 


03/03/12
1380
Andrey A в сообщении #1402160 писал(а):
А где тут аргументы Вы не сообщаете

Да, Вы правы. Хорошо, что спросили понятным мне языком. (Вот, и надо в лоб спрашивать, что конкретно не понятно.) Добавляю к условию информацию:$(m;H)$ параметры, $(x;y)$ переменные. Поэтому, наверное, в источнике указано в названии "семейство".

-- 29.06.2019, 17:49 --

Andrey A в сообщении #1402160 писал(а):
Почему моего?

Я не эб этом уравнении говорила, а об
Andrey A в сообщении #1402143 писал(а):
получаем $$D^2-4mx^4=H^2$$
Вот уже видно, что для фиксированной пары произвольных аргументов $(m,H)$ такое уравнение не факт что разрешимо, и условия разрешимости я бы не взялся сформулировать.

 Профиль  
                  
 
 Re: Семейство диофантовых уравнений (обобщение).
Сообщение29.06.2019, 17:46 
Заслуженный участник


20/12/10
8858
TR63 в сообщении #1402139 писал(а):
Получаем, что натуральная переменная $(k)$ может принимать только ограниченное количество значений, заключённых в диапазоне $H\le k\le mH$. Т.е. имеем не уравнение, а серию равенств, которые должны выполняться (правая часть должна быть полным квадратом). Вот и проверяем их. Здесь, хотя переменная $(x)$ неограниченная, но $(k)$ ограниченная. Поэтому перебор ограничен. Если равенство выполняется при некотором значении $(k)$, то получаем после подстановки $(x)$ в исходное уравнение уравнение от одной переменной $(y)$ (это просто; не рассматриваю).
В целом верно, но изложено так, что лучше не читать.

Короче, вердикт: алгоритм можно довести до ума, но при этом он окажется довольно затратный. В первом пункте объем перебора определяется произведением $(H+\sqrt{m})H/\sqrt{m}>H$, а во втором нужно решить порядка $mH$ квадратных уравнений относительно $y$ (это наиболее трудоемкая часть).

 Профиль  
                  
 
 Re: Семейство диофантовых уравнений (обобщение).
Сообщение30.06.2019, 08:09 


03/03/12
1380
nnosipov в сообщении #1402217 писал(а):
алгоритм ... окажется довольно затратный. ... а во втором нужно решить порядка $mH$ квадратных уравнений относительно $y$ (это наиболее трудоемкая часть).

Во втором случае можно сделать гипотетическое обобщение и исследовать его. Но это уже другая история.

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

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



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

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


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

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