Равенство решек
В тёмной‑тёмной (вот вообще ни зги не видать, и свет включить нельзя) комнате стоит стол, на котором лежат 50 монет. Вы их не видите, но можете пощупать, перевернуть. И главное, точно знаете: 40 монет изначально лежат орлом вверх, а 10 — решкой.
Ваша задача — разделить деньги на две группы (не обязательно равные), в каждой из которых будет одинаковое количество монеток решкой вверх.
Посмотреть ответ
Скрыть
Разделите монеты на две группы: в одной 40, в другой 10. Теперь переверните все деньги из второй группы. Вуаля, можно включать свет: задача выполнена. Не верите — проверьте.
Для буквоедов‑математиков поясним алгоритм. После слепого разделения на две группы случилось вот что: в первой осталось х решек; а во второй, соответственно, — (10 − х) решек (ведь суммарно по условиям задачи решек 10). А орлов, таким образом, — 10 − (10 − х) = х. То есть количество орлов во второй группе равно количеству решек в первой.
Делаем простейший шаг — переворачиваем все монетки во второй кучке. Таким образом все монетки‑орлы (х штук) становятся монетками‑решками, а их количество оказывается тем же, что и количество решек в первой группе.
Проблема перебора
Фото: Reuters / Thomas Peter
Вопрос короткий: равны ли классы сложности P и NP?
Классом P называют множество задач, которые компьютер может решить «быстро» (то есть за полиномиальное время). К ним относят базовые арифметические действия, сортировку списков, поиск по таблице с данными.
Класс NP — это задачи, правильность ответа на которые можно быстро проверить. Например, задача о сумме. Предположим, что у вас есть монеты номиналом 2, 3, 5, 6 и 7 рублей, по одной каждого номинала, и вы хотите без сдачи оплатить покупку стоимостью 21 рубль. Можно ли набрать из данных монет сумму, равную 21?
В этой задаче для получения ответа нужно перебрать разные варианты, а чтобы доказать, что решения нет, — вообще перебрать все возможные варианты. Если количество монет увеличить на несколько порядков, решение выглядит совсем непрактичным. При этом результат проверить легко — просто сложить номиналы всех монет.
Суть «задачи тысячелетия» формулируется так: равны ли классы P и NP? Если легко проверить правильность решения задачи, может ли быть так же легко решить эту задачу? Большинство специалистов уверены, что ответ отрицательный. Однако доказать этого пока никто не смог. Если же вдруг окажется, что P = NP, то человечество ждет переворот в криптографии.
Гипотеза Бёрча — Свиннертон-Дайера
Фото: Reuters
Математики всегда интересовались проблемой описания всех решений в целых числах x, y, z алгебраических уравнений. Пример такого уравнения — x2 + y2 = z2. Его целые решения уже описал Евклид, однако для более сложных уравнений это может быть чрезвычайно сложным.
Доказано, что у людей нет способа определить, в каких случаях такие уравнения имеют решения в целых числах, а в каких — нет. Например, у уравнения xn + yn = zn точно нет целых решений при n > 2. Это Великая теорема Ферма, на ее доказательство у математиков ушло больше 300 лет.
Однако в частном случае — когда решения образуют абелево многообразие, Брайан Бёрч и Питер Свиннертон-Дайер предположили, что число решений определяется значением связанной с уравнением дзета-функции в точке 1. Если значение дзета-функции в точке 1 равно 0, то имеется бесконечное число решений, и наоборот, если не равно 0, то имеется только конечное число таких решений.
Гипотеза Ходжа
Формулировка этой гипотезы выглядит так: «На любом невырожденном проективном комплексном алгебраическом многообразии любой класс Ходжа представляет собой рациональную линейную комбинацию классов алгебраических циклов». Нужно доказать или опровергнуть это утверждение.
О чем речь? Решения уравнения у = Зх + 1 можно представить на координатной сетке как прямую. Корни квадратного уравнения дадут нам параболу. Усложнять можно бесконечно — например, поверхности с таким уравнением
соответствует этот график:
Изображение: Claudio Rocchini / wikipedia.org
Математики не ограничивают себя тремя измерениями. К примеру, в четырехмерном пространстве у объекта будет четыре координаты (х, у, z, w). Измерений может быть сколько угодно, число уравнений и переменных тоже может быть любым (не пытайтесь это представить). К тому же переменные могут быть комплексными и принимать бесконечные значения разумным образом.
Гипотеза Ходжа говорит о глубокой связи между топологией, алгеброй, геометрией и анализом. Она предлагает добавить в инструментарий специалиста по алгебраической геометрии два новых инструмента: топологические инварианты и уравнение Лапласа. Если гипотеза верна, эти инструменты обретут новое значение и станут потенциальным средством поиска ответов на множество вопросов.
Задача об испорченных таблетках
На столе стоят пять баночек с таблетками. В одной из них все таблетки испорчены. Определить это можно только по весу. Обычная пилюля весит 10 граммов, а испорченная — 9 граммов. Как узнать, в какой баночке лежат испорченные таблетки? Можно воспользоваться весами, но только один раз.
Показать ответ
Скрыть ответ
Шанс, что при первом замере нам сразу же попадётся та самая испорченная таблетка, равен одному из пяти. Значит, нужно одновременно взвешивать пилюли из нескольких баночек. Если взять по одной таблетке из каждой банки и положить их все на весы, получится такая сумма: 10 + 10 + 10 + 10 + 9 = 49 граммов. Но это понятно и без взвешивания. Таким способом невозможно узнать, в какой именно из банок находится испорченная пилюля.
Нужно действовать иначе. Сначала присвоим каждой баночке порядковый номер от одного до пяти. Затем положим на весы одну таблетку из первой банки, две из второй банки, три из третьей, четыре из четвёртой, пять из пятой. Если бы все таблетки были нормального веса, результат получился бы такой: 10 + 20 + 30 + 40 + 50 = 150 граммов. Но в нашем случае вес будет меньше как раз на то количество граммов, которое соответствует номеру баночки с испорченными таблетками.
Например, у нас получился вес 146 граммов. 150 − 146 = 4 грамма. Значит, испорченные таблетки лежат в четвёртой банке. Если вес 147 граммов, то испорченные таблетки в третьей банке.
Есть и другой вариант решения. Взвешиваем одну таблетку из первой банки, две из второй, три из третьей, четыре из четвёртой. Если вес меньше 100 граммов, то количество недостающих граммов укажет на бракованную упаковку. Если вес ровно 100 граммов, то испорченные пилюли находятся в пятой баночке.
Оригинал задачи можно посмотреть здесь.
Как не выйти замуж
Однажды хозяин мелкой лавки в Италии задолжал ростовщику крупную сумму. Возможности отдать долг у него не было. Зато была красавица‑дочь, которая давно нравилась кредитору.
Но девушка не хотела выходить замуж за старого и некрасивого мужчину. Поэтому лавочник ответил отказом. Однако потенциальный зять уловил в его голосе колебание и сделал новое предложение.
Сделка выглядела справедливой, и на этот раз отец согласился. Ростовщик наклонился к дорожке, усыпанной галькой, быстро поднял камни и положил их в мешочек. Но дочь заметила ужасное: оба камушка были чёрными! Какой бы она ни вытащила, ей пришлось бы выходить замуж. Конечно, можно было уличить ростовщика в обмане, вынув сразу оба камня. Но тот мог бы прийти в ярость и отменить сделку, затребовав долг в полном объёме.
Подумав пару секунд, девушка уверенно протянула руку к мешочку. И сделала кое‑что, что избавило её отца от долга, а её саму — от необходимости замужества. Справедливость её поступка признал даже ростовщик. Что именно она сделала?
Посмотреть ответ
Скрыть
Девушка вытащила камень и, не успев показать никому, будто случайно уронила его на дорожку. Камушек тут же смешался с остальной галькой.
Конечно же, когда все заглянули в мешок, там обнаружился чёрный камень. Даже ростовщик был вынужден согласиться: это означает, что девушка вытащила белый. А раз так — свадьбы не будет и долг придётся простить.
Уравнения Навье — Стокса
Фото: Дмитрий Брушко, TUT.BY
Уравнения Навье — Стокса описывают, как потоки жидкости или газа ведут себя при определенных условиях. Их применяют в метеорологии, в конструировании самолетов, при расчете аэродинамики автомобилей. Однако в аналитическом виде решения этих уравнений найдены лишь в некоторых частных случаях.
Часть уравнений Навье-Стокса для несжимаемой жидкости
«Задача тысячелетия» не требует найти явные решения уравнения. Вопрос такой: если известно состояние жидкости в определенный момент времени и характеристики ее движения — существует ли решение, которое будет верно для всего будущего времени?
Чтобы получить премию, достаточно доказать или опровергнуть существование и гладкость решения в любом из двух вариантов, предложенных институтом Клэя. Возможно, ответ на вопрос позволит метеорологам наконец делать точные долгосрочные прогнозы.
У вас код запутался…
Вы закрыли чемодан на цифровой замок с трёхзначным кодом и случайно забыли цифры. Но память предлагает вам следующие подсказки:
- 682 — в этом коде одна из цифр верна и стоит на своём месте;
- 614 — одна из цифр правильная, но стоит не на своём месте;
- 206 — верны две цифры, но обе стоят не на своих местах;
- 738 — вообще чепуха, ни одного попадания;
- 870 — одна цифра верная, но не на своём месте.
Этой информации хватает, чтобы подобрать правильный код. Какой он?
Посмотреть ответ
Скрыть
042.
Следуя четвёртой подсказке, вычеркиваем из всех комбинаций цифры 7, 3 и 8 — их в искомом коде точно нет. Из первой подсказки выясняем, что своё место занимает либо 6, либо 2. Но если это 6, то не выполняется условие второй подсказки, где 6 стоит в начале. Значит, последняя цифра кода — 2. А 6 в шифре вообще отсутствует.
Из третьей подсказки делаем вывод, что правильные цифры кода — 2 и 0. При этом 2 стоит на последнем месте. А значит, 0 — на первом. Таким образом, нам становятся известны первая и третья цифры кода: 0…2.
Сверяемся со второй подсказкой. Цифру 6 отмели ранее. Единица не подходит: известно, что она стоит не на своём месте, однако все возможные места для неё — первое и последнее — уже заняты. Таким образом, верна только цифра 4. Её и двигаем в середину полученного кода — 042.
День рождения Шерил
Предположим, некие Бернард и Альберт недавно познакомились с девушкой Шерил. Они хотят узнать, когда у неё день рождения — чтобы приготовить подарки. Но Шерил та ещё штучка. Вместо ответа она вручает парням список из 10 возможных дат:
| 15 мая | 16 мая | 19 мая |
| 17 июня | 18 июня | |
| 14 июля | 16 июля | |
| 14 августа | 15 августа | 17 августа |
Предсказуемо обнаружив, что юноши не могут вычислить правильную дату, Шерил шёпотом, на ухо, называет Альберту только месяц её рождения. А Бернарду — также тихо — лишь число.
И они хором называют верную дату. Когда же у Шерил день рождения?
Если у вас не получается с ходу найти ответ, не расстраивайтесь. Впервые этот вопрос прозвучал на подростковой математической олимпиаде в Сингапуре Singapore and Asian School Math Olympiad , который славится высочайшими образовательными стандартами. После того как один из местных телеведущих опубликовал скрин этой задачки в Facebook, она стала вирусной When is Cheryl’s birthday?’ The tricky maths problem that has everyone stumped : решить её пытались десятки тысяч пользователей Facebook, Twitter, Reddit. Но справились не все.
Мы уверены, что у вас получится. Не открывайте отгадку, пока хотя бы не попробуете.
Посмотреть ответ
Скрыть
16 июля. Это следует из диалога, состоявшегося между Альбертом и Бернардом. Плюс немножечко метода исключений. Смотрите.
Если Шерил родилась в мае или июне, значит, её днём рождения может быть 19‑е или 18‑е. Эти числа встречаются в списке лишь по одному разу. Соответственно, Бернард, услышав их, сразу смог бы понять, о каком месяце идёт речь. Но Альберт, как следует из его первой реплики, уверен, что Бернард, зная число, совершенно точно не сможет назвать месяц. Значит, речь идёт не о мае или июне. Шерил родилась в месяце, каждая из названных дат в котором имеет дубль в соседних месяцах. То есть — в июле или августе.
Бернард, которому известно число рождения, услышав и проанализировав реплику Альберта (то есть выяснив про июль или август), сообщает, что теперь знает правильный ответ. Из этого следует, что известное Бернарду число — не 14, ведь оно дублируется и в июле, и в августе, так что определить верную дату нельзя. Но Бернард уверен в своём решении. Значит, известное ему число не имеет дублей в июле и августе. Под это условие попадают три варианта: 16 июля, 15 августа и 17 августа.
В свою очередь Альберт, услышав слова Бернарда (и логически дойдя до трёх вышеназванных возможных дат), заявляет, что теперь тоже знает правильную дату. Мы помним, что Альберту известен месяц. Если бы этим месяцем был август, юноша не смог бы определить число — ведь в августе фигурируют сразу два. Значит, остаётся лишь один возможный вариант — 16 июля.
Массовая щель
Изображение: nnm.me
Математическая теория Янга-Миллса объединяет электромагнитное, сильное и слабое взаимодействие на основе более общей математической теории, связанной с калибровочной симметрией. На основе этих уравнений есть гипотеза о так называемой массовой щели.
В теории относительности частица, которая имеет ненулевую массу покоя, не может двигаться со скоростью света. «Щель» в спектре масс позволяет квантовым частицам иметь конечную ненулевую массу, несмотря на то что связанные с ними классические волны движутся со скоростью света.
Эксперименты подтверждают существование массовой щели. Однако этой теории необходимо теоретическое обоснование.
Любовь в Клептопии
Ян и Мария полюбили друг друга, общаясь только через интернет. Ян хочет отправить Марии обручальное кольцо по почте — чтобы сделать предложение. Но вот беда: возлюбленные живут в стране Клептопии, где любая посылка, передаваемая по почте, обязательно будет украдена — если только её не заключить в ящик с замком.
У Яна и Марии много замков, но отправить друг другу ключи они не могут — ведь ключи тоже будут украдены. Как Яну отправить кольцо, чтобы оно наверняка попало Марии в руки?
Посмотреть ответ
Скрыть
Ян должен отправить Марии кольцо в запертой на замок коробке. Без ключа, естественно. Мария, получив посылку, должна врезать в неё собственный замок.
Затем коробка снова отправляется Яну. Тот открывает свой замок собственным ключом и вновь адресует посылку с единственным оставшимся запертым замком Марии. А у девушки есть к нему ключ.
Кстати, эта задачка — не просто теоретическая игра на логику. Использованная в ней идея — фундаментальная Seven Puzzles You Think You Must Not Have Heard Correctly в криптографическом принципе обмена ключами по протоколу Диффи — Хеллмана. Этот протокол позволяет двум и более сторонам получить общий секретный ключ, используя незащищенный от прослушивания канал связи.
