Гроб, да не гроб

svyatogorodski — 25.05.2025 Авва вывесил задачку с международной олмпиады, которую на удивление плохо решали. Хотя новый президент Румынии решил. Официальное решение - гробульник (и для чистоты эксперимента я его, конечно, посмотрел потом), но за час-полтора нашлось очень естественное решение. Я уверен, что те, кто решил, действовали как-то аналогично. Мой главный пойнт описать процесс нахождение решения, а не записать его кратчайшим образом. Итак, задача такая: a,b целые положительные, докажите, что, если x=(а²+b²)/(ab+1) целое, то оно целый квадрат.

Решение вслух.

0. Первая прикидка (индивидуально и необязательно).

Первый же вопрос, что можно вообще сказать про решения задачи найти a,b, чтобы x был целым? Возможны варианты:
1. Решений конечное число (обычно есть общая причина, почему их не должно быть, но она не работает при слишком маленьких числах, и пара левых спорадических решений получают путевку в жизнь). Тут у всех них отношение случайно оказалось квадратом, а вопрос так задали, чтобы немножко нас сбить с толку. Плохой стиль, на ИМО не должно бы быть, но иногда так делают.
2. Решений одна (или несколько) явных бесконечных серий (как пифагоровы тройки). Тогда надо найти эти серии.
3. Решений бесконечно, одной формулой не задашь, но есть рекурсия от малых к большим или спуск от больших к малым, что есть две стороны одной медали (пример, который должен быть известен топовому олимпиаднику -- Ферма для n=4, может, и для n=3).
4. Описать структуру решений нельзя никак (или даже доказать, что их нет, если их нет), но каким-то образом можно контролировать х. Например, если есть какая-то скрытая симметрия/трансформации в задаче.

Навскидку, только по формуле, я бы гадал, что скорее всего 2, потом 3, потом 4. В единицу слабо верится из-за того что ну очень плохой стиль. Скажи "найти все решения", а не так.

1. Практическая возня с маленькими значениями.

Дальше надо попробовать найти пару частных решений поменьше, чтобы почувствовать задачу, прикинуть какой вариант имеем. Почти любой олимпиадник начнет с этого, если сразу не видно что-то лучшее, а многие начнут с этого в любом случае.

Начнем, конечно, с a=1. Тогда b+1 | b²+1, значит b+1 делит (b²+1) - (b²-1)=2. Подходит только b=1. Дальше берем a=2, идея, как делить с остатком а ля Евклид уже есть из прошлого случая, имеем 2b+1 | b²+4, значит 2b+1 делит (4b²+4b+1) - 4(b²+4)=4b-15, значит 2b+1 делит 2(2b+1) - (4b-15)=17. Подходит только b=8, и (8²+2²)/(16+1)=4. Нетривиальное решение и не такое маленькое... Если есть время, то можно и a=3 рассмотреть, получить b=27 и угадать одну бесконечную серию, но в целом понятно, что тоже самое можно сделать когда a -- параметр. Таким образом, мы набрели на первую общую идею:

2. Алгоритм Евклида с параметром для исключения одного неизвестного из делимого.
ab+1 делит а²+b², значит он делит и b²(а²+b²) - (ab+1)²=b⁴-2ab-1, значит он делит и (b⁴-2ab-1)+2(ab+1)=b⁴+1. Опа, уравнение стало несимметричным но намного более интересным: ab+1 | b⁴+1. Во-первых, мы сразу угадываем одну бесконечную серию -- a=b³, и тогда легко видеть, что x=b². Kакие-то баллы за это должны дать, уже есть, что писать (видимо, давали всего один бал -- многие получили бал). Но главное, мы видим, что для каких-то b бывают и другие решения, например, если просто поменять a,b и взять b=а³, то b⁴+1=a¹²+1 делится на  ab+1=a⁴+1. В этот момент, вариант 1 уже просвистел, и довольно ясно, что и общей формулы мы не получим -- задача свелась к поиску делителей определенного вида у чисел b⁴+1, тривиальным случаем, как мы уже поняли, дело не ограничивается... остаются варианты 3 или 4.

3. The point.

Собственно, мы подошли к критическому этапу. В этот момент требуется одно миниозарение. Или элемнтарная внимательность. Но, в любом случае, это шаг, который не должен вызывать проблем у сильных олимпиадников, а, может, по силам и читателям. Я остановлюсь здесь, а допишу завтра.

Оставить комментарий

Популярные посты:

• Ранее
• Архив