• РЕГИСТРАЦИЯ

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

14 6981

В 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-страничные справочники со схемами. Тем не менее, математики до сих пор теряются в догадках, как определить, существует ли решение для конкретных заданных условий. Благодаря Кивашу мы узнали, что вероятность этого достаточно высока. Так что хотя бы теперь ясно, что при всех неизвестных лучше искать решение, чем отказываться от него. Тем более, существуют инструменты для генерации примерных схем для любых параметров.

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

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

источник

Учёный не политик, его не купишь

    Почему в Европе не едят гречку?

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

    "Послание Путина" услышали в Париже и Лондоне: Важнейшие учебные центры разнесло в щепки, офицеры убиты в первый же день

    Русская армия активно бьет по целям в тылах противника. На воздух взлетели склады, доверху забитые боеприпасами. Натовские инструкторы не успели сойти с поезда, как были уничтожены приц...

    Ваш комментарий сохранен и будет опубликован сразу после вашей авторизации.

    0 новых комментариев

      Neiro 30 марта 17:38

      Временный отказ от смартфона может омолодить мозг на 10 лет, доказали учёные

      Если отказаться от интернета на две недели, то можно добавить себе 10 лет жизни.   «Участники эксперимента установили приложение, ограничивающее доступ к мобильному интернету, то есть у испытуемых осталась возможность совершать звонки и отправлять SMS. По истечении этого срока все участники сообщили о повышении настроения, улучшении удовлетворённо...
      561
      Neiro 27 марта 10:39

      Клубника против деменции: учёные выяснили скрытую пользу популярной ягоды

      «Клубника улучшает работу мозга и здоровье сердца, но ее когнитивные преимущества остаются неясными»: Клубника три раза в неделю спасает от деменции.   «Регулярное употребление этой ягоды может не только поддерживать функции мозга, но и улучшать общее состояние организма благодаря воздействию на клеточные механизмы. Клубника положитель...
      427
      Neiro 23 марта 10:45

      Ученым впервые удалось создать лекарство от инсульта

      У пациентов, перенесших инсульт, появилась новая надежда на выздоровление, поскольку, по мнению исследователей, это самый первый препарат, который может обеспечить комплексную реабилитацию без необходимости в сложной длительной физиотерапии.    Ученые Калифорнийского университета совершили прорыв, сузив круг кандидатов в лекарственные препараты до ...
      475
      Neiro 22 марта 10:47

      Неизвестная форма жизни внутри мрамора и известняка

      В обширных и засушливых ландшафтах Намибии, Омана и Саудовской Аравии группа исследователей обнаружила ряд своеобразных структур в мраморных и известняковых образованиях, происхождение которых, похоже, не соответствует известным геологическим процессам. Это открытие, недавно опубликованное в специализированном журнале Geomicrobiology Journal, позволяет предположит...
      778
      Neiro 21 марта 16:51

      Госдума вводит маркировку звонков на экранах мобильных телефонов

      Госдума приняла в первом чтении проект о борьбе с телефонным и интернет-мошенничеством, согласно которому все звонки на экранах мобильных телефонов должны быть промаркированы. Gettyimages.ru Как сообщает ТАСС, юрлица должны будут бесплатно информировать абонента о себе перед звонком. При этом сам абонент сможет отказаться от них и пожаловаться оператор...
      741
      Neiro 20 марта 10:51

      В Британии будут вставлять мозговые имплантаты алкоголикам и наркоманам

      В мозг страдающих зависимостью от алкоголя и наркотиков начнут вживлять чипы в Британии. «Хирурги планируют провести эксперимент и вживить имплантаты в мозг алкоголиков и наркоманов, страдающих зависимостью. Цель эксперимента — проверить эффективность использования электрических импульсов для борьбы с тягой к алкоголю и наркотикам.   Эта ...
      183
      Neiro 19 марта 14:48

      Что происходит с мозгом во время гипноза?

      Гипнотизер говорит, что ваши веки тяжелеют, вы медленно засыпаете... Группа нейробиологов из Медицинской школы Стэнфордского университета выяснила, что происходит в мозге во время гипнотического транса. Ученые наблюдали работу мозга 57 добровольцев, когда те проходили сеанс управляемого гипноза по методике, которая используется в психотерапии для лечения тре...
      1033
      Neiro 13 марта 12:53

      Ученые нашли новые доказательства существования Ноева ковчега

      Ноев ковчег нашли? Курган в форме ковчега в Турции был под водой 5000 лет назад — в тот же период, что и библейский потоп. Подтвердить написанное в Библии остается заветной мечтой ученых — теперь они считают, что обнаружили ковчега времен глобальной катастрофы.   «Согласно Библии, Ноев ковчег спас человечество и всех животных от немину...
      835
      Neiro 13 марта 10:44

      Ученые обнаружили повседневную еду, которая может оказать существенное влияние на поведение подростков

      Ученые обнаружили повседневную еду, которая может оказать существенное влияние на поведение подростков: дети, которые едят мало рыбы, менее общительны и плохо учатся.   «Школьники, которые в возрасте 7 лет потребляли мало морепродуктов, имели меньше „просоциальных“ качеств в 7 и 9 лет по сравнению с теми, кто регулярно ел морепродукты....
      616
      Neiro 12 марта 12:39

      Ученые создали твердый и жидкий свет

      Мы привыкли к тому, что свет — это что-то неуловимое и нематериальное. Но физики утверждают, что это не так. Более того, недавно ученые обнаружили, что свет может вести себя одновременно и, как сверхтекучая жидкость и, как твердое тело.   Сочетание несочетаемого Сверхтвердые тела, как их называют физики, обладают нулевой вязкостью, что означает...
      736
      Neiro 9 марта 10:42

      Ученые проверили, одинаково ли люди воспринимают тот же цвет

      Видит ли один человек цвета именно так, как их видит другой, остается трудным вопросом для исследователей человеческого сознания. Это пытаются выяснить по косвенным признакам, например по тому, какие ассоциации вызывает у разных людей один и тот же цвет. Недавно ученые решили опробовать еще один подход к этой проблеме: определить, насколько схожи или различны те и...
      609
      Neiro 6 марта 10:50

      Ученые обнаружили белок, который обращает вспять старение клеток

      Человечество замахнулось на создание «молодильных яблок».   Группа исследователей из Университета Осаки в Японии освоила механизм обращения вспять процесса старения на клеточном уровне. Ученые объяснили, что с возрастом клетки организма постепенно становятся менее активными. Стареющие клетки не просто старше — они заметно крупнее. ...
      792
      Neiro 5 марта 12:58

      Слепому жителю Канады имплантировали в глаз зуб для восстановления зрения

      Жителю Канады провели операцию по восстановлению зрения путем пересадки его зуба в глазницу. Подобную необычную операцию на протяжении десятилетий проводят в других странах мира, для Канады она стала одной из первых в истории страны.   «Слепой канадец вскоре смог снова видеть благодаря удивительному источнику — своим зубам. Хотя это может по...
      1122
      Neiro 3 марта 14:03

      Парадокс Моравека

      Парадокс Моравека заключается вот в чем - почему для искусственного интеллекта элементарное оказывается самым сложным История технологий полна предсказаний, которые сейчас звучат смешно. Один из самых известных примеров приписывается Биллу Гейтсу, который в 1981 году заявил, что «640 килобайт должно хватить любому». Предсказания об искусственном ...
      643
      Neiro 26 февраля 10:49

      Ученые подтвердили существование аномального льда VII

      Международная группа исследователей сумела экспериментально подтвердить существование льда VII - редкой и экзотической формы, которая, как предполагается, может существовать в океанах на далеких экзопланетах. Ранее предположения о существовании этой экзотической формы воды высказывались исключительно теоретически. Теперь же материал был получен в лаборатории. ...
      800
      Neiro 22 февраля 16:47

      Инопланетная жизнь на основе серной кислоты: новая гипотеза ученых

      Недавнее исследование, проведенное группой специалистов из MIT, предлагает смелую идею: формы жизни, принципиально отличные от земных, могут использовать концентрированную серную кислоту так, как мы полагаемся на воду. Эта гипотеза кардинально меняет наше представление о необходимых условиях для возникновения жизни за пределами Земли. Альтернативный раствори...
      789
      Neiro 19 февраля 12:55

      Ученые вырастили человекоподобные зубы у свиней

      Потеря зуба у взрослого человека часто означает необходимость установки протезов или имплантатов, но исследователи из Университета Тафтса изучают новый вариант: выращенные в лаборатории зубы. На протяжении десятилетий варианты замены зубов ограничивались зубными протезами или титановыми имплантатами.   Эти решения часто дороги и чреваты осложнениями....
      571
      Neiro 16 февраля 10:55

      Хорошие новости к завтраку — ученые реабилитировали яйца

      Хорошие новости к завтраку — ученые реабилитировали яйца, употребление от 1 до 6 яиц в неделю снижает риск смерти.   «Изучив данные о здоровье и рационе участвующих в шестилетнем эксперименте австралийцев и американцев, ученые из Университета Монаша пришли к выводу, что у тех из них, кто еженедельно употребляли яйца, риск развития сердечно-с...
      675
      Neiro 12 февраля 12:48

      Странная трансформация внутреннего ядра Земли раскрыта

      Данные сейсмических волн свидетельствуют о необычных изменениях, происходящих вблизи внутреннего ядра Земли, утверждают учёные, обнаружившие свидетельства ранее неизвестных структурных преобразований, происходящих в глубинах планеты. Открытие, сделанное группой ученых из Университета Южной Калифорнии (USC), позволяет по-новому взглянуть на глубинные земные явления...
      1405
      Neiro 8 февраля 10:59

      В России может появиться химиотерапия, не вызывающая выпадения волос

      Ученые работают над снижением побочных эффектов от химиотерапии, в том числе выпадения волос, ведутся исследования, заявил РИА Новости генеральный директор НМИЦ радиологии, главный внештатный онколог Минздрава России Андрей Каприн.   «Да, такие исследования и работы ведутся постоянно. Химиотерапия, несмотря на свою эффективность в борьбе со злокач...
      289
      Служба поддержи

      Яндекс.Метрика