 |
-
Vladimirovich
-
-
OFFLINE
-
Инквизитор
-
- Posts: 99846
- Thank you received: 1816
-
Karma: 101
-
|
Математики установили рекорд по плотной упаковке тетраэдров
lenta.ru/news/2009/08/14/pack/
www.princeton.edu/main/news/archive/S25/...l?section=topstories
Princeton pair sets world record in packing puzzle
Математики из Принстона при помощи компьютерного моделирования смогли построить наиболее плотную упаковку тетраэдров в замкнутом трехмерном объеме из известных на сегодняшний день.
Я чего-то не понимаю...
Вроде тетраэдры плотно пакуются...
Или это надо их строго в куб закатать? Тогда да, будут дыры.
|
|
-
azur
-
-
OFFLINE
-
Бояринъ
-
- Posts: 239
- Thank you received: 1
-
Karma: 1
-
|
Вот. Задачку придумал.
Каждый день прилетает Правильный Мух и садится на шахматную доску.
Двигается строго по прямым, проходящим через центры клеток (на то он и Правильный). Пройдя все центры, улетает.
Сегодня он решил стартовать с центра какой-нибудь клетки и двигаться строго по вертикалям и горизонталям с поворотами только в центрах, да призадумался:
какой максимальной длины может быть его маршрут при минимально возможном числе поворотов?
Отредактировано azur (2009-08-14 19:05:46)
|
|
-
Vladimirovich
-
-
OFFLINE
-
Инквизитор
-
- Posts: 99846
- Thank you received: 1816
-
Karma: 101
-
|
Тут два экстремальных условия и надо бы расставить приоритеты.
Что важнее - минимум поворотов или максимальная длина ?
|
|
-
azur
-
-
OFFLINE
-
Бояринъ
-
- Posts: 239
- Thank you received: 1
-
Karma: 1
-
|
Оба важны. Надо среди всех возможных маршрутов с минимальным количеством поворотов найти самый длинный ..
|
|
-
Vladimirovich
-
-
OFFLINE
-
Инквизитор
-
- Posts: 99846
- Thank you received: 1816
-
Karma: 101
-
|
azur написал(а): Оба важны. Надо среди всех возможных маршрутов с минимальным количеством поворотов найти самый длинный .. Т.е минимум важнее получается?
|
|
-
azur
-
-
OFFLINE
-
Бояринъ
-
- Posts: 239
- Thank you received: 1
-
Karma: 1
-
|
Vladimirovich написал(а): Т.е минимум важнее получается? Да, именно так
|
|
-
azur
-
-
OFFLINE
-
Бояринъ
-
- Posts: 239
- Thank you received: 1
-
Karma: 1
-
|
PS. Дело в том, что максимум длины стремится к бесконечности, очевидно (можно бесконечно ходить по 63 клеткам и лишь затем пойти на последнюю, 64-ю)
В таких маршрутах искать минимум поворотов - гиблое дело
|
|
-
Vladimirovich
-
-
OFFLINE
-
Инквизитор
-
- Posts: 99846
- Thank you received: 1816
-
Karma: 101
-
|
Ну в общем навскидку - два маршрута по 14 поворотов
Один по пиле - а1-а8-b8-b1-c1-c8-...
8x7+7x1 насчитал = 63
А второй спираль из центра - d5-e5-e4-c4-c5-f6-f3-....
1+1+2+2+3+3+4+4+5+5+6+6+7+7+7 = 63
Тоже
Может все равно как ходить?
|
|
-
azur
-
-
OFFLINE
-
Бояринъ
-
- Posts: 239
- Thank you received: 1
-
Karma: 1
-
|
|
|
-
Vladimirovich
-
-
OFFLINE
-
Инквизитор
-
- Posts: 99846
- Thank you received: 1816
-
Karma: 101
-
|
azur написал(а): PS. Дело в том, что максимум длины стремится к бесконечности, очевидно (можно бесконечно ходить по 63 клеткам и лишь затем пойти на последнюю, 64-ю)
В таких маршрутах искать минимум поворотов - гиблое дело Ну тогда я не понял условия
Я думал по всем по одному разу почему-то
|
|
-
azur
-
-
OFFLINE
-
Бояринъ
-
- Posts: 239
- Thank you received: 1
-
Karma: 1
-
|
Vladimirovich написал(а): Ну тогда я не понял условия При минимуме поворотов ведь можно и пройти по одной и той же клетке дважды ..
|
|
-
СюгировФан
-
-
OFFLINE
-
Боярин
-
- Posts: 5541
- Thank you received: 221
-
Karma: 33
-
|
84?
a1-a8-h8-h1-b1-b8-g8-g1-c1-c8-f8-f1-d1-d8-e8-e1.
|
|
-
Vladimirovich
-
-
OFFLINE
-
Инквизитор
-
- Posts: 99846
- Thank you received: 1816
-
Karma: 101
-
|
azur написал(а): При минимуме поворотов ведь можно и пройти по одной и той же клетке дважды .. Ну тады надо подумать...
Я сразу не так понял
|
|
-
azur
-
-
OFFLINE
-
Бояринъ
-
- Posts: 239
- Thank you received: 1
-
Karma: 1
-
|
Vladimirovich написал(а): Я чего-то не понимаю...
Вроде тетраэдры плотно пакуются... Кроме кубов никакие равные многогранники плотно не пакуются. В свое время Улам выдвинул гипотезу, что упаковка равных сфер (~0,74048) плотнее, чем выпуклых многогранников .. Недавно выяснилось, что уже в случае с тетраэдрами это не так .. А сейчас упаковка тетраэдров достигла плотности ~0,782
Отредактировано azur (2009-08-15 01:57:38)
|
|
-
СюгировФан
-
-
OFFLINE
-
Боярин
-
- Posts: 5541
- Thank you received: 221
-
Karma: 33
-
|
87 для 14 поворотов:
d1-d8-h8-h1-c1-c8-g8-g1-b1-b8-f8-f1-a1-a8-e8-e1
Отредактировано СюгировФан (2009-08-15 22:16:08)
|
|
-
Vladimirovich
-
-
OFFLINE
-
Инквизитор
-
- Posts: 99846
- Thank you received: 1816
-
Karma: 101
-
|
azur написал(а): Кроме кубов никакие равные многогранники плотно не пакуются. Вот нет у меня много пирамидков под рукой...
Угол пространственный у вершины вроде кратный пространственному углу тетраэдра?
Могу ошибаться конечно...
|
|
-
Vladimirovich
-
-
OFFLINE
-
Инквизитор
-
- Posts: 99846
- Thank you received: 1816
-
Karma: 101
-
|
Эээ. ув. СюгировФан , по 15-16 поворотов легко крутить
Вот по 14 - пока я такой минимум нашел. Условия были, что минимум первичен
|
|
-
СюгировФан
-
-
OFFLINE
-
Боярин
-
- Posts: 5541
- Thank you received: 221
-
Karma: 33
-
|
Ув. Владимирович, у меня вроде 14 поворотов.
|
|
-
Vladimirovich
-
-
OFFLINE
-
Инквизитор
-
- Posts: 99846
- Thank you received: 1816
-
Karma: 101
-
|
СюгировФан написал(а): Ув. Владимирович, у меня вроде 14 поворотов. Вах, ув. СюгировФан, прошу прощения. Я типа по ходам ладьей посчитал,а не по поворотам.
-1 мне
Тогда Ваш последний вариант не знаю пока, как превзойти ..
|
|
-
azur
-
-
OFFLINE
-
Бояринъ
-
- Posts: 239
- Thank you received: 1
-
Karma: 1
-
|
Попробуйте доказать, что 14 это минимум
|
|
-
СюгировФан
-
-
OFFLINE
-
Боярин
-
- Posts: 5541
- Thank you received: 221
-
Karma: 33
-
|
13 поворотов-это 7 вертикальных и 7 горизонтальных ходов ладьёй. Есть вертикаль и есть горизонталь, вдоль которых ладья не ходила. В точку их пересечения ладья попасть не могла.
|
|
-
azur
-
-
OFFLINE
-
Бояринъ
-
- Posts: 239
- Thank you received: 1
-
Karma: 1
-
|
СюгировФан написал(а): 13 поворотов-это 7 вертикальных и 7 горизонтальных ходов ладьёй. Есть вертикаль и есть горизонталь, вдоль которых ладья не ходила. В точку их пересечения ладья попасть не могла.
87 - это мой правильный ответ и тоже не вижу как превзойти ..
|
|
-
Swordman
-
-
OFFLINE
-
Жилец
-
- Posts: 53
-
Karma: 0
-
|
В свое время в сети были очень популярны флеш-игры одного японца: Toshimitsu Tagagi.
Если еще не играли, можете убить час свободного времени на первой из них - ogl.ru/flash/play/1334 красная комната
|
|
-
Vladimirovich
-
-
OFFLINE
-
Инквизитор
-
- Posts: 99846
- Thank you received: 1816
-
Karma: 101
-
|
korrespondent.net/tech/science/938590
Математики из Канады рассчитали оптимальную стратегию борьбы с гипотетическим нашествием зомби: рамках работы ученые использовали классические представления о зомби как о медленно передвигающихся живых трупах. При этом они считали, что укус зомби приводит к превращению укушенного в одного из живых мертвецов. На основе этих предположений исследователи моделировали распространение инфекции зомби, а также пытались выяснить оптимальную стратегию борьбы с ней. В ходе исследования, математики выяснили, что лучшим вариантом является тотальное уничтожение живых мертвецов. Попытки найти вакцину против зомби-вируса или изолировать живых мертвецов пользы не принесут. По расчетам исследователей, скорость распространения зомби колоссальна - живые мертвецы способны захватить целый город с населением в 500 тысяч человек всего за трое суток.
|
|
-
azur
-
-
OFFLINE
-
Бояринъ
-
- Posts: 239
- Thank you received: 1
-
Karma: 1
-
|
Опять прилетал Правильный Мух. Сегодня решил двигаться только по диагоналям.
Долго думал при каком минимуме числа поворотов ему удастся пройти все центры клеток одного цвета ..
|
|
-
СюгировФан
-
-
OFFLINE
-
Боярин
-
- Posts: 5541
- Thank you received: 221
-
Karma: 33
-
|
15
a1-h8-g7-h6-c1-a3-f8-e7-h4-e1-a5-d8-c7-h2-g1-a7-b8.
|
|
-
Vladimirovich
-
-
OFFLINE
-
Инквизитор
-
- Posts: 99846
- Thank you received: 1816
-
Karma: 101
-
|
|
|
-
azur
-
-
OFFLINE
-
Бояринъ
-
- Posts: 239
- Thank you received: 1
-
Karma: 1
-
|
СюгировФан написал(а): 15 Обосновать попробуем?
|
|
-
СюгировФан
-
-
OFFLINE
-
Боярин
-
- Posts: 5541
- Thank you received: 221
-
Karma: 33
-
|
Разобьём доску на прямоугольники a3-f8-h6-c1: a5-d8-h4-e1: a7-b8-h2-g1 и диагональ a1-h8. Каждому углу прямоугольника соответствует ход по этому прямоугольнику, после которого слон попал в этот угол. Значит, по каждому прямоугольнику сделано не меньше четырёх ходов.
Если первый и последний ход не принадлежит прямоугольнику, то:
обход начинается не с угла;
каждому углу соотв. ход;
плюс ещё ход чтобы можно было уйти с прямоугольника.Итого не меньше 5 ходов.
В противном случае можно обойтись 4 ходами.
Соответственно большая диагональ 3 и 2 хода.
Минимум ходов: 3+5+5+5-2(объекты, которым принадлежат первый и последний ходы)=16ходов, т.е. 15 поворотов.
Отредактировано СюгировФан (2009-09-01 23:17:15)
|
|
-
azur
-
-
OFFLINE
-
Бояринъ
-
- Posts: 239
- Thank you received: 1
-
Karma: 1
-
|
В общем правильно.
Мух же рассуждал примерно так:
Разделим все возможные повороты на внешние - на находящихся на краю доски полях a1, c1, e1, g1, h2, h4, h6, h8, f8, d8, b8, a7, a5, a3 (всего 14) - и на внутренние (не на краю доски). На внешних полях не будет поворотов только если в них начинается и заканчивается маршрут. Вопрос в том, как минимизировать количество внутренних поворотов.
А вот тут помогает представление доски в виде большой диагонали a1-h8 и прямоугольников c1-h6-f8-a3, e1-h4-d8-a5, g1-h2-b8-a7. Все возможные маршруты Муха принадлежат исключительно этим четырем фигурам. Очевидно, чтобы перейти от одной фигуры к другой необходим внутренний поворот. Всего таких поворотов минимум три (т.к. фигур - четыре).
Итого, если начинать и заканчивать маршрут на внешних полях, то минимум поворотов будет равен 14-2+3=15. При этом маршрут необходимо начинать (или заканчивать) из угла на большой диагонали, иначе поворотов будет больше.
Отредактировано azur (2009-09-02 03:45:21)
|
|
|
|
 |