Задача номер 3532 сумма кубов кириенко решение

Решение задачи числа 42 с помощью планетарного суперкомпьютера

Математикам наконец-то удалось найти три куба чисел, сумма которых равна 42. Так была решена задача, над которой ломали голову целых 65 лет: можно ли каждое из натуральных чисел от 1 до 100 выразить как сумму трёх кубов?

Задача, сформулированная в 1954 году, заключается именно в этом: x 3 +y 3 +z 3 =k. K — это каждое из чисел от 1 до 100; вопрос в том, каковы x, y и z?

За прошедшие десятилетия были найдены решения для самых лёгких чисел. В 2000 году математик Ноам Элкис из Гарвардского университета опубликовал алгоритм, упрощающий поиск решений для более сложных чисел.

На текущий год оставались только два самых сложных числа: 33 и 42.

Посмотрев видео о задаче числа 33 на популярном математическом YouTube-канале Numberphile, математик Эндрю Букер из Бристольского университета вдохновился на написание нового алгоритма. Он запустил его на мощном суперкомпьютере университетского центра сложных вычислителных исследований и всего за три недели получил решение для числа 33.

Так осталось самое сложное из всех чисел: 42. Доказано, что это гораздо более трудная задача, поэтому Букер воспользовался помощью коллеги-математика Эндрю Сазерленда из MIT, специалиста по масштабным параллельным вычислениям.

Как уже понятно из заголовка статьи, им удалось решить задачу. Чтобы поделиться своим успехом, они выбрали забавный способ: по данным The Aperiodical, оба математика втихомолку заменили свои личные веб-страницы на решение задачи, и назвали эти страницы «Жизнь, Вселенная и всё остальное», что является отсылкой к книге Дугласа Адамса.

Разумеется, поиск решения не был простым. Двум математикам пришлось просить помощи у Charity Engine — международной инициативы, использующей свободные вычислительные ресурсы более 500 тысяч домашних PC в качестве своеобразного «планетарного суперкомпьютера».

Нахождение решения заняло более миллиона часов машинного времени, но математики всё-таки смогли найти ответ.

То есть полное уравнение имеет вид (-80538738812075974) 3 + 80435758145817515 3 + 12602123297335631 3 = 42.

«Я чувствую огромное облегчение», — признаётся Букер.

«В этой игре невозможно быть уверенным, что удастся что-нибудь найти. Это немного похоже на предсказание землетрясений, приходится иметь дело только с приблизительными вероятностями. То есть мы могли найти ответ за несколько месяцев поисков, или на его поиск мог потребоваться целый век».

И что, на этом всё закончилось? Ну-у-у… не совсем. Ответ пока найден только для чисел от 1 до 100. Если подняться на один порядок величин, до 1000, то ещё остаётся довольно много нерешённых чисел — 114, 165, 390, 579, 627, 633, 732, 906, 921 и 975 по-прежнему ждут решения в виде суммы трёх кубов.

Источник

Почему сумма трёх кубов – это такая сложная математическая задача

Тяжело искать ответы в бесконечном пространстве. Математика уровня старших классов может помочь вам сузить область поисков.

Учитывая, что люди изучают свойства чисел тысячи лет, можно было бы решить, что нам известно всё о числе 3. Однако недавно математики обнаружили нечто новое касательно числа 3: третий способ выразить это число в виде суммы трёх кубов. Задача записи числа через сумму трёх кубов целых чисел оказывается неожиданно интересной. Легко показать, что большую часть чисел нельзя записать в виде одного куба или суммы из двух кубов, но существует гипотеза, что большую часть чисел можно записать в виде суммы из трёх кубов. Однако найти эти кубы оказывается иногда чрезвычайно сложно.

К примеру, нам было известно, что число 3 можно записать в виде 1 3 + 1 3 + 1 3 , а также в виде 4 3 + 4 3 + (-5) 3 , однако более 60 лет математиков интересовал вопрос, нет ли ещё одного способа сделать это. И в этом сентябре Эндрю Букер и Эндрю Сазерленд, наконец, нашли и третий способ:

