Задачка 165-летней давности не даёт покоя математикам



    В 1850 году преподобный Томас Киркман, британский математик и настоятель прихода в Ланкашире, сформулировал невинно выглядящую головоломку в развлекательном журнале для любителей математики «Записная книжка леди и джентльменов»:

    «Пятнадцать юных школьниц выходят на прогулку семь дней рядами по трое: нужно каждый день располагать их так, чтобы одна и та же пара школьниц никогда не встречалась дважды в одном ряду».

    Задачка выглядит простой, но если попробовать её решить, то сразу понимаешь, что это не так. Можете попробовать решить её с карандашом и бумагой или сыграть в HTML-версию.

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

    В результате, эта головоломка помогла сформировать новое направление математики: комбинаторные схемы, которому сейчас посвящены толстые учебники. Что началось как простая задачка по распределению людей по группам (или схемам, как в итоге их назвали), теперь стало методом, который применяется в экспериментальном дизайне, кодах коррекции ошибок в информатике, криптографии, сельском хозяйстве, спорте и даже в мошенничествах с азартными играми (была история, когда преступный картель заработал миллионы долларов за семь лет, скупая билеты со всеми возможными комбинациями 5 из 46 в лотерее 6 из 46, если стоимость билетов была ниже, чем дополнительные бонусы за выигрыш 5 из 46 плюс вероятность выигрыша джекпота).

    Например, классический код Хамминга для коррекции ошибок использует решение задачи про школьниц (создание групп из трёх школьниц, где ни одна пара не повторяется), но только для схемы из семи девушек (бит).


    Плоскость Фано для (7, 3, 2)

    Удивительнее всего, что за 165 лет математики так и не смогли решить задачу в общем виде. Они так и не могут дать ответ, каково решение у головоломки при начальных условиях: есть n школьниц, нужно создать группы размером k, так что наборы из t девушек никогда не встречались дважды в одной группе. Такая формулировка называется схемой (n, k, t).

    Например, для группы из 19 девушек существует более 11 миллиардов возможных триплетов, в которых каждая пара встречается только однажды. Это число и является ответом. Но количество вариантов растёт экспоненциально при увеличении количества школьниц.

    Понятно, что задача решается при некоторых условиях и не решается при некоторых других. Например, если из шести школьниц составить триплеты из всех возможных пар, то задача очевидно не решается (со школьницей Аней существует пять возможных пар, в то же время в каждом триплете есть две пары с Аней, а пять не делится на два). То есть по принципу делимости сразу отсеивается много вариантов (n, k, t).

    В то же время есть (n, k, t), которые вполне соответствуют принципу делимости, но всё равно не имеют решения: например, (47, 3, 2).

    За минувшие годы решение стало известно для многих сочетаний (n, k, t), которые были проверены алгебраически или перебором на компьютерах. Но как решить это в общем виде, что делать с исключениями типа (47, 3, 2)? Как понять, имеет задача решение или нет?

    Эта задача долгое время считалась одной из самых знаменитых проблем в комбинаторике, говорит математик Джил Калай (Gil Kalai) из Еврейского университета в Иерусалиме в интервью Wired. Он вспоминает, как спорил по этому поводу с коллегами полтора года назад, и они пришли к выводу, что «мы никогда не узнаем ответ, потому что задача явно слишком сложная».

    Однако всего через две недели юный профессор математики Питер Киваш (Peter Keevash) из Оксфорда доказал, что Калай не прав. В научной статье от января 2014 года он доказывает, что решение задачи почти всегда существует, если выполняется условие делимости. В новой работе от апреля 2015 года он показал, как подсчитать примерное количество решений для заданных параметров.

    Никто не ожидал, что к решению задачи можно применить теорию вероятности, но метод отлично сработал.

    Возвращаясь к лотереям, мошенники поняли, что можно сократить количество покупаемых билетов, если скупить все комбинации 5 из 46 (при указании 6 из 46 чисел), тогда они получат абсолютно все дополнительные призы, а могут ещё получить и джекпот. Хотя схема (46, 6, 5) пока не рассчитана, но есть схемы, достаточно близкие для практического применения. Одну из них, вероятно, использовал преступный картель.

    Количество новых рассчитанных схем постоянно растёт. Многие из них находят практическое применение, как (15, 3, 2) из классической задачи, и (46, 6, 5). Выходят 1000-страничные справочники со схемами. Тем не менее, математики до сих пор теряются в догадках, как определить, существует ли решение для конкретных заданных условий. Благодаря Кивашу мы узнали, что вероятность этого достаточно высока. Так что хотя бы теперь ясно, что при всех неизвестных лучше искать решение, чем отказываться от него. Тем более, существуют инструменты для генерации примерных схем для любых параметров.

    Но благодаря работам Киваша появилась надежда, что можно разработать метод для создания точных схем для любых параметров. Если это произойдёт, то станет экстраординарным прорывом в математике.

    Впрочем, работа Киваша чисто теоретическая. Специалисты говорят, что создание практических алгоритмов на основе его метода потребует упорного труда ещё нескольких поколений математиков.
    AdBlock has stolen the banner, but banners are not teeth — they will be back

    More
    Ads

    Comments 11

      +29
      Если решу создать преступный картель, обязательно найму математика.
        0
        Так задача решается для (7, 3, 2) или нет? И можете подсказать другие параметры, для которых она решается?
          0
          В статье схема Фано и есть решение этой задачи. Точки это возможные тройки, линии — школьницы
          0
          не то? rghost.net/private/7jx5gH9cn/f6e319ac03574075b5a44d240535d486/image.png
            +3
            А какой закон нарушили те, кто скупал билеты? Запрещено покупать более 1 билета на человека что ли?
              0
              Наверное, деньги отмывали (и им можно было с отрицательным ожидаемым выигрышем работать — как у подавляющего большинства лотерей). Но регулярно слышу и о вполне легальных фин.организациях ищущих арбитраж на глобальном лотерейном рынке (если джек поты накопленные такие, что ожидаемый выигрышь больше 0 (- стоимость билета)
              +3
              Итого статья в двух словах: до пары человек наконец-то дошло, что теорвер применим к комбинаторике!
                +5
                На самом деле даже как-то это странно, что так долго доходило.
                Комбинаторика и теорвер — это практически две стороны одной медали. Многие задачи в комбинаторике поддаются оценке через теорвер. И если грамотно применять теорию вероятности, то можно ее очень эффективно использовать в комбинаторике и, вообще, в дискретной математике.
                0
                В веб версии: I completed the nine schoolgirls problem in 129.7 seconds!
                  0
                  84.4. На бумаге было бы гораздо дольше.
                  0
                  А куда из формулировки общего случая делось количество дней?

                  Я так понимаю, исходная задача представляет из себя случай 15, 3, 2?

                  И где можно посмотреть уже известные результаты для разных триплетов?

                  Only users with full accounts can post comments. Log in, please.