Гроб, да не гроб
May. 26th, 2025 11:25 pm![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
svyatogorodskiАвва вывесил задачку с международной олмпиады, которую на удивление плохо решали. Хотя новый президент Румынии справился. Официальное решение - гробульник (и для чистоты эксперимента я его, конечно, посмотрел только потом), но за час-полтора нашлось очень естественное решение. Я уверен, что те, кто решил, действовали как-то аналогично. Мой главный пойнт описать процесс нахождение решения, а не записать его кратчайшим образом. Итак, задача такая: a,b целые положительные, докажите, что, если x=(а2+b2)/(ab+1) целое, то оно целый квадрат.
Решение вслух.
0. Первая прикидка (индивидуально и необязательно).
Первый же вопрос, что можно вообще сказать про решения задачи найти a,b, чтобы x был целым? Возможны варианты:
1. Решений конечное число (обычно есть общая причина, почему их не должно быть, но она не работает при слишком маленьких числах, и паралевых спорадических решений получают путевку в жизнь). Тут у всех них отношение случайно оказалось квадратом, а вопрос так задали, чтобы немножко нас сбить с толку. Плохой стиль, на ИМО не должно бы быть, но иногда так делают.
2. Решений одна (или несколько) явных бесконечных серий (как пифагоровы тройки). Тогда надо найти эти серии.
3. Решений бесконечно, одной формулой не задашь, но есть рекурсия от малых к большим или спуск от больших к малым, что есть две стороны одной медали (пример, который должен быть известен топовому олимпиаднику -- Ферма для n=4, может, и для n=3).
4. Описать структуру решений нельзя никак (или даже доказать, что их нет, если их нет), но каким-то образом можно контролировать х. Например, если есть какая-то скрытая симметрия/трансформации в задаче.
Навскидку, только по формуле, я бы гадал, что скорее всего 2, потом 3, потом 4. В единицу слабо верится из-за того что ну очень плохой стиль. Скажи "найти все решения", а не так.
1. Практическая возня с маленькими значениями.
Дальше надо попробовать найти пару частных решений поменьше, чтобы почувствовать задачу, прикинуть какой вариант имеем. Почти любой олимпиадник начнет с этого, если сразу не видно что-то лучшее, а многие начнут с этого в любом случае.
Начнем, конечно, с a=1. Тогда b+1 | b2+1, значит b+1 делит (b2+1) - (b2-1)=2. Подходит только b=1. Дальше берем a=2, идея, как делить с остатком а ля Евклид уже есть из прошлого случая, имеем 2b+1 | b2+4, значит 2b+1 делит (4b2+4b+1) - 4(b2+4)=4b-15, значит 2b+1 делит 2(2b+1) - (4b-15)=17. Подходит только b=8, и (82+22)/(16+1)=4. Нетривиальное решение и не такое маленькое... Если есть время, то можно и a=3 рассмотреть, получить b=27 и угадать одну бесконечную серию, но в целом понятно, что то же самое можно сделать, когда a -- параметр. Таким образом, мы набрели на первую общую идею:
2. Алгоритм Евклида с параметром для исключения одного неизвестного из делимого.
ab+1 делит а2+b2, значит он делит и b2(а2+b2) - (ab+1)2=b4-2ab-1, значит он делит и (b4-2ab-1)+2(ab+1)=b4+1. Опа, уравнение стало несимметричным, но намного более интересным: ab+1 | b4+1. Во-первых, мы сразу угадываем одну бесконечную серию -- a=b3, и тогда легко видеть, что x=b2. Kакие-то баллы за это должны дать, уже есть, что писать (видимо, давали всего один балл -- многие получили балл). Но главное, мы видим, что для каких-то b бывают и другие решения, например, если просто поменять a,b и взять b=а3, то b4+1=a12+1 делится на ab+1=a4+1. В этот момент, вариант 1 уже просвистел, и довольно ясно, что и общей формулы мы не получим -- задача свелась к поиску делителей определенного вида у чисел b4+1, тривиальным случаем, как мы уже поняли, дело не ограничивается... остаются варианты 3 или 4.
3. Пуанта/миниозарение.
Итого, наша задача -- как-то описать пары (b,d), где d -- делитель b4+1 вида d=ab+1, т..е d имеет остаток 1 при делении на b. Я оставлю это в качестве упражнения (и оно всплывет в конце решения), но наши переходы были эквивалентными -- мы не получили лишних решений (а есть и еще эквивалентные формулировки, которые не помогают, a могут только запутать и потратить ваше время -- ab+1 делит a4+1, или b3-a, или a3-b).
Мы уже видели, что кроме тривиального решения a=b3 (дающего нетривиальное решение исходной задачи), бывают и другие. Если есть время, можно тупо перебрать маленькие b, разложить на множители b4+1, дойти до b=8 (где, как мы знаем, есть интересное решение с a=2, d=17) и увидеть.. что оно не одно. Тогда и миниозарения не надо. А можно просто обратить внимание, что b4+1 вообще-то тоже 1 по модулю b, а значит, и дополнительный делитель (а делители ходят парами) тоже будет 1 по модулю b. Другими словами, мы обязательно имеем b4+1=(ab+1)(cb+1). Второе решение не видно в "тривиальном случае", когда второй делитель 1 и c=0 -- а в задаче c>0. Кстати, а почему не c ≥ 0? Ведь пары 0,b тоже подходят -- (b2+0)/(0*b+1)=b2... Теперь ясно, зачем -- чтобы замаскировать механизм спуска, который мы, наконец, нашли: если a,b -- решение, то и b,c -- решение, где a и c связаны через b4+1=(ab+1)(cb+1) или b3=acb+(a+c). Более того, не может быть, что a>b и c>b, потому что тогда abc > b3, поэтому из решения b<c мы всeгда можем получить меньшее решение a<b, пока не упремся. В реале упремся, когда a=0, и все очевидно, но в задаче числа положительные и упремся на шаг раньше, тоже нам хорошо уже знакомом -- когда c=b3 и следующий шаг сделал бы a=0.
4. Дело техники.
Любой уважающий себя олимпиадник, дойдя досюда и имея полчаса в остатке (что совсем не всегда будет верно после решения и записи первух двух задач и страданий с третьей), своего уже не отдаст. Остается только проверить, что если b4+1=(ab+1)(cb+1) и x=(b2+a2)/(ab+1) -- квадрат, то и y=(b2+c2)/(bc+1) -- квадрат. Это гарантированно условием, а значит должно быть несложно доказать. Надо найти связь x и y. Если повезет, то они вообще равны, если нет -- то, скорее всего, будет простая формула, дающая, что их отношение -- квадрат. Тут мы уже прошли критическую часть -- нашли рекурсию/спуск, и сто дорог ведут в Рим. Вопрос только, напишешь пару строчек или полстраницы. Можно тупо половить шансы в расчете на легкое везение и проверить не равны ли отношения, помня что b3=acb+(a+c). А можно, как сделал я, связать то, с чего мы начали -- эквивалентность того, что ab+1 делит b4+1 или b2+a2. Такой подход, когда раскроешь скобки, дает, что bc+1=(b4+1)/(ab+1)=(1-ab)+b2(b2+a2)/(ab+1), т.е. b(a+c)=b2x. Опа -- левая часть симметрична относительно замены двух решений, значит, совсем не работая, мы также имеем, что b(a+c)=b2y, и таки x=y. Happy end.
P.S. Так в чем же дело?
Если есть разумное решение, не требующее слишком нетривиальных ходов, то почему же задачу решило так мало народу, и на ней прокололись очень сильные олимпиадники? У меня есть только одно объяснение -- они... слишком хорошо и быстро считали. Это я сейчас ленюсь пару лишних строчек зря написать в черновике, решаю не торопясь, в свое удовольствие. Чистый и быстрый счет на олимпиаде -- важное техническое умение, как в шахматах. Скорее всего, они очень быстро наткнулись на решение 2,8, а, может, и 3,27, поэтому догадались, что пары b,b3 решение, подставили и проверили -- и все это еще до деления с остатком с параметром. Таким образом, не дойдя до правильной переформулировки, что ab+1 делит b4+1, они набрели на ложный след, который в этот момент кажется весьма правдоподобным -- имеем вариант 2, а не 3, -- есть одна бесконечная серия b,b3, и надо доказать, что других нет. Вопросом, что отношение -- квадрат (а не про найти все решения) нас сбивают с толку, маскируют ответ. Немножко дешево, для шестой задачи на ИМО, но все бывает... Время они потратили на попытку доказать неверное утверждение, других решений не видели, в своем решении написали про эту серию и спекуляции на тему, почему других решений нет (в надежде на частичный балл, если эти рассуждения в правильном направлении), но, так как, это шаг совсем не туда, и версия неправильная, то и получили всего один балл -- таких оценок за задачу было немало. Если это так, то на самом деле задача оказалось сложной неожиданным элементом -- излишне напрашивающимся ложным ходом.
Решение вслух.
0. Первая прикидка (индивидуально и необязательно).
Первый же вопрос, что можно вообще сказать про решения задачи найти a,b, чтобы x был целым? Возможны варианты:
1. Решений конечное число (обычно есть общая причина, почему их не должно быть, но она не работает при слишком маленьких числах, и пара
2. Решений одна (или несколько) явных бесконечных серий (как пифагоровы тройки). Тогда надо найти эти серии.
3. Решений бесконечно, одной формулой не задашь, но есть рекурсия от малых к большим или спуск от больших к малым, что есть две стороны одной медали (пример, который должен быть известен топовому олимпиаднику -- Ферма для n=4, может, и для n=3).
4. Описать структуру решений нельзя никак (или даже доказать, что их нет, если их нет), но каким-то образом можно контролировать х. Например, если есть какая-то скрытая симметрия/трансформации в задаче.
Навскидку, только по формуле, я бы гадал, что скорее всего 2, потом 3, потом 4. В единицу слабо верится из-за того что ну очень плохой стиль. Скажи "найти все решения", а не так.
1. Практическая возня с маленькими значениями.
Дальше надо попробовать найти пару частных решений поменьше, чтобы почувствовать задачу, прикинуть какой вариант имеем. Почти любой олимпиадник начнет с этого, если сразу не видно что-то лучшее, а многие начнут с этого в любом случае.
Начнем, конечно, с a=1. Тогда b+1 | b2+1, значит b+1 делит (b2+1) - (b2-1)=2. Подходит только b=1. Дальше берем a=2, идея, как делить с остатком а ля Евклид уже есть из прошлого случая, имеем 2b+1 | b2+4, значит 2b+1 делит (4b2+4b+1) - 4(b2+4)=4b-15, значит 2b+1 делит 2(2b+1) - (4b-15)=17. Подходит только b=8, и (82+22)/(16+1)=4. Нетривиальное решение и не такое маленькое... Если есть время, то можно и a=3 рассмотреть, получить b=27 и угадать одну бесконечную серию, но в целом понятно, что то же самое можно сделать, когда a -- параметр. Таким образом, мы набрели на первую общую идею:
2. Алгоритм Евклида с параметром для исключения одного неизвестного из делимого.
ab+1 делит а2+b2, значит он делит и b2(а2+b2) - (ab+1)2=b4-2ab-1, значит он делит и (b4-2ab-1)+2(ab+1)=b4+1. Опа, уравнение стало несимметричным, но намного более интересным: ab+1 | b4+1. Во-первых, мы сразу угадываем одну бесконечную серию -- a=b3, и тогда легко видеть, что x=b2. Kакие-то баллы за это должны дать, уже есть, что писать (видимо, давали всего один балл -- многие получили балл). Но главное, мы видим, что для каких-то b бывают и другие решения, например, если просто поменять a,b и взять b=а3, то b4+1=a12+1 делится на ab+1=a4+1. В этот момент, вариант 1 уже просвистел, и довольно ясно, что и общей формулы мы не получим -- задача свелась к поиску делителей определенного вида у чисел b4+1, тривиальным случаем, как мы уже поняли, дело не ограничивается... остаются варианты 3 или 4.
3. Пуанта/миниозарение.
Итого, наша задача -- как-то описать пары (b,d), где d -- делитель b4+1 вида d=ab+1, т..е d имеет остаток 1 при делении на b. Я оставлю это в качестве упражнения (и оно всплывет в конце решения), но наши переходы были эквивалентными -- мы не получили лишних решений (а есть и еще эквивалентные формулировки, которые не помогают, a могут только запутать и потратить ваше время -- ab+1 делит a4+1, или b3-a, или a3-b).
Мы уже видели, что кроме тривиального решения a=b3 (дающего нетривиальное решение исходной задачи), бывают и другие. Если есть время, можно тупо перебрать маленькие b, разложить на множители b4+1, дойти до b=8 (где, как мы знаем, есть интересное решение с a=2, d=17) и увидеть.. что оно не одно. Тогда и миниозарения не надо. А можно просто обратить внимание, что b4+1 вообще-то тоже 1 по модулю b, а значит, и дополнительный делитель (а делители ходят парами) тоже будет 1 по модулю b. Другими словами, мы обязательно имеем b4+1=(ab+1)(cb+1). Второе решение не видно в "тривиальном случае", когда второй делитель 1 и c=0 -- а в задаче c>0. Кстати, а почему не c ≥ 0? Ведь пары 0,b тоже подходят -- (b2+0)/(0*b+1)=b2... Теперь ясно, зачем -- чтобы замаскировать механизм спуска, который мы, наконец, нашли: если a,b -- решение, то и b,c -- решение, где a и c связаны через b4+1=(ab+1)(cb+1) или b3=acb+(a+c). Более того, не может быть, что a>b и c>b, потому что тогда abc > b3, поэтому из решения b<c мы всeгда можем получить меньшее решение a<b, пока не упремся. В реале упремся, когда a=0, и все очевидно, но в задаче числа положительные и упремся на шаг раньше, тоже нам хорошо уже знакомом -- когда c=b3 и следующий шаг сделал бы a=0.
4. Дело техники.
Любой уважающий себя олимпиадник, дойдя досюда и имея полчаса в остатке (что совсем не всегда будет верно после решения и записи первух двух задач и страданий с третьей), своего уже не отдаст. Остается только проверить, что если b4+1=(ab+1)(cb+1) и x=(b2+a2)/(ab+1) -- квадрат, то и y=(b2+c2)/(bc+1) -- квадрат. Это гарантированно условием, а значит должно быть несложно доказать. Надо найти связь x и y. Если повезет, то они вообще равны, если нет -- то, скорее всего, будет простая формула, дающая, что их отношение -- квадрат. Тут мы уже прошли критическую часть -- нашли рекурсию/спуск, и сто дорог ведут в Рим. Вопрос только, напишешь пару строчек или полстраницы. Можно тупо половить шансы в расчете на легкое везение и проверить не равны ли отношения, помня что b3=acb+(a+c). А можно, как сделал я, связать то, с чего мы начали -- эквивалентность того, что ab+1 делит b4+1 или b2+a2. Такой подход, когда раскроешь скобки, дает, что bc+1=(b4+1)/(ab+1)=(1-ab)+b2(b2+a2)/(ab+1), т.е. b(a+c)=b2x. Опа -- левая часть симметрична относительно замены двух решений, значит, совсем не работая, мы также имеем, что b(a+c)=b2y, и таки x=y. Happy end.
P.S. Так в чем же дело?
Если есть разумное решение, не требующее слишком нетривиальных ходов, то почему же задачу решило так мало народу, и на ней прокололись очень сильные олимпиадники? У меня есть только одно объяснение -- они... слишком хорошо и быстро считали. Это я сейчас ленюсь пару лишних строчек зря написать в черновике, решаю не торопясь, в свое удовольствие. Чистый и быстрый счет на олимпиаде -- важное техническое умение, как в шахматах. Скорее всего, они очень быстро наткнулись на решение 2,8, а, может, и 3,27, поэтому догадались, что пары b,b3 решение, подставили и проверили -- и все это еще до деления с остатком с параметром. Таким образом, не дойдя до правильной переформулировки, что ab+1 делит b4+1, они набрели на ложный след, который в этот момент кажется весьма правдоподобным -- имеем вариант 2, а не 3, -- есть одна бесконечная серия b,b3, и надо доказать, что других нет. Вопросом, что отношение -- квадрат (а не про найти все решения) нас сбивают с толку, маскируют ответ. Немножко дешево, для шестой задачи на ИМО, но все бывает... Время они потратили на попытку доказать неверное утверждение, других решений не видели, в своем решении написали про эту серию и спекуляции на тему, почему других решений нет (в надежде на частичный балл, если эти рассуждения в правильном направлении), но, так как, это шаг совсем не туда, и версия неправильная, то и получили всего один балл -- таких оценок за задачу было немало. Если это так, то на самом деле задача оказалось сложной неожиданным элементом -- излишне напрашивающимся ложным ходом.
