Иэн Стюарт - Математические головоломки профессора Стюарта

– Поскольку вы не знаете самих чисел, p не может быть произведением двух простых, таким как 35. Ведь 35 – это 5 × 7, и никак иначе выразить это число как произведение двух чисел, больших 1, невозможно, так что вы сразу поняли бы, какие два числа имеются в виду. По аналогичной причине p не может равняться кубу простого числа, такому как 5³ = 125, поскольку такое число раскладывается только как 5 × 25.

– Да, это понятно, – вставил я.

– Кроме того, p не может быть равно qm , где q – простое число, а m – составное, поскольку для любого d больше 1, которое является делителем m, qd будет больше 100.

– Ну, даааа…

– К примеру, p не может быть равным 67 × 3 × 5, что раскладывается на множители тремя способами: 67 × 15, 201 × 5 и 335 × 3. Поскольку в двух последних случаях используются числа больше 100, на эти способы разложения можно не обращать внимания, и остается только один способ, с числами 67 и 15.

– Верно.

– Итак, ваше замечание помогает мне понять все это, но к тому моменту я и сам сделал те же выводы на основании известной мне суммы чисел. Я видел, что s не является суммой двух таких чисел. Но затем вы тоже об этом узнали, потому что я вам сказал, то есть вы узнали кое-что новое о числе s . Конечно, оба мы должны помнить, что если s = 200, то оба числа должны равняться 100, а если s = 199, то они равняются 100 и 99.

– Разумеется.

– Если исключить невозможное… – сказал Сомс, – получится, что сумма s может равняться одному из следующих чисел: 11, 17, 23, 27, 29, 35, 37, 41, 47, 51 и 53.

– Но раньше вы с большим пренебрежением отзывались о…

– О, в математике это правило достаточно хорошо работает, – небрежно ответил он. – Потому что здесь мы можем быть уверены, что невозможное на самом деле невозможно.

– Итак, на главной стадии рассуждений мы оба знаем то, что я только что вам рассказал. И в этот момент вы быстро объявляете, что можете определить нужные нам числа! Так что я быстро перебираю все возможные пары чисел с этими суммами и обнаруживаю, что 10 из 11 вариантов s имеет одно из возможных произведений, совпадающее с произведением для другого значения s . Поскольку вы сказали мне, что уже знаете нужные нам числа, все 10 таких s можно смело исключить из расследования. Остается единственный возможный вариант суммы, 17, и единственное произведение, не допускающее двух разных значений s . А именно 52, которое получится, если представить 17 как 4 + 13, и только в этом случае. Следовательно, два наших числа – это 4 и 13.

Я поздравил Сомса с такой проницательностью.

– Пошлите кого-нибудь из Нерушимых сил Бейкер-стрит к Роулейду с этим сообщением, – скомандовал он, быстро записывая числа на клочке бумаги. – Не пройдет и часа, как двое злоумышленников будут арестованы.

В 1930 г. Хайман Лоб и Херберт Ричмонд доказали, что в некоторых случаях жадный алгоритм дает лучшее решение, чем построение Малфатти. Ховард Ивз в 1946 г. заметил, что для равнобедренного треугольника с очень острой вершиной пирамидальное построение почти вдвое больше по площади, чем построение Малфатти. В 1967 г. М. Голдберг доказал, что жадный алгоритм всегда лучше варианта Малфатти, а в 1994 г. Виктор Залгаллер и Г. А. Лось доказали, что он всегда дает наибольшую возможную площадь.

M. R. Schroeder, Diffuse sound reflection by maximum-length sequence. Journal of the Acoustical Society of America 57 (1975) 149–150.

János Pach and Ethan Sterling, Conway's conjecture for monotone thrackles, American Mathematical Monthly 118 (June/July 2011) 544–548.

Я ломал голову три часа кряду, но в конце концов сдался и попросил Сомса раскрыть секрет.

– Но потом вы скажете мне, как все абсурдно просто.

– Нет! Никогда!

– Позволю себе не согласиться, Ватсап. Потому что на этот раз все действительно просто до абсурдности, – молчание тянулось и тянулось, и он смилостивился: – Очень хорошо. Будем считать, что в нашем распоряжении имеется только черная и серая краска, а белым цветом отмечены еще не рассмотренные области. Начнем с того, что покрасим одну из областей в черный цвет (см. верхнюю левую фигуру на рисунке). После этого я выбираю одну из примыкающих областей и окрашиваю ее в серый цвет (верхняя средняя фигура). Затем окрашиваю примыкающую область черным, затем следующую – серым и т. д.