Уравнение в натуральных числах

[Ktina]

Решить в натуральных числах уравнение:

$$2n^2-n=k!$$

(невесть какой турнир матбоёв)

[ProPupil]

Фиксируем $k$, и решаем квадратное уравнение $2n^2-n-k!=0$ относительно $n$.

$$D=1+8k!$$

, откуда $n_1 = \frac{1-\sqrt{1+8k!}}{4}$, $n_2 = \frac{1+\sqrt{1+8k!}}{4}$

Первый корень неположительный, поэтому его отбрасываем. Исследуя второй случай, находим следующие условия на $k$:

1. $1+8k!$ - точный квадрат.
2. $\sqrt{1+8k!} \equiv 3 \pmod 4$

Перебираем начальные значения $k$:
$k=1$ - $3 \equiv 3 \pmod 4$ - соответствующее $n = 1$
$k = 3$ - $7 \equiv 3 \pmod 4$ - $n = 2$
$k = 5$ - $31 \equiv 3 \pmod 4$ - $n = 8$

Осталось только строго доказать, что при $k > 7$ нельзя удовлетворить двум условиям одновременно. Пока получаются пары $(k,n)=\{(1,1),(3,2),(5,8)\}$

[Ktina]

ProPupil
Большое спасибо!

[Shadow]

оособенно если иметь ввиду, что условия:

ProPupil в сообщении #1088663 писал(а):

1. $1+8k!$ - точный квадрат.
2. $\sqrt{1+8k!} \equiv 3 \pmod 4$

можно записать просто $1+8k!=(4n-1)^2$, или $k!=2n^2-n$

[Ktina]

Shadow
И Вам спасибо!

[andreiandrei]

$2n^2-n=k!$
$n(2n-1)=k!$
Множитель $2n-1$ может содержать только нечётные множители числа $k!$
Так как $2n-1>n$ для $n>1$, то $k$-нечётно.
Последовательно подставляя $k=1, k=3, k=5$, находим $n=1, n=2, n=8$.

Пусть $k\geqslant7$. Тогда

1) Если $n$ - произведение только чётных множителей $n=2\cdot4\cdot6$..., тогда второй множитель $(2n-1)$ будет $3\cdot5\cdot7$... , причём более чем в 2 раза больше $n$. И чем больше $k$, тем в большее число раз $3\cdot5\cdot7$... больше $2\cdot4\cdot6$... (так как $3>2$, $5>4$, $7>6,$...)
Но $2n-1$ больше $n$ всегда менее, чем в 2 раза. То есть при $k\geqslant7$ $n$ не может содержать только чётные множители числа $k!$

2) Пусть произведение $n$, помимо чётных, содержит также нечётный множитель $p$:
$n= 2\cdot4\cdot...\cdot(p-3)\cdot(p-1)\cdot p\cdot(p+1)\cdot(p+3)\cdot(p+5)\cdot...\cdot(k-1)$. Тогда второй множитель
$2n-1=3\cdot ... \cdot(p-4)\cdot(p-2)\cdot (p+2)\cdot(p+4)\cdot ... \cdot(k-2)\cdot k$

Сравнивая их, видим, что для того, чтоб второй множитель был хотя бы больше первого ($n$) необходимо, чтобы $k$ было больше $2p(p+1)$. То есть $3\cdot5\cdot7$... должен содержать множители кратные $p$. А это невозможно, так как если $n$ делится на $p$, то $2n-1$ на $p$ не делится.

То есть при $k\geqslant7$ решений нет.

[NSKuber]

andreiandrei в сообщении #1093330 писал(а):

Так как $2n-1>n$ для $n>1$, то $k$-нечётно.

Это почему?

andreiandrei в сообщении #1093330 писал(а):

1) Если $n$ - произведение только чётных множителей...

andreiandrei в сообщении #1093330 писал(а):

2) Пусть произведение $n$, помимо чётных, содержит также нечётный множитель...

Как-то вы странно варианты разобрали. Почему именно так должны распределяться множители между числами?
Множители факториала бывают составными, и может, например, $n$ содержит все степени двойки из всех множителей факториала, а $2n-1$ - все оставшиеся нечётные множители?

[andreiandrei]

NSKuber в сообщении #1093385 писал(а):

andreiandrei в сообщении #1093330 писал(а):

Так как $2n-1>n$ для $n>1$, то k-нечётно.

Это почему?

Смотрите, если $k$-нечётно (напр. $k=9$), то $3>2, 5>4, 7>6, 9>8 ... , k>k-1$, т.е. $3\cdot 5\cdot 7\cdot 9\cdot ... \cdot k > 2\cdot 4\cdot 6\cdot 8\cdot ... \cdot(k-1)$, а если $k$-чётно (напр. $k=8$), то $2>1, 4>3, 6>5, 8>7 ..., k>k-1$ , т. е. $1\cdot 3\cdot 5\cdot 7\cdot ... \cdot (k-1) < 2\cdot 4\cdot 6\cdot 8\cdot ... \cdot k$ .

