Max Home IndustryИграя с кирпичами в детстве, мы все понимаем идею выступа — или, по крайней мере, раньше думали, что понимаем. Отмеченные наградами исследования показывают, что это еще не все.
Приятно осознавать, что Microsoft Research занимается не только изобретением датчиков всего тела, таких как Kinect. Недавно Theory Group получила премию Дэвида П. Роббинса от Математической ассоциации Америки — возможно, это не медаль Филдса, но работа увлекательна, если вы заинтересованы в решении задач.
Эта конкретная проблема называется проблемой максимального выступа, и она считалась решенной в течение очень долгого времени — пока член группы Theory не стал соавтором статьи под названием «Максимальный выступ», которая также может быть хорошим названием для камня. группа.
Проблема очень проста. Все, что вам нужно сделать, это взять несколько кирпичей (подойдут книги, если они не электронные) и создать стопку с самым большим выступом для этого количества кирпичей.
Если вы попробуете, вы быстро поймете причину, по которой это сложная проблема. Слегка свес книги дает большую устойчивость, но небольшой свес, в то время как выталкивание кирпичей дальше дает больший свес, но колонна быстрее становится неустойчивой. Вы также можете сделать вывод, что можете создать выступ из более чем одного блока, но не можете.
Решение состоит в том, чтобы взять n кирпичей и расположить их так, чтобы каждый из них перекрывался на 1 / (2B), где B — номер кирпича (начиная сверху):
Это создает стопку кирпичей, которая нависает на 1 / 2логн. Поскольку серия 1 / n является гармонической серией, это называется гармоническим стеком, и считалось, что это лучший выступ, который вы можете получить с помощью всего n кирпичей. Также обратите внимание, что по мере расхождения гармонических рядов вы можете создать выступ любого размера при наличии достаточного количества кирпичей.
Гармонический стек — это элегантное решение, поэтому для вас стало сюрпризом узнать, что вы можете добиться большего, создавая стопки, которые напоминают плохо построенную стену. Для решения необходимы отверстия, неровные края и специальные противовесы. С помощью компьютерного поиска были найдены оптимальные стопки размером n = 20 и n = 20:
Оптимальный стек для n = 20 по сравнению с гармоническим стеком
Оптимальный стек для n = 30 по сравнению с гармоническим стеком
Однако для полного решения проблемы вам понадобится верхняя граница вылета как функция от n — очевидно, что результаты n = 20 и n = 30 означают, что это не может быть классическая гармоническая граница log n.
Вопрос решается путем создания модели, которой сбалансированная стопка из n кирпичей должна удовлетворять с точки зрения сил, и демонстрации того, что вылет должен быть меньше 6n ^ 1/3. Это делается с учетом того, что распределение сил, необходимое для сбалансированной стопки, такое же, как и в задаче движения массы — сколько ходов нужно, чтобы сместить начальное распределение массы, чтобы данная пропорция переместилась за заданное расстояние. Оказывается, легче поставить ограничения на эту проблему, чем на проблему вылета, и это дает результат, что вылет может быть не более 6n ^ (1/3).
«Начиная с единицы массы в начале координат, сколько ходов нужно, чтобы переместить половину массы на расстояние n, где при каждом перемещении выбирается узел k между -n и n, а масса в k делится поровну между k -1 и k + 1. Легко видеть, что порядка n3 ходов достаточно, и ключевым шагом статьи о максимальном выступе было показать, что это количество ходов также необходимо ».
Обратите внимание, что это верхняя граница, и нет никаких доказательств того, что ее можно достичь — именно так часто бывает неконструктивная математика! На данный момент наибольший фактически достижимый вылет составляет 0,57n ^ (1/3) при использовании «кирпичной стены» примерно параболической формы:
Стопка «6» n = 111 с выступом 3
У нас все еще нет четкой верхней границы того, какой вылет может быть достигнут. Вы можете продвинуть тему, найдя стабильные стеки, которые приближаются к верхней границе, или доказав это неконструктивными методами — я знаю, какой из них мне кажется более привлекательным …