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

Эти задачи были предложены ученикам 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)’ »

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

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

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

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

Немного об омонимах :-)

Эти всем известные слова часто употребляются в обычной жизни, однако математики их используют совсем в другом смысле :-) Оказывается, таких слов довольно много. Разумеется, далее приведены не все такие слова. Предлагаю вам добавлять свои :-)

Граф в математике — совокупность непустого множества вершин и наборов пар вершин (связей между вершинами). Объекты представляются как вершины, или узлы, графа, а связи — как дуги, или ребра.

Граф в обычной жизни:

Граф Уильям Кадоган

Читать полностью ‘Немного об омонимах :-) ’ »

Забытый творец технологий: Билл Татт или Алан Тьюринг?

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

Тьюринг известен тем, что придумал первый компьютер, взломал код Энигмы… и, конечно, своей преждевременной смертью и жестоким преследованием за гомосексуализм. Ну а Билл Татт вел обычную жизнь… и вряд ли вообще известен, хотя взломал более сложный код Лоренца, с помощью которого шифровались послания от самого Гитлера, отличавшийся настолько сложной формулой, что для расшифровки отдельных сообщений было необходимо построить первый компьютер, Колосс.

“Мы столкнулись с огромным очевидным заговором с целью признать, что Алан Тьюринг сделал львиную долю работы, выполненной в Блетчли-Парке’’, — сказал Ричард Флетчер, секретарь и казначей Фонда памяти Билла Татта. — “Было понятно, что Энигма действует на воображение людей, и был также большой интерес общественности к смерти Тьюринга’’.

“К сожалению, все это отвлекло внимание людей от гораздо более важных событий, которые происходили Блетчли-Парк во время войны. Службу безопасности устраивает, что Алан Тьюринг разрекламирован, а гораздо более важные люди получают очень мало признания. Мы чувствовали, что это несправедливо, и загорелись идеей сделать с этим что-нибудь’’. Читать полностью ‘Забытый творец технологий: Билл Татт или Алан Тьюринг?’ »