Если же какие-то нечётные множители содержатся в $n$, а произведение остальных нечётных тем не менее больше $n$, то $k$ тем более не может быть чётным. А при $n>1$ $n$ всегда меньше $2n-1$ на $n-1$.

NSKuber в сообщении #1093385 писал(а):

andreiandrei в сообщении #1093330 писал(а):

1) Если $n$ - произведение только чётных множителей...

andreiandrei в сообщении #1093330 писал(а):

2) Пусть произведение $n$, помимо чётных, содержит также нечётный множитель...

Как-то вы странно варианты разобрали. Почему именно так должны распределяться множители между числами?
Множители факториала бывают составными, и может, например, $n$ содержит все степени двойки из всех множителей факториала, а $2n-1$ - все оставшиеся нечётные множители?

2 - чётное число. И все степени двойки (кроме нулевой)всегда будут содержатся в $n$. В $2n-1$ могут содержатся только нечётные множители, так как нечётное произведение может содержать только нечётные множители. Если же Вы какой-нибудь нечётный множитель (напр. $p=7$) включите в $n$, то, чтобы удовлетворить условию $2n-1>n$, Вам нужно будет увеличить $k$, причём так, что появятся нечётные множители кратные $p$ (как я показал в прошлом посте. К сожалению, я не знаю, как делать пробелы в формулах. А так можно было записать оба множителя друг под другом, чтоб было нагляднее.)

Я нигде не писал, что $p$ должно быть обязательно простым. Оно может быть и составным. $p$ - это просто нечётный множитель факториала (3 или 5, или 7, или 9 ...) . После переноса $p$ из $2n-1$ в $n$, Вы можете перегруппировать множители в числе $2n-1$ как хотите, от этого само число ведь не поменяется.

Перенос из нечётного произведения в $n$ множителя $p>k$ тем более нарушит условие $n<2n-1$. Чтоб это наглядно увидеть, можно сначала перенести самый большой делитель числа $p$, но который меньше или равен $k$, и заметить, что уже тогда условие $n<2n-1$ нарушится. Ведь условие из моего прошлого поста для нижней границы $k$ выполнено не будет.

[Deggial]

Посты andreiandrei отделены в Карантин.

Тема перемещена из форума «Олимпиадные задачи (М)» в форум «Карантин»
Причина переноса: формулы не оформлены $\TeX$ом

andreiandrei
Наберите все формулы и термы $\TeX$ом.
Инструкции по оформлению формул здесь или здесь (или в этом видеоролике).
См. также тему Что такое карантин, и что нужно делать, чтобы там оказаться.
После исправлений сообщите в теме Сообщение в карантине исправлено, и тогда тема будет возвращена.

Возвращено

[andreiandrei]

Научился писать пробелы в формулах.

$n \qquad =2\cdot4\cdot...\cdot(p-3)\cdot(p-1) \cdot p\cdot(p+1)\cdot(p+3)\cdot(p+5)\cdot...\cdot(k-1)$
$2n-1=\quad 3\cdot ... \cdot(p-4)\cdot(p-2)\cdot \qquad \qquad \quad \;\; (p+2)\cdot(p+4)\cdot ... \cdot(k-2)\cdot k$

Вот, если так записать второй множитель под первым, то легко увидеть необходимость условия $2p(p+1)<k$, которое, как я уже говорил, несовместимо с взаимной простотой множителей $n$ и $2n-1$

[grizzly]

andreiandrei в сообщении #1093649 писал(а):

Научился писать пробелы в формулах.

$n \qquad =2\cdot4\cdot...\cdot(p-3)\cdot(p-1) \cdot p\cdot(p+1)\cdot(p+3)\cdot(p+5)\cdot...\cdot(k-1)$
$2n-1=\quad 3\cdot ... \cdot(p-4)\cdot(p-2)\cdot \qquad \qquad \quad \;\; (p+2)\cdot(p+4)\cdot ... \cdot(k-2)\cdot k$

Этого недостаточно. Вам всё же необходимо понять, в чём был вопрос NSKuber. Вы считаете, что все перечисленные в Ваших формулах сомножители неделимы и что в обеих формулах в сумме ровно $k-1$ множитель. И, следовательно, считаете, что переносить их из верхней формулы в нижнюю и наоборот можно только целиком. Но ведь нет. Вы вполне можете из всех-всех множителей верхней формулы повыдёргивать только троечки и переместить в нижнюю формулу (от числа 6, например, множитель 2 останется вверху, а 3 пойдёт вниз, и т.д.). А с нижней формулы повыдёргивать все пятёрочки и семёрки. И после этого Ваши аргументы посыпятся.

