Целочисленное уравнение

[Pripyat]

Добрый день, на этот раз решаю задачу:

Цитата:

Найти всевозможные пары чисел x и y таких, что среднее арифметическое чисел $\frac{1}{x(x+y)}$, $\frac{1}{(x+y)(x+2y)}$, $\frac{1}{(x+2y)(x+3y)}$, ... , $\frac{1}{(x+9y)(x+10y)}$ равно $\frac{1}{3^{x+11y+3}-y^2-16}$

Для начала я нашел среднее арифметическое этих 10 чисел.
Т.к. $\frac{1}{x(x+y)} = \frac{1}{xy} - \frac{1}{(x+y)y}$; $\frac{1}{(x+y)(x+2y)} = \frac{1}{(x+y)y} - \frac{1}{(x+2y)y}$; ... ; $\frac{1}{(x+9y)(x+10y)} = \frac{1}{(x+9y)y} - \frac{1}{(x+10y)y}$, то
$\sum = \frac{1}{xy} - \frac{1}{(x+y)y} + \frac{1}{(x+y)y} - \frac{1}{(x+2y)y} + ... + \frac{1}{(x+9y)y} - \frac{1}{(x+10y)y} = \frac{1}{xy} - \frac{1}{(x+10y)y} = \frac{10}{x(x+10y)}$
Тогда $\overline{a} = \frac{\sum}{10} = \frac{1}{x(x+10y)}$

Теперь решаем целочисленное уравнение: $\overline{a} = \frac{1}{x(x+10y)} = \frac{1}{3^{x+11y+3}-y^2-16}$
$x(x+10y) = 3^{x+11y+3}-y^2-16$

Решил проанализировать четность:
Выражение $x(x+10y)$ имеет такую же четность как и $x$, т.к. $10y$ - чётное, $x+10y$ совпадает с четностью $x$. Если $x$ - чётно, то и произведение $x(x+10y)$ - чётно, аналогично, если $x$ - нечётно, то и $x(x+10y)$ - нечётно.

Выражение $3^{x+11y+3}-y^2-16$ по чётности различается с $y$, т.к. $3^{x+11y+3} - 16$ - нечётно. И если $y$ - чётно, то всё выражение нечётно, иначе, если $y$ - нечётно, то всё выражение чётно.

Тогда мы получаем, что числа $x$ и $y$ должны быть разной чётности. Тогда степень тройки $x+11y + 3$ всегда чётная. Однако этим воспользоваться далее не получается ... Подскажите пожалуйста направление ... Спасибо

[Markiyan Hirnyk]

Диофантово уравнение содержит член с показательной функцией $3^{x+11y+3}$, т.е. оно не полиномиальное.
Рассматриваемое уравнение можно переформулировать как задачу целочисленного программирования (методы решения таких задач известны). Таким образом с применением Мэйпла находятся решения $\{x = 8, y = -1\},\,\{x = 19, y = -2\}$. Можно также попробовать рассмотреть это уравнение по модулю 3 для сужения поиска решений.

[provincialka]

Markiyan Hirnyk в сообщении #1278623 писал(а):

Можно также попробовать рассмотреть это уравнение по модулю 3 для сужения поиска решений.

Тут важно знать, целочисленные решения ищутся или только натуральные? В случае целочисленных степень тройки вполне может оказаться единицей.

-- 25.12.2017, 17:57 --

Да! Именно делимость на три. И натуральность требовать как раз не надо!
(Без целочисленного программирования можно вполне обойтись: у меня под рукой был только мел и доска )

[Pripyat]

provincialka, требуется найти целые числа.
Спасибо за подсказку, буду пытаться рассматривать делимость на 3 и остатки от деления на 3.

[provincialka]

Просто перенесите все, кроме степени тройки, на одну сторону.

[Pripyat]

provincialka, сделал втупую.
$3^{x+11y+3} = x^2+10xy+y^2+16 = 9xy + 15 + (x^2 + xy + y^2 + 1)$
Чтобы правая часть делилась на 3 необходимо, чтобы делилось на 3 выражение: $x^2 + xy + y^2 + 1$
Пусть $x = 3m+r_1$, $y= 3n+r_2$, тогда
$x^2 + xy + y^2 + 1 = (3m+r_1)^2 + (3m+r_1)(3n+r_2) + (3n+r_2)^2 + 1 = (9m^2 + 6mr_1+r_1^2) + (9mn+3mr_2+3nr_1+r_1r_2)+(9n^2+6nr_2+r_2^2) + 1$.

Чтобы делилось на три данное выражение необходимо, чтобы делилось на три выражение: $r_1^2 + r_1r_2 + r_2^2 + 1$ для $r_1 = 0, 1, 2$ или $r_2 = 0, 1, 2$
Можно убедиться, что при любых допустимых $r_1$, $r_2$ данное выражение на три не делится!

Тогда первоначальное равенство возможно только в случае, если:

$$\left\{ \begin{array}{rcl} x+11y+3=0 \\ x^2+10xy+y^2+16 = 1 \\ \end{array} \right.$$

$$\left\{ \begin{array}{rcl} x= -11y-3 \\ (x+5y)^2 = 24y^2-15 \\ \end{array} \right.$$

$(-6y-3)^2 = 24y^2-15$
$(6y+3)^2 = 24y^2-15$
$36y^2+36y+9 = 24y^2-15$
$12y^2+12y+3 = 8y^2-5$
$4y^2+12y+8 = 0$
$y^2+3y+2 = 0$
$y_1 = -1$, $x_1 = 11 - 3 = 8$
$y_2 = -2$, $x_2 = 22 - 3 = 19$

Ответ: $(8; -1)$ ; $(19; -2)$

[provincialka]

Нормально... только можно было покороче:
$3^{x+11y+3} = x^2+10xy+y^2+16 \equiv x^2-2xy+y^2+1 (\mod 3) = (x-y)^2+1$
Ну, а квадрат числа не может иметь остаток 2 при делении на 3, так что результат на 3 не делится.

[Pripyat]

provincialka
Спасибо, я чувствовал, что есть более рациональное решение.

А не подскажите напоследок литературу по олимпиадным целочисленным задачам, с использованием сравнения по модулю (и вообще модульной арифметики)?