?

Log in

No account? Create an account
ТОЧНАЯ ФОРМУЛИРОВКА ЗАДАЧИ ! - ЗА ВЕРУ, ЦАРЯ И ОТЕЧЕСТВО [entries|archive|friends|userinfo]
ЗА ВЕРУ, ЦАРЯ И ОТЕЧЕСТВО

[ website | Савватеев ]
[ userinfo | livejournal userinfo ]
[ archive | journal archive ]

ТОЧНАЯ ФОРМУЛИРОВКА ЗАДАЧИ ! [Nov. 19th, 2007|04:51 pm]
ЗА ВЕРУ, ЦАРЯ И ОТЕЧЕСТВО
Рассмотрим пространство R^n. Каждому разбиению
этого пространства на (почти нигде) не пересекающиеся
ограниченные куски конечной положительной меры
можно сопоставить некоторое число.



Сейчас я опишу, что это за число. Сразу просьба -
не придирайтесь к мелочам типа "границы между
кусками могут быть сколько угодно плохими" и т.п. -
в ответе заведомо получится разбиение на
многогранные множества.

Расселяем школьников равномерно по всему пространству.
Считаем, что каждый кусок пространства задаёт школьный
district, то есть все школьники из этого куска будут ходить
в одну и ту же школу. Школу строят там, где суммарное
число школьнико-километров наименьшее (как обычно).
В многомерной ситуации положение школы определяется
этим требованием ОДНОЗНАЧНО (в отличие от прямой).

Теперь каждому куску сопоставляется число (1+суммарное
число школьнико-километров) разделить на (мера куска, то
есть количество школьников в district). Здесь под 1 понимается
(нормализованная) стоимость построения и содержания школы.

Можно сопоставить любому большому числу кусков такое
же число, то есть (число кусков + сумма суммарных чисел
школьнико-километров во всех кусках)/(суммарная мера
кусков). Говоря проще, это - средние издержки посещения
школы одним учеником.

В нормальных ситуациях можно перейти к пределу, сопоставив
в результате это число - средние издержки посещения школы
одним учеником - данному разбиению пространства на куски.

Теперь задача выглядит так: какое разбиение пространства
на куски является наиболее экономным с точки зрения обучения
школьников, равномерно населяющих пространство?

На плоскости это - шестиугольная сетка (доказано). Уже
в пространстве - я не в курсе, чтобы эта задача была решена -
то есть, среди экономистов, кажется, ответ неизвестен. А среди
математиков? Может, известен?

Конфликт в данной задаче состоит в том, что оптимальная
форма ОДНОГО district'а - конечно, шар нужного размера.
Но шарами пространство не замостишь! Отсюда берётся
живой интерес экономистов к этой задаче - ядро пустое!
А это всегда интересно.
linkReply

Comments:
[User Picture]From: mi_b
2007-11-19 10:27 pm (UTC)
похожие задачки математики решают давно, см упаковки шаров, kissing numbers итп. на вид, эта штука на них похожа, если взять разбиение на многогранники Делоне для упаковки шаров.

про упаковки известно следующее: в больших размерностях нерешетчатые упаковки строить очень трудно. те решетчатые или вроде, что удается построить, не просто сильно хуже верхней границы, но и сильно хуже неконструктивной нижней границы (!). неконструктивные нижние границы (по типу Минковского-Хлавки) строят через конструкции, эквивалентные преобразованию Радона в подходящем двойственном однородном пространстве.

стандартная книжка про решетки и упаковки - Конвей-Слоэн. ссылки по все этим словам можешь посмотреть, скажем, здесь

(Reply) (Thread)