[andreiandrei]

grizzly в сообщении #1093662 писал(а):

andreiandrei в сообщении #1093649 писал(а):

Научился писать пробелы в формулах.

$n \qquad =2\cdot4\cdot...\cdot(p-3)\cdot(p-1) \cdot p\cdot(p+1)\cdot(p+3)\cdot(p+5)\cdot...\cdot(k-1)$
$2n-1=\quad 3\cdot ... \cdot(p-4)\cdot(p-2)\cdot \qquad \qquad \quad \;\; (p+2)\cdot(p+4)\cdot ... \cdot(k-2)\cdot k$

Этого недостаточно. Вам всё же необходимо понять, в чём был вопрос NSKuber. Вы считаете, что все перечисленные в Ваших формулах сомножители неделимы и что в обеих формулах в сумме ровно $k-1$ множитель. И, следовательно, считаете, что переносить их из верхней формулы в нижнюю и наоборот можно только целиком. Но ведь нет. Вы вполне можете из всех-всех множителей верхней формулы повыдёргивать только троечки и переместить в нижнюю формулу (от числа 6, например, множитель 2 останется вверху, а 3 пойдёт вниз, и т.д.). А с нижней формулы повыдёргивать все пятёрочки и семёрки. И после этого Ваши аргументы посыпятся.

Да, действительно. Спасибо. Забыл про то, что верхнее произведение изначально содержит в том числе и нечётные множители. (Я, конечно, не считал множители факториала неделимыми, но переносил только из нижнего в верхний. Там было неважно, соберем ли мы $p$ по кусочкам или возьмём целиком, ведь нас удовлетворяло лишь $p<k$, а такое $p$ всегда было и целиком.)

Я понял ошибку. Более того, $n$ и $2n-1$ именно должны раскладываться на различные простые множители, чтоб быть взаимно простыми. Завтра ещё подумаю, всё-таки почему-то хочется строго решить эту задачу.

[andreiandrei]

$n = \frac{1+\sqrt{1+8k!}}{4}$

При $k\geqslant10$ $k!$ заканчивается на два нуля. Поэтому $1+8k!$ заканчивается на 01.
Из того, что последняя цифра этого точного квадрата равна 1, следует, что $\sqrt{1+8k!}$ заканчивается на 9 или на 1. Тогда весь числитель заканчивается на 0 или 2.
При этом он должен делиться на 4. То есть, эти числа могут заканчиваться на 12, 32, 52, 72, 92, 20, 40, 60, 80, 00.
$n$ - чётно, так как $k! =n(2n-1)$. Следовательно, при делении числителя на 4 должно получаться чётное число.
Тогда числитель может заканчиваться только на 32, 72, 40, 80. А $\sqrt{1+8k!}$ может заканчиваться только на 31, 71, 39, 79.
Но квадрат чисел, заканчивающихся на 31, 71, 39 или 79, не будет заканчиваться на 01. (Это сразу видно, если начать перемножать такие числа сами на себя столбиком.)
Следовательно, при $k\geqslant10$ не найдутся $n$, удовлетворяющие уравнению.
При $k<6$ ProPupil уже написал ответы. Можно проверить, что если $k$ равно 6, 7, 8 или 9, то решений нет.

Теперь вроде верно?

[Shadow]

andreiandrei в сообщении #1098474 писал(а):

То есть, эти числа могут заканчиваться 12, 32, 52, 72, 92, 20, 40, 60, 80, 00.

andreiandrei в сообщении #1098474 писал(а):

Следовательно, при делении числителя на 4 должно получаться чётное число.
Тогда числитель может заканчиваться только на 32, 72, 40, 80

Почему вы думаете, что число, заканчивающие на $52,92,20,60,00$ не может делится на $8$?
И вообще, по любому модулю противоречий не найдете.
И вообще...

[andreiandrei]

Shadow в сообщении #1098484 писал(а):

Почему вы думаете, что число, заканчивающие на $52,92,20,60,00$ не может делится на $8$?

Да, что-то я совсем невнимательный какой-то. Спасибо.

А если вот так:

При $k\geqslant5$ $2n^2 -n$ заканчивается на 0. Тогда числа $2n^2$ и $n$ должны заканчиваться на одинаковую цифру. Если перебрать цифры, то видно, что это возможно только если $n$ заканчивается на 8. При $k\geqslant5$ в разложении числа $n$ не меньше трёх двоек. А если число, делящееся на восемь и заканчивающееся на восемь, разделить на восемь, то получится число, заканчивающееся на 1, то есть оно будет нечётным. А это возможно только если в разложении на простые множители числа $n$ (а значит и $k!$) только три двойки.
Выходит, при $k\geqslant5$ подходят только $k=5; n=8$