Задача о восьмистах красках

Эта интересная топологическая задача о раскраске привлекает внимание логиков всего мира с начала семидесятых годов прошлого века. Известная как “теорема о раскраске карты в восемьсот цветов”, она звучит так: “Можно ли разбить карту Европы на государства и раскрасить их в восемьсот цветов так, чтобы каждое государство было покрашено в свой цвет и никакие два соседние государства не были покрашены в один цвет?”

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

В 1974 г. Мартин Рендраг, коллега профессора Николя Бурбаки, предложил блестящий метод нумерации цветов, который позволил переформлировать проблему, так что получилось нечто вроде этого: “Можно ли разбить карту Европы на государства и перенумеровать их числами от единицы до восьмисот так, чтобы каждое государство имело свой номер и никакие два соседние государства не имели одинаковых номеров?” Эта новая формулировка не дает ничего нового, она только позволяет оттянуть время начала раскрашивания карты, следовательно, она не устраняет трудности подбора цветов. Однако она может служить прекрасной отправной точкой для поиска рационального ответа на вопрос.

Тем не менее, ни одному математику не удавалось решить проблему с помощью карандаша и бумаги до тех пор, пока в 1979 г. команда, возглавляемая доктором Гёте из МТИ, не получила частичное решение, основанное на переформулировке Рендрага: программируя машину отеля Touring Club Конечных Штатов, доктор Гёте разделил карту Европы на восемьсот государств так, чтобы выполнялись логические ограничения задачи. Для получения данного результата необходимо было посчитать независимыми государствами все французские регионы, швейцарские кантоны, итальянские провинции, включая Изернии и Ористано, а также некоторые испанские области, такие как Ла-Манча и Пенедес, а также Фарерские острова, Кабреру и Лампедузу. Читать полностью ‘Задача о восьмистах красках’ »

Человек, который познал бесконечность

“Я вижу.”

(С. Рамануджан)

Это фильм о замечательном индийском математике Рамануджане, прожившем короткую жизнь, полную удивительных математических открытий. Сриниваса Рамануджан родился и жил в Индии, математике учился самостоятельно. В Мадрасе молодой человек пытается найти работу, предлагая посмотреть тетрадь с записями по математике, которые он сделал. Однако на работу его никто не берет, предлагают лишь рекомендации. И они с женой живут очень бедно. В конце концов он устраивается в бухгалтерскую контору, однако с одним условием: он должен научить математике шефа, объяснить то, что написано в его тетрадях. И Рамануджан объясняет. Возникает идея опубликовать то, что получил Рамануджан. И вот уже написано письмо в Кембридж, английскому математику Годфри Харди, который заинтересовался результатами никому не известного индуса. После переписки Сриниваса Рамануджан приезжает в Англию, где вместе с Харди они получают новые красивые формулы…

Рамануджану трудно в Англии. Он индус, он отличается от окружающих не только цветом кожи. Он ест другую пищу, он живет иначе. Его не принимают профессора в Кембридже. Его не избирают профессором, как-то его даже избивают, а потом еще и болезнь… Характер у него тоже довольно сложный. Кажется, что он очень самоуверен. “Возможно, Вы видите обычное стекло, но я обещаю, что скоро Вы увидите бриллиант,” — говорит он хозяину конторы в Мадрасе. Он хочет, чтобы его результаты опубликовали, все время говорит об этом Харди. И хотя Харди очень ценит Рамануджана, но ему лишь с огромным трудом и не сразу удается объяснить молодому индусу, что все формулы нужно доказывать, без доказательств ничего публиковать нельзя. Читать полностью ‘Человек, который познал бесконечность’ »

Задачи городской олимпиады

Эти задачи были предложены ученикам 11 класса на городской олимпиаде по математике.

Задача 1. Найдите целые положительные числа a,b и c, для которых НОК(a,b)=210; НОД(a,b)=10; НОК(a,c)=110; НОД(a,c)=2. (Здесь НОК(u,v) — наименьшее общее кратное чисел u и v, т.е. наименьшее натуральное число, делящееся на u и на v, НОД(u,v) — наибольший общий делитель чисел u и v, т.е. наибольшее натуральное число, на которое делятся числа u и v.)

