21.05.2025 13:38
PatientZero 6 853 Источник

Сложность текста: 2-3/5

Необходимые знания: должно быть достаточно основ теории многочленов, например, формул Виета

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

Интернет переполнен «математическими задачками с эмодзи», которые выглядят примерно так:

https://engineeringdiscoveries.com/wp-content/uploads/2019/03/Untitled-2nmmmmmmmmmmmmm.jpg

Они более-менее продуманы, поэтому в них легко запутаться (приглядитесь к бананам), и у людей получаются разные ответы, что вызывает споры и обсуждения, делая посты виральными и так далее...

Естественно, настоящим математикам это надоело. В начале 2017 года на Reddit появился пост с заголовком «Меня утомила вся эта фейсбучная фруктовая математика. Хочет кто-нибудь придумать действительно сложную математическую задачу, чтобы побороться с этим явлением?». Один пользователь создал такую картинку:

https://i.imgur.com/IVOs9IP.png
«95% людей не смогут решить эту задачку! Сможете найти значения каждого из фруктов?»

Она не особо сложна. Её можно легко решить для целых чисел, если быть терпеливым или перебрать все варианты. Но здесь начинается самое интересное.

Пользователь по имени Сридхар Рамеш увидел эту картинку и решил внести небольшое изменение, прежде чем распространять её.

https://i.redd.it/p92108lekoq11.jpg
«95% людей не смогут решить эту задачку! Сможете найти положительные целые значения каждого из фруктов?»

Благодаря этому задача стала ужасно сложной. Самое маленькое решение имеет длину более восьмидесяти разрядов. Доктор Алон Амит назвал её «умной и злой шуткой». Считается, что для её решения нужен высокий уровень знаний в области эллиптических кривых.

Но когда это нас останавливало? В посте мы решим эту задачу. Точнее, я опишу, как наконец-то решил её.

Разогреемся

Для начала попробуем решить задачу попроще

Задача: найти все пифагоровы тройки.

Решение. Нам нужно решить диофантово уравнение 

$x^2+y^2=z^2$

для неотрицательных целых чисел. Но это неприятно. Мы были бы гораздо счастливее, если бы нужно было вместо этого решить

$$x_1^2+y_1^2 = 1$$

где x_1 и y_1 — неотрицательные рациональные числа. По сути, это та же задача, потому что решение

$x^2+y^2=z^2$

эквивалентно решению

$\left(\frac{x}{z}\right)^2+\left(\frac{y}{z}\right)^2=1$

То есть мы, по сути, принимаемx_1=x/zиy_1=y/z.

Тонкости

На самом деле, они не совсем эквивалентны, потому что хотя каждая(x,y,z)будет соответствовать(x_1,y_1), в обратную сторону мы пойти не сможем. Например,(3,4,5)и(6,8,10)соответствуют(3/5,4/5). Исправить это легко: какие бы решения мы не получали для(x,y,z)из(x_1,y_1), мы просто будем помнить, что нельзя будет получить и любые кратные. Эта проблема более-менее решает сама себя. Подумайте, сможете ли вы понять сами, почему.

Мы так довольны этим, потому что теперь задача формулируется как «найти все рациональные точки в единичной окружности», где рациональная точка — это просто точка с рациональными координатами. Действительно ли это легче сделать?

Вот трюк, который позволит решить задачу.

  1. Начнём с нахождения какой-нибудь подходящей точкиP = (x_1,y_1). Я возьму(0,1).

  2. Проведём прямую с рациональным наклоном, проходящую черезP. Что-то типаy = \frac{m}{n}x+1, гдеm/nрационально.

    [asy] unitsize(2cm); draw(circle((0,0),1)); pair A,B; A = (0,1); B = (24/25,7/25); draw(B+7/4*(A-B)--A+(7/4)*(B-A),arrow=Arrows,p=red); dot("$(0,1)$",A,NE); dot(B); draw((-2,0)--(2,0),arrow=Arrows); draw((0,-2)--(0,2),arrow=Arrows); [/asy]

  3. Она будет всегда (практически) пересекать окружность во второй точкеQ.

  4. Тогда Qвсегда будет ещё одной рациональной точкой!

