День 3. Проблема Борсука

На работе собрали дистрибутив и запустили автоматическую установку на первую партию школ. Завтра посмотрим результаты.

Когда на обед заходил домой отец сказал, что по радио сообщили об изменениях в законе о воинской службе: с этого призыва не разносят повестки, а каждый призывник сам обязан явиться за повесткой в двухнедельный срок, по истечении которого в случае неявки наступает административная, а затем и уголовная ответственность. Испугался. Перерыл гугл. Ничего такого не нашел. Подумал, что первоапрельская шутка, возможно. Нужно еще уточнить.

Решил тоже пошутить: казанским коллегам написал, что заказчик требует к пятнице реализовать возможность повышения оценок в электронном дневнике при отправке учеником платных СМС. Представителю заказчика написал ту же шутку: типа нужно позвонить школам и узнать, насколько критична для них данная доработка. Мы, дескать, работаем, но если очень нужно — можем и побыстрее работать. Казанцы сразу посмеялись, а вот заказчик юмор не оценил. Не надо так с заказчиком шутить. Особенно, если идет отставание от сроков проекта.

Продолжаю читать Расмуссона, но до гибкой команды нам далеко. Хотя зачатки (размытые границы между ролями и тесное взаимодействие с заказчиком) у нас есть. Я все ж буду настаивать на разделении ролей менеджера проекта и техлида: первый должен обеспечивать взаимодействие команды с заказчиком, ездить на совещания, болтать и отдуваться. А второй — добиваться поставленных целей, строить работу внутри команды и управлять проектной группой и группой внедрения. В некоторых компаниях (даже если смотреть вакансии) вторая должность (и роль) начисто отсутствует. Кто знает почему — напишите уж.

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

Начал читать книгу Канемана «Думай медленно, решай быстро», прочитал Райгородского «Проблема Борсука». О чем и хочу рассказать.

Речь пойдет об одной одной из наиболее известных, красивых и интригующих задач современной комбинаторной геометрии. Эта задача была предложена в 1933 году польским математиком Каролем Борсуком и за прошедшие 70 лет она стала едва ли не самой популярной в своей области. История проблемы Борсука носит весьма драматический и в чём-то почти детективный характер.

Задача формулируется следующим образом: Найти минимальное число частей меньшего диаметра, на которые может быть разбито произвольное ограниченное множество в пространстве.

Более строго: пусть А — некоторое ограниченное множество из R^n. Представим А в виде объединения множеств А_1, А_2, ..., А_m меньшего диаметра. Обозначим через f(A) минимум среди m, для которых такое представление имеет место. Определим f(n) как максимум f(A) по всем A из R^n.

Равенство f(1)=2 очевидно, f(2)=3 доказывается просто и было получено самим Борсуком, равенство f(3)=4 отнюдь не очевидно (прочитайте доказательство!) Когда Борсук ставил свою проблему в 1933 году, он был осторожен, но всё же задал вопрос: правда ли, что f(n)=n+1? Гипотезу он не формулировал. Однако верить в положительный ответ на вопрос Борсука было столь заманчиво, что очень скоро все стали говорить о «гипотезе Борсука», и сам её «автор» от этого уже не открещивался.
История гипотезы Борсука весьма драматична. Все, кто занимался проблемой (а в рядах этих людей были замечательные математики), практически не сомневались в справедливости гипотезы, и потому огромные усилия были направлены на её подтверждение. Разумеется, многочисленные нетривиальные результаты не замедлили появиться.

Нетрудно найти доказательство нижней оценки f(n) >= n+1. А вот с верхней оценкой дела обстояли хуже. Понятно, что в идеале должно было получиться f(n) <= n+1, однако до такой правой части было как до Луны.

Первую из оценок, а именно f(n) <= 2^n можно получить из теоремы Юнга (1901 г.): всякое множество диаметра 1 в R^n покрывается шаром радиуса sqrt (n / (2n + 2)).

Наилучшей из явных оценок является оценка, полученная М. Лассаком в 1982 г.: f(n) <= 2^(n-1) + 1.

Что с неявными оценками? В 1965 г. было показано, что f(n) <= (sqrt(2) + o(1))^n (К. Роджерс), в 1988 г. О. Шрамму удалось установить, что f(n) <= (sqrt(3/2) + o(1))^n. Его результат остается непревзойденным и по сей день. Пользуясь совершенно другими средствами, в 1991 году его безуспешно пытались улучшить и смогли лишь передоказать Ж.Бургейн и Й.Линденштраусс. 

Развязка нашей драмы наступила в 1993 году, ровно через 60 лет после того, как проблема Борсука была поставлена. Дж.Кан и Г.Калаи сумели построить контрпример к гипотезе! Для многих это стало абсолютной неожиданностью. Однако и результат Кана—Калаи выглядел в некотором роде угрожающе: контрпримеры возникали лишь во всех размерностях, начиная с n = 2015.

Неудобоваримое число. Что такое 2015 измерений, помыслить нереально. В то же время и нижняя оценка на f(n), которую заодно с контрпримерами предложили Кан и Калаи, оказалась весьма любопытной. Теперь речь уже не шла ни о каком n+1; выяснилось, что всё гораздо хитрее и что по крайней мере f(n) >= (1.203 + o(1))^(sqrt(n)).

На сегодня все. Интересных задач и содержательных результатов!

 

Обсудить у себя 0
Комментарии (0)
Чтобы комментировать надо зарегистрироваться или если вы уже регистрировались войти в свой аккаунт.

Войти через социальные сети:

sakharov_denis
sakharov_denis
Было на сайте никогда
Читателей: 6 Опыт: 0 Карма: 1
все 5 Мои друзья