Задача для профессиональных математиков

Логические задачи

Модераторы: Азарапетыч, Администрация

Ответить
Аватара пользователя
Шшок
Акула пера
Акула пера
Сообщения: 9061
Зарегистрирован: 28 ноя 2003, 14:05
Пол: Мужской
Откуда: С большой дороги.

Задача для профессиональных математиков

Сообщение Шшок »

Задача из интернета. Позиционировалась как очень сложная, я за нее даже не взялся. Но условие очень простое и интригующее.

Дано: a, b - целые положительные числа, такие что (a^2+b^2) нацело делится на (ab+1).
Доказать, что частное от такого деления является квадратом целого числа.

Если кому-то не лень с этим возиться - повозитесь пожалуйста.
В борьбе бобра с козлом побеждает бобро. Или козло.

Юляша
Популярный автор
Популярный автор
Сообщения: 3352
Зарегистрирован: 15 янв 2009, 12:32
Пол: Женский

Re: Задача для профессиональных математиков

Сообщение Юляша »

Есть подозрение, что a=b=1 - единственная подходящая пара...

Неверно. Компьютер показал, что для a,b<1000 существует 13 вариантов. Во-первых, существует семейство вида (x, x^3). Первая пара, не принадлежащая этому семейству - (8,30). 964/241=4...

Далее (интересно, что число, появляющееся как b, далее дает решение и как a):
8 30
27 240
30 112
112 418
Нас двое - я и папа
И погромче нас были витии Да не сделали пользы пером. Дураков не убавим в России, А на умных тоску наведем.

Юляша
Популярный автор
Популярный автор
Сообщения: 3352
Зарегистрирован: 15 янв 2009, 12:32
Пол: Женский

Re: Задача для профессиональных математиков

Сообщение Юляша »

Несколько дополнительных выводов.

1. Базовое семейство пар, удовлетворяющих условию, - это пары вида (0,a). Для них получаем a^2=n*1, то есть n=a^2.

2. Пара вида (a, a) удовлетворяет условию только для a=1, при этом n=1

3. Пусть пара вида (a, b), a<b удовлетворяет условию при некотором значении n. Тогда пара (b,c), где с=nb-a, также удовлетворяет условию причем n остается тем же самым. (Все варианты, показанные компьютером, получаются этим способом.)

4. Но это означает, что пара (с, a), где с=na-b также будет удовлетворять условию.

5. Если доказать, что в пункте 4 всегда 0<=c<=a, то исходное утверждение будет доказано, так как "обратной индукцией" мы в итоге придем к базовому семейству.
Нас двое - я и папа
И погромче нас были витии Да не сделали пользы пером. Дураков не убавим в России, А на умных тоску наведем.

Аватара пользователя
Шшок
Акула пера
Акула пера
Сообщения: 9061
Зарегистрирован: 28 ноя 2003, 14:05
Пол: Мужской
Откуда: С большой дороги.

Re: Задача для профессиональных математиков

Сообщение Шшок »

Юляша писал(а):
12 май 2022, 11:53
Несколько дополнительных выводов.

1. Базовое семейство пар, удовлетворяющих условию, - это пары вида (0,a). Для них получаем a^2=n*1, то есть n=a^2.

2. Пара вида (a, a) удовлетворяет условию только для a=1, при этом n=1

3. Пусть пара вида (a, b), a<b удовлетворяет условию при некотором значении n. Тогда пара (b,c), где с=nb-a, также удовлетворяет условию причем n остается тем же самым. (Все варианты, показанные компьютером, получаются этим способом.)

4. Но это означает, что пара (с, a), где с=na-b также будет удовлетворять условию.

5. Если доказать, что в пункте 4 всегда 0<=c<=a, то исходное утверждение будет доказано, так как "обратной индукцией" мы в итоге придем к базовому семейству.
Красиво. Но еще надо доказать, что не существует пар, не принадлежащих к таким семействам... А вдруг при больших значениях a, b такие пары существуют?
В борьбе бобра с козлом побеждает бобро. Или козло.

Юляша
Популярный автор
Популярный автор
Сообщения: 3352
Зарегистрирован: 15 янв 2009, 12:32
Пол: Женский

Re: Задача для профессиональных математиков

Сообщение Юляша »