Почему это так? Чтобы найти координаты этой второй точки, мы решаем систему уравненийx_1^2+y_1^2 = 1иy_1 = \frac{m}{n}x_1 + 1. Однако мы уже знаем одно решение:(x_1,y_1) = (0,1). Поэтому мы избавляемся отy_1, чтобы получить квадратичное уравнение

$$x_1^2+\left(\frac{m}{n}x_1+1\right)^2=1, \qquad (*)$$

Мы можем рассуждать следующим образом:

  • Коэффициенты уравнения рациональны.

  • Следовательно, по формулам Виета, сумма корней рациональна.

  • Мы знаем, что один корень рационален, потому что провели прямую через рациональную точку. Следовательно, другой корень должен быть рациональным.

  • Еслиx_1рационален, то\frac{m}{n}x_1 + 1рационально; следовательно,y_1рационально.

  • Следовательно, вторая точка пересечения этой прямой с окружностью — это рациональная точка.

Можно сделать вывод, что, проведя любую прямую с рациональным наклоном черезP, мы получим ещё одну рациональную точку на окружности. Но и это ещё не всё. Обратим внимание, что если(x_1',y_1')— ещё одна рациональная точка, то прямая, соединяющаяPи(x_1',y_1'), должна иметь рациональный наклон. То есть, если мы проведём каждую прямую рациональной точки черезP, то получим ВСЕ возможные рациональные точки на окружности.

Давайте найдём эту вторую точку для всех возможных наклоновm/n. Развернув уравнение(*), получим:

$$\frac{m^2+n^2}{n^2}x_1^2 + \frac{2m}{n}x_1 = 0$$

Мы уже знаем, чтоx_1 = 0был корнем, поэтому координатаx_1, которую мы ищем — это ещё один корень, который задаётся какx_1 = \frac{-2mn}{m^2+n^2}. Соответствующее значение дляy_1имеет вид\frac{n^2-m^2}{m^2+n^2}. Сократив делители и подчистив знаки, мы увидим, что ВСЕ пифагоровы тройки можно охарактеризовать следующим образом:

$$(x,y,z) = \left(2mn,n^2-m^2,n^2+m^2\right)$$

для положительных чиселm,nвплоть до какого-то целочисленного кратного. Это очень удобное свойство из олимпиадной теории чисел, о котором вы могли слышать.

Важный вывод здесь заключается в том, что проводя прямые, мы будем получать новые точки. Выше мы провели лишь одну прямую через точку, чтобы получить ещё одну точку. Хоть это не подходит для решения исходной задачи, принцип очень похож. Давайте приступим!

Приступаем к решению

Итак, мы начинаем со следующего уравнения:

$$\frac{x}{y+z}+\frac{y}{x+z}+\frac{z}{x+y}=4$$

Подчистив знаменатели, мы в конечном итоге придём к следующему:

$$x^3+y^3+z^3 = 3(x^2(y+z)+y^2(x+z)+z^2(x+y)) + 8xyz$$

Вместо того, чтобы пытаться решить это в положительных числах, мы выразим уравнение относительноx_1иy_1, попробовав найти рациональные точки, положительные и отрицательные. Будем надеяться, что это упростит решение.

Разделив уравнение наz^3, мы получим

$$(x/z)^3+(y/z)^3+1 = 3((x/z)^2(y/z+1)+(y/z)^2(x/z+1)+x/z+y/z) + 8(x/z)(y/z)$$
$$x_1^3+y_1^3+1 = 3(x_1^2(y_1+1)+y_1^2(x_1+1)+x_1+y_1) + 8x_1y_1$$

График этого уравнения будет выглядеть так:

https://i.imgur.com/bzCVSqs.png

Можно заметить, что он «повёрнут» на45^\circ. Это логично, потому что перемена местамиx_1 иy_1не должна ничего менять в показанном выше уравнении.