3 = 569 936 821 221 962 380 720 3 + (−569 936 821 113 563 493 509) 3 + (−472 715 493 453 327 032) 3

Если вам захочется проверить этот результат, не пытайтесь использовать калькулятор. Большинство из них не справится с таким количеством цифр. Но с этим справится WolframAlpha.

В поисках новых вариантов решений для числа 3, математики используют техники, придуманные в этом году Буккером, первым нашедшим сумму трёх кубов для числа 33. Но почему на подобные прорывы требуется столько времени? В поисках правильных кубов приходится покрывать очень большую территорию, а нужное направление нам может указать лишь небольшое число подсказок. Поэтому фокус состоит в том, чтобы найти более хитрые методы поиска. Чтобы представить себе саму задачу и её решение, начнём с более простого вопроса: как мы можем записать 33 в виде суммы трёх целых чисел?

Мы можем записать 33 = 19 + 6 + 8, или 33 = 11 + 11 + 11, или 33 = 31 + 1 + 1. Мы можем использовать и отрицательные числа: 33 = 35 + (−1) + (−1). Существует бесконечное множество способов сделать это, поскольку всегда можно увеличить одно или два числа и уменьшить третье для компенсации этого – например, 33 = 36 + (−1) + (−2), 33 = 100 + 41 + (−108), и так далее.

Что насчёт записи 33 в виде суммы трёх квадратов? Нам нужно будет найти числа, являющиеся квадратами целых чисел, типа 1 = 1 2 , 9 = 3 2 , и 64 = 8 2 — их сумма даёт 33. Немного поигравшись, можно обнаружить, что 33 = 4 2 + 4 2 + 1 2 и 33 = 5 2 + 2 2 + 2 2 . Есть ли ещё варианты? В принципе, нет. Можно заменить 4 на -4, и получить 33 = (-4) 2 + 4 2 + 1 2 , что даст нам ещё несколько способов записи наши решений, но как их ни считай, найдётся не очень много способов записать 33 в виде суммы трёх квадратов.

При суммировании квадратов у нас нет той же гибкости, что при суммировании любых целых чисел. У нас меньше выбор, и, что ещё важнее, сложение лишь увеличивает нашу сумму. Ведь квадраты целых чисел не бывают отрицательными – возведение в квадрат и положительного и отрицательного числа всегда даёт положительное.

У квадратов больше ограничений, но это даёт нам и нечто полезное: наше пространство поисков «ограничено». Пытаясь найти три квадрата, дающих в сумме 33, мы не можем использовать числа, чьи квадраты больше, чем 33, поскольку как только наша сумма выйдет за пределы 33, уменьшить её уже не получится. А это значит, нам нужно рассмотреть лишь комбинации из 0 2 , 1 2 , 2 2 , 3 2 , 4 2 и 5 2 (их отрицательные двойники ничего нового нам не дают, и мы их проигнорируем).

Имея шесть вариантов для каждого их трёх квадратов, мы получаем не более 6 × 6 × 6 = 216 способов записать 33 как их сумму. Достаточно небольшой список для того, чтобы проверить все возможности и убедиться, что мы ничего не пропустили.

Теперь вернёмся к задаче о сумме трёх кубов. Несложно видеть, что она комбинирует ограниченный выбор из задачи о сумме квадратов с бесконечным пространством поиска из задачи о сумме целых чисел. Как и с квадратами, не любое целое число является кубом другого числа. Мы можем использовать числа типа 1 = 1 3 , 8=2 3 , 125=5 3 , но не можем использовать 2, 3, 4, 10, 108, и большую часть остальных чисел. Но, в отличие от квадратов, кубы бывают отрицательными – к примеру, (-2) 3 = -8, (-4) 3 = -64 – а значит, мы можем по необходимости и уменьшать нашу сумму. Доступ к отрицательным числам даёт нам неограниченное количество вариантов, то есть, наше пространство поиска, как и в случае с суммой целых чисел, неограниченно.

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

