упаковка в квадрате
Если взять прямоугольники со сторонами 1 и 1/2, потом 1/2 и 1/3, потом 1/3 и 1/4 и так далее, то нетрудно увидеть, что сумма площадей всего этого бесконечного числа прямоугольников равна 1.
Поэтому логично поинтересоваться, можно ли все эти прямоугольники уместить внутрь квадрата 1 на 1. Оказывается, этот вопрос остается открытым, с тех пор, как в 1960-х его сформулировал Лео Мозер (родившийся в Вене, но выросший в Канаде).
(почему сумма площадей равна 1? Потому что площадь каждого из них 1/n(n+1) можно представить как 1/n - 1/(n+1), и в бесконечной сумме таких площадей всё, кроме 1, сокращается)
На картинке - иллюстрация из знаменитого учебника "Конкретная математика" Кнута, Грэма и Паташника. Там эта задача приводится в качестве "исследовательского упражнения". Отмечается разногласие среди соавторов по вопросу того, какой ответ они предсказывают. Кнут считает, что можно уместить, Грэм что нельзя, Паташник предпочел не высказывать мнение.
Известно, что можно уместить все эти прямоугольники внутрь квадрата со стороной 133/132 (есть также утверждение насчет 501/500, но я меньше уверен в этом доказательстве). Известно, что если существует упаковка в квадрат со стороной 1+epsilon для любого сколь угодно малого положительного epsilon, то существует также упаковка в просто 1x1. Но плотнее, чем epsilon=1/132 или 1/500 никто не упаковал пока. И напрямую в 1x1 тоже, и не доказал, что это невозможно. Вопрос остается открытым.
Китайский ученый Yilei Chen говорит на своем сайте, что из-за этой задачи - о которой он узнал во время учебы в университете - он решил заняться наукой. А сейчас он опубликовал очень сложный препринт, в котором утверждается решение с помощью квантовых алгоритмов нескольких важных проблем на целых решетках (lattice problems). Если алгоритм Чена действительно верен, это будет иметь огромное значение для криптографии, пока что больше теоретическое, но потом и практическое. Об этом пишет Скотт Ааронсон в своем блоге.