Шшок писал(а):
12 май 2022, 12:26
Красиво. Но еще надо доказать, что не существует пар, не принадлежащих к таким семействам... А вдруг при больших значениях a, b такие пары существуют?
Ну пятый пункт пока не доказан (просто руки не дошли). Если его доказать, то вопрос будет снят.

Неотрицательность доказывается элементарно. Осталось показать, что c<a.
Нас двое - я и папа
И погромче нас были витии Да не сделали пользы пером. Дураков не убавим в России, А на умных тоску наведем.

Юляша
Популярный автор
Популярный автор
Сообщения: 3352
Зарегистрирован: 15 янв 2009, 12:32
Пол: Женский

Re: Задача для профессиональных математиков

Сообщение Юляша »

Юляша писал(а):
12 май 2022, 13:01
Неотрицательность доказывается элементарно. Осталось показать, что c<a.
Вроде получается, если рассматривать равенство a^2+b^2=n(ab+1) как квадратное уравнение относительно b.
Нас двое - я и папа
И погромче нас были витии Да не сделали пользы пером. Дураков не убавим в России, А на умных тоску наведем.

Юляша
Популярный автор
Популярный автор
Сообщения: 3352
Зарегистрирован: 15 янв 2009, 12:32
Пол: Женский

Re: Задача для профессиональных математиков

Сообщение Юляша »

Итак, полное решение.
Вполне возможно (и даже скорее всего) оно не оптимально, но как получилось.

Это решение не появилось бы, если бы мне не захотелось проверить, существуют ли вообще подходящие пары чисел, с помощью простой компьютерной программы.
Эта программа, в частности, нашла семейство решений вида (x, x^3) - действительно x^2+x^6=x^2*(x*x^3+1), а также и другие решения, среди которых мне броислось в глаза семейство (8, 30), (30, 112), (112, 418). После проверки выяснилось, что для этого семейства всегда n=4. Отсюда и появилась идея доказательства.


1. Запишем выполнение условия в виде уравнения a^2+b^2=n(ab+1) (уравнение У1).
2. Расширим множество допустимых чисел до неотрицательных. В этом случае получим базовое семейство (БС) допустимых пар вида (0, x). У1 в этом случае принимает вид x^2=n*1, то есть, n=x^2.
3. Рассмотрим отдельно вариант a=b. Тогда из У1 2*a^2=n*(a^2+1). a^2+1 и a^2 взаимно просты, так что a^2+1=2 и a=1, n=1.
4. Значит достаточно рассмотреть пары вида (a, b), где a<b. Докажем, что для любой такой пары положительных a и b, удовлетворящиющих У1, можно найти пару неотрицательных x, y, удовлетворяющих У1 и таких, что x<a и y<b, а n не изменяется. Если это утверждение верно, то, повторяя эту операцию, мы в итоге методом "обратной индукции" придем к БС, а для него утверждение задачи уже доказано
5. Будем искать нужную пару в виде (с, а). Тогда a^2+b^2=n(ab+1), с^2+а^2=n(сa+1). Вычтем второе уравнение из первого, получим b^2-c^2=n(ab-ca) -> (b+c)(b-c)=na(b-c) -> b+c=na -> c=na-b. Неотрицательность с сразу следует из У1 для пары (с, а).
6. Обратим внимание на то, что У1 - это квадратное уравнение относительно b при фиксированных a и n, так что оно имеет два корня. Запишем его в виде b^2-nab+a^2-n=0.
7. Так как мы уже знаем, что оба корня неотрицательны, проверим утверждение, что меньший корень больше a.
(na-V((na)^2-4(a^2-n)))/2>a[/i] -> na-V((na)^2-4(a^2-n))>2a -> (n-2)a>V((na)^2-4(a^2-n)) ->* ((n-2)a)^2>(na)^2-4(a^2-n) -> -4na^2+4a^2>-4a^2+4n -> 2a^2>na^2+n. Мы пришли к очевидному противоречию (вариант n=1 можно было отбросить уже при переходе, помеченном звездочкой). А значит, утверждение в п.4 верно, из чего следует и исходное утверждение задачи. (Буква V представляет знак радикала.)
Нас двое - я и папа
И погромче нас были витии Да не сделали пользы пером. Дураков не убавим в России, А на умных тоску наведем.

Ответить

Вернуться в «Задачки»