Допустим, вам нужно найти решение уравнения:

Простой подход – разметить некий регион чисел и подставлять каждый из них, пока что-нибудь не подойдёт. Если вы ничего не найдёте, можно определить новое пространство поиска и начать сначала. Это похоже на поиск новых планет при помощи методичного изучения неба в телескоп.

Представьте, что ваше начальное пространство поиска ограничивает все x, y и z рамками от -100 до 100. Сначала вы пробуете:

Не вышло. Тогда вы пробуете:

Тоже не работает. Вы продолжаете, пока не дойдёте до (100, −100, −100), потом переключаетесь на (−100, −99, −100), и вновь продолжаете свою охоту. В итоге вы проверите порядка 200 × 200 × 200 = 8 000 000 вариантов, не найдя ничего подходящего. Придётся обозначить новое пространство поиска и начать заново.

Более интересный подход – переписать уравнение в следующем виде:

Теперь, вместо того, чтобы перебирать все тройки (x, y, z), мы будем перебирать двойки (x, y). Для каждой пары мы будем вычислять результат, а потом проверять список кубов, смотря, нет ли там нашего результата z 3 . Если он есть, решение найдено. Если нет, мы продолжим искать. Это значительно уменьшает пространство поиска. Вместо 8 000 000 троек мы теперь ищем среди 200 × 200 = 40 000 пар. Серьёзная экономия, однако всё равно недостаточно для того, чтобы сделать задачу вычислительно доступной.

Ещё более удобный подход — переписать уравнение в следующем виде:

Теперь мы перебираем z, а для каждого вычисленного z мы используем хитрый фокус из курса математики. Выражение x 3 + y 3 всегда можно разложить так:

x 3 + y 3 = (x + y)(x 2 – xy + y 2 )

Это формула для суммы кубов. Чтобы проверить её, просто перемножим правую часть, пользуясь правилом дистрибутивности:

(x + y)(x 2 – xy + y 2 ) = x 3 – x 2 y + xy 2 + yx 2 – xy 2 + y 3 = x 3 + y 3

Как это помогает нам в поисках? Подсчитав 33 – z 3 , мы раскладываем её на произведение простых чисел, с чем хорошо справляются компьютеры, по крайней мере, в интересующем нас числовом диапазоне. Разложив 33 – z 3 на множители, мы проверяем, можно ли составить эти множители в виде (x + y)(x 2 – xy + y 2 ). Если да, мы нашли решение.

Допустим, к примеру, что мы пытаемся записать 34 как сумму трёх кубов, и наши поиски привели нас к z = -6. Мы подсчитываем 34 – z 3 = 34 – (-6) 3 = 34 – (-216) = 34 + 216 = 250, и теперь разложим 250.

Изучив вопрос, мы понимаем, что можем записать 250 = 10 × 25 = (5+5)(5 2 – 5 × 5 + 5 ² ). А это именно (x + y)(x 2 – xy + y 2 ) для x = 5 и y = 5, так что тройка (x, y, z) = (5, 5, -6) должна сработать для 34. И, конечно же, 34 = 5 3 + 5 3 + (-6) 3 , и мы успешно обнаружили три куба, сумма которых даёт 34.

Такой метод позволяет вместо 200 3 = 8 000 000 троек или даже 200 2 = 40 000 пар исследовать 200 возможных вариантов z. Дополнительную работу составляют разложение на множители и проверка, но в целом поисковая эффективность серьёзно растёт. И всё равно пространство поисков, изученное в поисках суммы кубов, дающих такое число, как 33, настолько огромно, что даже такие улучшения не могут помочь суперкомпьютерам близко подступиться к этой задаче.