Показать решение

Задача 2. Для углов \alpha,\beta и \gamma справедливо неравенство

\sin\alpha+\sin\beta+\sin\gamma\ge2.

Докажите, что тогда

\cos\alpha+\cos\beta+\cos\gamma\le\sqrt{5}.

Читать полностью ‘Задачи городской олимпиады’ »

А есть ли формула любви? (X+Y, 2014)

“Когда я разговариваю с людьми, которые не являются математиками, они всегда спорят с тем, что математика может быть красивой. Но если красота — это правда, а правда — это красота, то математика — определенно самая прекрасная вещь в мире.”

(Ричард, цитата из фильма)

Достаточно интересный фильм. Кто не смотрел, посмотрите, очень рекомендую. Однако не нашла на русском языке, только на английском (есть еще субтитры, тоже английские, что для меня было плюсом). Фильм о многом и разном, поднимает различные вопросы. Естественно, сюжет имеет отношение к математике, а как же иначе :-)

Итак, сначала немного о сюжете. Английский мальчик Нейтан — аутист, он ведет себя не так, как остальные дети, он погружен в себя, его занимают числа и геометрические фигуры, он любит математику, а окружающий мир воспринимает как-то по-своему, его пугают люди, он не может переносить их прикосновений, он не любит, когда трогают его вещи, он ест только правильное, точнее, простое количество креветочных шариков. Нейтан начинает заниматься математикой с Мартином Хамфрисом, который тоже не является обычным учителем. В свое время он побывал на Международной олимпиаде по математике и… проиграл. Виноват в этом был его характер. Сейчас у Мартина в жизни тоже много проблем. Мартин готовит Нейтана к участию в Международной математической олимпиаде, и Нейтана приглашают участвовать в отборе в команду, которая на эту олимпиаду поедет. Мальчик вместе с другими ребятами едет в Таиланд, где ребята из Англии начинают тренироваться вместе с китайскими школьниками. Он знакомится с девушкой Мэй, с которой проводит довольно много времени…

Нейтан: “Когда я рядом с ней, мой мозг работает иначе”. Читать полностью ‘А есть ли формула любви? (X+Y, 2014)’ »

Об изоморфизме графов (P vs. NP)

László Babai

Кажется, есть некоторое, довольно серьезное, продвижение в задаче об изоморфизме графов. 10 ноября математик Ласло Бабаи (László (Laci) Babai) расскажет о новом алгоритме, который позволяет решить задачу об изоморфизме графов за квазиполиномиальное время. Объявление об этом имеется на сайте Чикагского университета.

Задача об изоморфизме графов является одной из “математических болезней”. Самый быстрый известный алгоритм, позволяющий определить, изоморфны ли два данные графа, принадлежит Бабаи и Лаксу. Этот алгоритм был предложен в 1983 году. Время его работы — e^{\sqrt{n\log n}}. Если верить объявлению, Бабаи уменьшил это время до e^{{\rm polylog}(n)} ({\rm polylog}(n) — некоторый полином от \log\, n). Таким образом, одна из важнейших задач оказывается чуть-чуть более, чем P.

А теперь немного о самом Ласло Бабаи. Он родился в 1950 году в Будапеште. Работает профессором математики и информатики в Чикагском университете. Главным образом занимается комбинаторикой, теорией сложности вычислений, алгоритмами и конечными группами, особенно интересуется связями между этими областями математики. Наиболее значительные его достижения — это введение интерактивной системы доказательств, введение термина “алгоритм Лас-Вегас” и использование теоретико-групповых методов в проверке графов на изоморфизм. Читать полностью ‘Об изоморфизме графов (P vs. NP)’ »

Решение математической задачи с использованием физики

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

Эта задача по математике, предлагавшаяся шотландским школьникам, вызвала бурную дискуссию в Интернете.

Вот условие задачи на русском языке. Читать полностью ‘Решение математической задачи с использованием физики’ »