Для моего собственного удобства (этот шаг необязателен, но я его сделал) я решил повернуть график, чтобы он был симметричным относительно осиx. Я сделал это, подставивx_2-y_2 = x_1и x_2+y_2=y_1. Теперь это уравнение с новыми рациональными переменнымиx_2иy_2, а уравнение принимает вид:

$$1 - 6 x_2 - 11 x_2^2 - 4 x_2^3 - y_2^2 + 12 x_2y_2^2 = 0$$

Так гораздо удобнее. Теперь график выглядит так:

https://i.imgur.com/NDn5txV.png

Красиво и симметрично! Такая кривая называется эллиптической.

Достаточно посмотреть на график, чтобы увидеть очевидные рациональные точки:(0,1),(-1,0)и(0,-1), которые я обозначуP,3Pи5P. (Тому есть причины, о которых мы поговорим во второй части статьи.)

https://i.imgur.com/jZdIjMb.png

К сожалению, нахождение этих точек не означает, что мы решили задачу. Они соответствуют неправильным решениям исходной задачи. Но можем ли мы использовать эти «лёгкие точки», чтобы найти другие?

Эпичное возвращение трюка с прямыми

Получить ещё больше точек нам позволит следующий процесс.

  1. Начинаем с двух рациональных точекPиQ, лежащих на эллиптической кривой.

  2. Проводим прямую\overline{PQ}. Отмечаем, что она имеет рациональный наклон, потому чтоPиQ— рациональные точки.

  3.  \overline{PQ} всегда будет пересекать эллиптическую кривую в третий раз (включая кратность) в точкеR.

  4. Более того,Rвсегда будет ещё одной рациональной точкой!

Здесь нужно объяснить некоторые аспекты: почему прямая будет пересекаться в третий раз и почему третье пересечение должно быть рациональной точкой? Мы рассуждаем следующим образом, аналогичным предыдущим рассуждениям из раздела «Разогреваемся»:

  • Третья точкаR=(x_2,y_2)удовлетворяет системе уравнений

    $$\begin{cases}1 - 6 x_2 - 11 x_2^2 - 4 x_2^3 - y_2^2 + 12 x_2y_2^2 = 0 \\ ax_2+by_2=1\end{cases},$$

    гдеax_2+by_2=1— уравнение прямой, проходящей через точкиPи
    Q.

  • Если мы найдёмy_2из второго уравнения и подставим его в первое уравнение, чтобы сократить переменную, то у нас останется кубическое уравнение дляx_2.

  • Это кубическое уравнение имеет рациональные коэффициенты, потому что коэффициентыaиbдолжны быть рациональными, поскольку прямая имеет рациональный наклон и проходит через рациональные точки.

  • Следовательно, по формулам Виета, сумма корней кубического уравнения — это рациональное число.

  • Два корня определяются координатамиx_2точекPиQ, а обе они рациональны.

  • Следовательно, третий корень рационален. Это значит, что координатаx_2точкиRрациональна.

  • Воспользовавшисьax_2+by_2=0, мы можем сделать вывод, что координатаy_2тоже рациональна. Следовательно,R— рациональное число.

Отлично! Важное дополнение: пересечения подсчитываются с учётом кратности. Допустим, можно взятьPиQтак, чтобы они были одной точкой. Тогда «прямая» на самом деле будет касательной к кривой в точкеP, но всё равно будет работать. Обязательно разберитесь, почему это так!

Теперь мы знаем, что если соединить две рациональные точки эллиптической кривой, то можно получить ещё одну рациональную точку на кривой. Давайте попробуем это сделать.

Соединив(0,1)и(-1,0)прямой, мы найдём, что существует третье пересечение в(-1/2,1/2).

https://i.imgur.com/5KrB52C.png

И в самом деле, если мы подставим эти значения, то всё сойдётся! Что ещё можно получить?

«Соединив(0,1)и(0,1)прямой» или взяв касательную к(0,1), мы можем найти ещё одно третье пересечение с кривой.

https://i.imgur.com/BMn9h0j.png