Тут на сцену и вышел Эндрю Букер. Он разработал некоторые дополнительные техники, используя алгебру и теорию чисел, для ещё более сильного улучшения поисковой эффективности. Напустив суперкомпьютер своего университета на эту задачу, через три недели он получил впервые найденное представление числа 33 как суммы трёх кубов:

33 = 8 866 128 975 287 528 3 + (−8 778 405 442 862 239) 3 + (−2 736 111 468 807 040) 3

Решив эту задачу, перед тем, как перейти к числу 3, Букер и Сазерленд решили такую же задачу для числа 42:

42 = (−80 538 738 812 075 974) 3 + 80 435 758 145 817 515 3 + 12 602 123 297 335 631 3

Вас может удивить, что спустя тысячи лет, мы ещё можем узнать что-то новое о таких числах, как 3, 33 и 42. Возможно ещё более удивительным будет то, что этому могут помочь такие абстрактные вещи из школьной математики, как формула для суммы кубов. Однако так работает математика, и поэтому мы продолжаем наши изыскания. Так что следите за числом 114 – самым маленьким из чисел на сегодня, для которого пока ещё не найдена сумма из трёх кубов. У меня есть ощущение, что для Эндрю Букера и других математиков поиск уже начался.

Источник

Задача номер 3532 сумма кубов кириенко решение

1 января 2015 года Тарас Павлович взял в банке 1,1 млн рублей в кредит. Схема выплаты кредита следующая — 1 числа каждого следующего месяца банк начисляет 2 процента на оставшуюся сумму долга (то есть увеличивает долг на 2%), затем Тарас Павлович переводит в банк платёж. На какое минимальное количество месяцев Тарас Павлович может взять кредит, чтобы ежемесячные выплаты были не более 220 тыс. рублей?

Ясно, что чем больше месячные выплаты, тем быстрее будет выплачен долг. Значит, срок кредита будет минимален в том случае, когда выплаты составляют 220 тыс. рублей. Составим таблицу, в первом столбце которой будем указывать долг на первое число месяца, а во втором — долг в том же месяце, но уже после выплаты. Для упрощения расчётов будем сохранять только два знака после запятой, представляя суммы долга в тыс. рублей.

Месяц	Долг на первое число месяца (тыс. руб)	Долг после выплаты за предыдущий месяц (тыс. руб)
1	1100	—
2	1122	902
3	920,04	700,04
4	714,04	494,04
5	503,92	283,92
6	289,60	69,60
7	70,99	0

При указанной схеме платежей равно через 6 месяцев после взятия кредита в первый день седьмого месяца можно полностью рассчитаться с банком.

Источник

Задача номер 3532 сумма кубов кириенко решение

1 января 2015 года Тарас Павлович взял в банке 1,1 млн рублей в кредит. Схема выплаты кредита следующая — 1 числа каждого следующего месяца банк начисляет 2 процента на оставшуюся сумму долга (то есть увеличивает долг на 2%), затем Тарас Павлович переводит в банк платёж. На какое минимальное количество месяцев Тарас Павлович может взять кредит, чтобы ежемесячные выплаты были не более 220 тыс. рублей?

Ясно, что чем больше месячные выплаты, тем быстрее будет выплачен долг. Значит, срок кредита будет минимален в том случае, когда выплаты составляют 220 тыс. рублей. Составим таблицу, в первом столбце которой будем указывать долг на первое число месяца, а во втором — долг в том же месяце, но уже после выплаты. Для упрощения расчётов будем сохранять только два знака после запятой, представляя суммы долга в тыс. рублей.

Месяц	Долг на первое число месяца (тыс. руб)	Долг после выплаты за предыдущий месяц (тыс. руб)
1	1100	—
2	1122	902
3	920,04	700,04
4	714,04	494,04
5	503,92	283,92
6	289,60	69,60
7	70,99	0

При указанной схеме платежей равно через 6 месяцев после взятия кредита в первый день седьмого месяца можно полностью рассчитаться с банком.

Источник