Entry tags:
о красивой и тяжелой задаче
Давайте я вам расскажу про задачу номер шесть Международной Математической Олимпиады в 1988 году. Оказывается, эта задача знаменита (в узких кругах математиков, интересующихся олимпиадными задачами) своей сложностью. На последнее, шестое место традиционно ставят самую тяжелую задачу. В том году шестую задачу полностью решило всего 11 участников из многих сотен. Среди них был Никушор Дан, новый румынский президент (так я узнал об этой задаче), а вот например знаменитый математик Теренс Тао не смог ее решить. Ему, правда, было только 13 лет, но это все равно был Теренс Тао.
Немецкий математик Артур Энгель пишет так об этой задаче в своей книге "Стратегии решения задач":
"Следующая задача была подана в 1988 году от ФРГ. Никто из шести членов австралийского комитета по задачам не смог её решить. Двое из членов были Дьёрдь и Эстер Секереш, оба известные решатели и составители задач. Поскольку это была задача по теории чисел, её отправили четырём самым известным австралийским специалистам по теории чисел. Их попросили поработать над ней в течение шести часов. Никто из них не смог решить её за это время. Комитет по задачам представил её жюри XXIX Международной математической олимпиады, отметив двойной звёздочкой, что означало сверхсложную задачу, возможно, слишком сложную для предложения. После долгого обсуждения жюри наконец набралось смелости выбрать её в качестве последней задачи соревнования. Одиннадцать студентов представили идеальные решения."
Вот эта задача. Дано, что a,b положительные целые числа, и a^2+b^2 без остатка делится на a*b+1. Доказать, что результат этого деления - полный квадрат (т.е. число вида x^2).
Ее решение, которое я подсмотрел в википедии, так элегантно и просто, что не могу удержаться от соблазна рассказать его здесь. Как это сочетается с тем, что это супер-тяжелая задача, которую почти никто не решил? Дело в том, что до главной идеи доказательства очень тяжело додуматься самому, и можно лишь позавидовать таланту тех 11, кому это удалось.
Да, перед тем, как рассказать решение, отмечу еще один интересный факт об этой задаче. Ее автор - некий Стефан Бек (Stephan Beck) из Западной Германии. Никто не знает, как она пришла ему в голову, и никто не может его спросить, потому что никто не знает, кто он такой. Математика с таким именем, публикующего научные статьи, не существует (есть генетик, вряд ли это он). В разных книгах и постах в интернете мне попались сожаления о том, что авторы не смогли ничего о нем разузнать. Я перелопатил вчера кучу интернетной руды и единственная кроха, которую нашел - это что этот же человек подавал от Германии две другие задачи, которые вошли в списки кандидатов для Олимпиад-1995 и -2002, но не были в итоге использованы. Это упоминается в книге "IMO Compendium", и там есть условия этих двух задач, они тоже по теории чисел. Если кто-то может разыскать какую-то информацию о нем, поделитесь, это интересно.
Теперь обещанное решение. Докажем от противного. Пусть A,B числа, опровергающие условие: можно записать Α^2+B^2 = k(AB+1), где k какое-то целое положительное число, но не полный квадрат. Если A=B, то неизбежно k=1 и это квадрат, так что мы можем предположить, что одно из них больше другого, например A > B.
Теперь сгруппируем эти числа как квадратное уравнение от "переменной" A:
A^2 - (kB)A + (B^2-k) = 0
Мы знаем, что у этого уравнения есть одно решение: собственно A! Значит, есть еще одно, некое C (при этом гипотетически возможно C=A, хотя потом мы докажем, что нет), и по формулам Виета выполняются два равенства:
A+C = kB
A*C = B^2-k
Из первого равенства мы видим, что C целое число, оно равно kB-A. Из того, что C выполняет уравнение, мы видим - группируя в обратную сторону - что C^2+B^2 = k(CB+1), и поскольку в этом уравнении всё, кроме CB+1, положительно, CB+1 тоже >0, и значит C положительное или 0. Однако C не может быть 0, потому что из второго равенства следовало бы B^2-k = 0, но k не полный квадрат (вот где мы этим воспользовались!). Значит, C > 0.
Наконец, из второго равенства выше мы видим, что A*C = B^2-k < B^2, и поскольку мы предположили A>B, неизбежно C < A, иначе их произведение было бы больше B^2.
Итак, мы пришли к тому, что контрпример к исходному утверждению в виде A,B, где A>B, можно заменить на C,B, где C<A, все еще оба числа положительные и выполняют, что нужно, и это новый контрпример. При этом сумма A+B уменьшается и становится C+B. Но это значит, что мы можем строить контрпримеры неограниченно долго, все время уменьшая сумму A+B - а это абсурдно (скажем, если бы вначале эта сумма была 1000, мы не сможем уменьшать ее больше 1000 раз). Поэтому таких A,B не существует, т.е. из Α^2+B^2 = k(AB+1) следует, что k полный квадрат. Что и требовалось доказать. Эта техника перехода от A к C, где оба - решения одного квадратного уравнения, называется "прыжки Виета", Vieta jumping.
Немецкий математик Артур Энгель пишет так об этой задаче в своей книге "Стратегии решения задач":
"Следующая задача была подана в 1988 году от ФРГ. Никто из шести членов австралийского комитета по задачам не смог её решить. Двое из членов были Дьёрдь и Эстер Секереш, оба известные решатели и составители задач. Поскольку это была задача по теории чисел, её отправили четырём самым известным австралийским специалистам по теории чисел. Их попросили поработать над ней в течение шести часов. Никто из них не смог решить её за это время. Комитет по задачам представил её жюри XXIX Международной математической олимпиады, отметив двойной звёздочкой, что означало сверхсложную задачу, возможно, слишком сложную для предложения. После долгого обсуждения жюри наконец набралось смелости выбрать её в качестве последней задачи соревнования. Одиннадцать студентов представили идеальные решения."
Вот эта задача. Дано, что a,b положительные целые числа, и a^2+b^2 без остатка делится на a*b+1. Доказать, что результат этого деления - полный квадрат (т.е. число вида x^2).
Ее решение, которое я подсмотрел в википедии, так элегантно и просто, что не могу удержаться от соблазна рассказать его здесь. Как это сочетается с тем, что это супер-тяжелая задача, которую почти никто не решил? Дело в том, что до главной идеи доказательства очень тяжело додуматься самому, и можно лишь позавидовать таланту тех 11, кому это удалось.
Да, перед тем, как рассказать решение, отмечу еще один интересный факт об этой задаче. Ее автор - некий Стефан Бек (Stephan Beck) из Западной Германии. Никто не знает, как она пришла ему в голову, и никто не может его спросить, потому что никто не знает, кто он такой. Математика с таким именем, публикующего научные статьи, не существует (есть генетик, вряд ли это он). В разных книгах и постах в интернете мне попались сожаления о том, что авторы не смогли ничего о нем разузнать. Я перелопатил вчера кучу интернетной руды и единственная кроха, которую нашел - это что этот же человек подавал от Германии две другие задачи, которые вошли в списки кандидатов для Олимпиад-1995 и -2002, но не были в итоге использованы. Это упоминается в книге "IMO Compendium", и там есть условия этих двух задач, они тоже по теории чисел. Если кто-то может разыскать какую-то информацию о нем, поделитесь, это интересно.
Теперь обещанное решение. Докажем от противного. Пусть A,B числа, опровергающие условие: можно записать Α^2+B^2 = k(AB+1), где k какое-то целое положительное число, но не полный квадрат. Если A=B, то неизбежно k=1 и это квадрат, так что мы можем предположить, что одно из них больше другого, например A > B.
Теперь сгруппируем эти числа как квадратное уравнение от "переменной" A:
A^2 - (kB)A + (B^2-k) = 0
Мы знаем, что у этого уравнения есть одно решение: собственно A! Значит, есть еще одно, некое C (при этом гипотетически возможно C=A, хотя потом мы докажем, что нет), и по формулам Виета выполняются два равенства:
A+C = kB
A*C = B^2-k
Из первого равенства мы видим, что C целое число, оно равно kB-A. Из того, что C выполняет уравнение, мы видим - группируя в обратную сторону - что C^2+B^2 = k(CB+1), и поскольку в этом уравнении всё, кроме CB+1, положительно, CB+1 тоже >0, и значит C положительное или 0. Однако C не может быть 0, потому что из второго равенства следовало бы B^2-k = 0, но k не полный квадрат (вот где мы этим воспользовались!). Значит, C > 0.
Наконец, из второго равенства выше мы видим, что A*C = B^2-k < B^2, и поскольку мы предположили A>B, неизбежно C < A, иначе их произведение было бы больше B^2.
Итак, мы пришли к тому, что контрпример к исходному утверждению в виде A,B, где A>B, можно заменить на C,B, где C<A, все еще оба числа положительные и выполняют, что нужно, и это новый контрпример. При этом сумма A+B уменьшается и становится C+B. Но это значит, что мы можем строить контрпримеры неограниченно долго, все время уменьшая сумму A+B - а это абсурдно (скажем, если бы вначале эта сумма была 1000, мы не сможем уменьшать ее больше 1000 раз). Поэтому таких A,B не существует, т.е. из Α^2+B^2 = k(AB+1) следует, что k полный квадрат. Что и требовалось доказать. Эта техника перехода от A к C, где оба - решения одного квадратного уравнения, называется "прыжки Виета", Vieta jumping.