На этот раз она находится в(-1/2,-1/2). Это довольно просто: мы могли бы выяснить это, взяв предыдущую полученную точку и отразив её относительно осиx. Можем ли мы легко получить что-то ещё? На самом деле, нет. Причина в том, что эти5точек (и ещё одна скрытая «точка», о которой я не буду говорить) — это точки кручения. Сколько бы раз мы ни повторяли этот трюк с прямой, новых точек мы не получим.

Это плохо. Как же нам получить точки, которые «сбежали» от этих5точек?

Находим больше точек (бесконечного порядка)

Я довольно глупый, поэтому написал код Mathematica, чтобы попробовать найти менее тривиальные точки кривой.

https://i.imgur.com/ibVDVhX.png

И мне удалось найти красивые точки! Я долго экспериментировал с точками, но оказалось, что нам подходит первая точка(-2,1/5). Я обозначу эту точкуA

.

https://i.imgur.com/61rkWvt.png

Прежде чем мы перейдём к поиску других точек, нужно осветить два момента.

Во-первых, какую рациональную точку я пытаюсь найти? Если мы проверимA, то выясним, что она не подходит, потому что некоторые из получившихся переменныхx,y,zмогут оказаться отрицательными. Поэтому мы пытаемся найти рациональные точки(x_2,y_2), такие, чтобы они соответствовали полностью положительной тройке(x,y,z). Когда такое происходит? Давайте порассуждаем об этом, немного вернувшись назад.

  • Мы можем предположить, что какая-то переменная (zбез потери общности) положительна, потому что если все переменныеx,y,zотрицательны, мы получим положительное решение, поменяв все знаки.

  • Тогдаx,y > 0, еслиx/z,y/z>0. То естьx_1,y_1 > 0

  • Это значит, что нам нужноx_2+y_2 > 0иx_2-y_2 > 0. Иными словами,x_2 > |y_2|.

Это соответствует следующей зелёной области:

https://i.imgur.com/BEDmeWy.png

Повторимся: наша цель — найти рациональное число на кривой, лежащей в этой области. Следовательно, задача превращается в забавный «математический футбол»: нам нужно использовать трюк с прямыми для генерации всё большего количества точек, пока мы не достигнем «гола», то есть зелёной области.

Вручную это делать крайне утомительно. К счастью, у меня есть Mathematica! Это подводит нас ко второму вопросу, который я хотел рассмотреть: как нам упростить наш трюк с прямыми?

Выполнив развёртывание при помощи Mathematica, я выяснил, что кубическое уравнение. полученное из нахождения третьего пересечения прямой, проходящей через точки(a,b)и(c,d), имеет сумму корней, задаваемую следующим образом:

$$\frac{-(11 a^2 - 22 a c + 11 c^2 + b^2 (1 + 24 c) + d^2 + 24 a d (-b + d) - 2 b (d + 12 c d))}{(4 (a^2 - 3 b^2 - 2 a c + c^2 + 6 b d - 3 d^2))}$$

То есть, по формулам Виета, мы можем написать формулу для координатыx_2третьего пересечения:

$$L(a,b,c,d) := \frac{-(11 a^2 - 22 a c + 11 c^2 + b^2 (1 + 24 c) + d^2 + 24 a d (-b + d) - 2 b (d + 12 c d))}{(4 (a^2 - 3 b^2 - 2 a c + c^2 + 6 b d - 3 d^2))} - a - c$$

Аналогично, мне удалось записать формулу для третьего пересечения, имея касательную в точке(a,b):

$$T(a,b) := \frac{-(-9 - 282 a - 1741 a^2 - 3900 a^3 - 3204 a^4 - 864 a^5 - 47 b^2 + 1860 a b^2 + 4680 a^2 b^2 + 3456 a^3 b^2 + 108 b^4 - 2592 a b^4) }{108 + 792 a + 1884 a^2 + 1584 a^3 + 432 a^4 - 436 b^2 - 1488 a b^2 - 1440 a^2 b^2 + 432 b^4}-2a$$

Как некрасиво! Именно поэтому числа будут огромными.

Кроме того, эти формулы дают нам только координатыx. Координатуy(положительную) легко можно найти при помощи одной последней формулы, которая достаточно просто выводится (можно буквально просто выразитьy_2):

