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

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

14 6988

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

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

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

источник

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

    Что ж ты, джентльмен, сдал назад?

    Так вот почему британцы вдруг резко расхотели  отправлять наземные войска на Украину? The Times приводит сегодня слова коммодора авиации Блайта Кроуфорда, который до прошлой недели...

    Попову дали пять лет. На СВО? "Нет вакансий!" А он журналистам: "Спасибо, ребята"
    • Beria
    • Вчера 10:49
    • В топе

    Тамбовский гарнизонный суд дал генералу Ивану Попову 5 лет. С отбыванием в колонии общего режима. А ещё, по решению суда, экс-командарм должен выплатить штраф в 800 тысяч рублей. В этом деле, к...

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

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

      Neiro 23 апреля 12:40

      Полет на Марс грозит космонавтам слабоумием

      Мы уже выясняли к чему приведет Размножение в космосе и вообще Чего нельзя сделать в космосе, но оказывается это еще не все. Наши радужные мечты о покорении далеки планет или даже уже банальный и давно планируемый полет к Марсу достаточно опасен. Известно, что наша физиология не приспособлена для жизни в отсутствие гравитации. Мышцы тела, включая...
      783
      Neiro 20 апреля 19:41

      Почему многие физики уверены, что наша Вселенная — это голографическая иллюзия

      Природа и происхождение нашей Вселенной является предметом бесконечных споров и самых разнообразных теорий. В последнее время в среде учёных-физиков появилась новая основа для понимания космоса. Они считают, что вся Вселенная, включая нашу планету, а также всю жизнь на Земле, на самом деле является сложной голографической иллюзией. На чём основана эта радикальн...
      1499
      Neiro 20 апреля 17:35

      Ученые пытаются разгадать загадку «молочных морей» — таинственного свечения океана

      В январе 1967 года во время плавания судна SS Ixion по Аравийскому морю команда корабля наблюдала настолько странное явление, что оно показалось им чем-то из области научной фантастики: насколько хватало глаз, окружающий океан излучал жуткое молочное свечение. «Море от горизонта до горизонта во всех направлениях приобрело фосфоресцирующее свечение, не ярк...
      454
      Neiro 19 апреля 13:48

      Ученые вырастили куриное мясо в лаборатории

      Исследователи из Токийского университета совершили прорыв в создании искусственного мяса, разработав биореактор, имитирующий кровеносную систему. Это позволило вырастить реалистичные куриные мышцы без использования традиционного животноводства. Новая система, описанная в журнале Trends in Biotechnology, произвела более 10 граммов структурированного куриного мяс...
      281
      Neiro 18 апреля 16:50

      В Америке аутизм уничтожает детей

      Доктор биологических наук Анча Баранова - о резком росте числа случаев аутизма среди детей в США: Новая статистика вышла, которую давно ждали. Частота случаев диагностики заболеваний аутистического спектра в США возросла до 1 на 31 для восьмилетних детей. В 2016 году аутизм был диагностирован у 1 из 54 из 8-летних детей. В 2000 году это был всего лишь 1 с...
      573
      Neiro 17 апреля 16:47

      Ученые обнаружили неизвестную форму жизни глубоко под Землей

      Группа исследователей под руководством микробиолога Джеймса Тидже из Университета штата Мичиган открыла новый тип микроорганизмов в пределах Критической зоны Земли — тонкого поверхностного слоя планеты, простирающегося от вершин деревьев до коренных пород. Находка проливает свет на ранее неизученные формы жизни, скрытые глубоко под почвой. Обнаруженные...
      666
      Neiro 17 апреля 16:36

      Ученые нашли область мозга, отвечающую за логику

      Новое исследование нейропсихологов поможет лучше понять, какая часть мозга позволяет нам рассуждать и принимать правильные решения. За принятие решений, организацию действий, планирование, контроль, речь, письмо и другие сложные, жизненно необходимые функции отвечает в целом вся лобная доля мозга, состоящая из нескольких зон. Поэтому лоботомия (иссечение этой о...
      438
      Neiro 16 апреля 11:05

      В недрах Земли обнаружены существа весом 20 миллиардов тонн

      Согласно результатам исследований, они скрываются в нескольких километрах от поверхности планеты.   Группа ученых из 52 стран обнаружила в недрах Земли существ, которые могут достигать в весе 20 миллиардов тонн. Они скрываются в нескольких километрах от поверхности планеты, пишет «Вечерняя Москва». Сообщается, что ученые нашли микробы,...
      1869
      Neiro 6 апреля 10:34

      Парализованная женщина вернула свой голос с помощью нейропротеза

      Потерявшей способность говорить женщине вернули способность общаться после 18 лет молчания. «Американские ученые разработали устройство, которое вернуло способность общаться женщине, которая почти 20 лет назад перенесла инсульт. Их изобретение расшифровывает мысли в режиме реального времени и преобразует их в синтезированную речь.   Ученые Кали...
      238
      Neiro 2 апреля 12:40

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

      Хотя выражение «это случайно» часто используется для описания непредсказуемых ситуаций, истинная случайность, как в физике, так и в математике, долгое время оставалась неуловимым понятием. Однако группа исследователей в области квантовых вычислений только что сделала важный шаг: впервые они сгенерировали число, которое признано фундаментально случайным...
      828
      Neiro 30 марта 17:38

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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