$$Y(x) := \sqrt{\frac{1 - 6 x - 11 x^2 - 4 x^3}{1 - 12 x}}$$

А теперь давайте закончим наш бой.

Финал

ИзAя проведу касательную и найду третье пересечение в новой точке-2A. (Здесь тоже не стоит беспокоиться о названиях!)

https://i.imgur.com/rtBLd2Q.png

Наши формулы дадут координаты для-2A:

https://i.imgur.com/1SfWEPD.png

Из-2Aя проведу ещё одну касательную и найду третье пересечение в новой точке4A.

https://i.imgur.com/YRdhBz8.png
https://i.imgur.com/IspQusz.png

Mathematica снова подскажет нам координаты4Aпри помощи формул.

https://i.imgur.com/tE1PHhx.png

Мы пока не смогли попасть в зелёную область, поэтому нужно продолжать двигаться дальше. Как это ни неприятно, я проведу ещё одну касательную в4A, чтобы получить точку-8A:

https://i.imgur.com/5JNs7NJ.png

Она имеет следующие координаты:

https://i.imgur.com/3E4HwyT.png

С касательными мы закончили! Для удобства я нанёс на график точку8A, которая просто соответствует-8Aс обратной координатойy_2, и соединил4Pс8Aпрямой, чтобы получить точку-8A-4P:

https://i.imgur.com/saSMd4j.png

Координаты:

https://i.imgur.com/ggLuFXK.png

В этом и заключался мой великий план! Мне нужна была настолько высокая точка, чтобы наконец попасть в зелёную область с ещё одной прямой. Что это за прямая? Рад, что вы спросили! Всё это время оставлял на последний момент одну последнюю «красивую» рациональную точку:B = (-15/2,7/2)! Проведя прямую междуBи-8A-4P, мы наконец-то окажется в точке в зелёной области:

https://i.imgur.com/mAegeBX.png

Координаты:

https://i.imgur.com/SrCf2px.png

Свет в конце туннеля уже близок! Сделав эту последнюю точку(x_2,y_2), мы вычислимx_2+y_2иx_2-y_2, чтобы получитьx_1иy_1:

$$x_1 = \frac{36875131794129999827197811565225474825492979968971970996283137471637224634055579}{ 4373612677928697257861252602371390152816537558161613618621437993378423467772036}$$
$$y_1 = \frac{154476802108746166441951315019919837485664325669565431700026634898253202035277999}{ 4373612677928697257861252602371390152816537558161613618621437993378423467772036}$$

Вспомнив, что они равны, соответственно,x/yиx/z, мы сделаемzнаименьшим общим кратным знаменателей, аx,yбудут итоговыми числителями, когда мы найдём общий знаменатель. Так мы получим это огромное решение... в положительных целых числах!

$$X = 36875131794129999827197811565225474825492979968971970996283137471637224634055579$$
$$Y = 154476802108746166441951315019919837485664325669565431700026634898253202035277999$$
$$Z = 4373612677928697257861252602371390152816537558161613618621437993378423467772036$$

Чтобы по-настоящему оценить нашу работу, мы можем убедиться, что они действительно подходят.

https://i.imgur.com/JXcc55N.png

Комментарии (6)


  1. LeshaRB
    21.05.2025 14:33
    #28334264

    (приглядитесь к бананам)

    Наверное, к кокосам?

    PS Бананы тоже отличаются, вопрос снят


  1. askv
    21.05.2025 14:33
    #28334294

    А теперь попробуйте эту


  1. chrooter
    21.05.2025 14:33
    #28334590

    яблоки бананы ананасы
    A - яблоко B-банан C-ананас


  1. Sazonov
    21.05.2025 14:33
    #28334860

    Мне почему-то вот эта картинка вспомнилась:


    1. Newpson
      21.05.2025 14:33
      #28334922

      Скрытый текст
      \frac{5\pi}{2}


      1. Oncenweek
        21.05.2025 14:33
        #28335054

        Hidden text

        Не, аутентичнее: бургер*pi/кружкапива