Рубрика «Разные задачи»

Лемма Бёрнсайда и задача об ожерельях

Уильям Бёрнсайд

Уильям Бёрнсайд

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

Задача. Сколько существует различных ожерелий, составленных из n красных и m синих бусин? (Считается, что два ожерелья одинаковы, если одно можно получить из другого поворотом.)

Эта задача решается с помощью леммы Бернсайда, которая позволяет получить и множество других интересных результатов.

Сначала немного истории. Уильям Бернсайд (1852–1927) привел доказательство этой леммы в своей книге в 1897 г. Однако выяснилось, что данную формулу знали еще Коши (1845 г.) и Фробениус (1887 г.). Видимо, лемма была настолько хорошо известна, что Бернсайд не указал авторство Коши. Данный результат имеет несколько названий (кроме уже приведенного): лемма Коши — Фробениуса, лемма не Бернсайда (в области теории групп очень многие результаты принадлежат именно Бернсайду).

Для формулировки леммы понадобятся некоторые сведения. Поскольку нас интересует задача об ожерельях, на ее примере и будем все рассматривать.

Обозначим через M множество всех ожерелий. Пусть G — множество всех различных поворотов ожерелий (ясно, что разных поворотов всего n+m). Очевидно, что Gгруппа. При этом каждому ожерелью из M можно сопоставить ожерелье, полученное из него с помощью поворота g\in G. При этом два ожерелья считаются одинаковыми, или эквивалентными, если одно можно перевести в другое каким-либо поворотом из G. Таким образом, все ожерелья разбиваются на классы эквивалентности, или орбиты. Наша задача — найти число различных орбит. Читать полностью ‘Лемма Бёрнсайда и задача об ожерельях’ »

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

Эти задачи были предложены ученикам 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}.\]

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

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

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

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

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

Еще две задачи из тестов

Здесь сказано, что эти задачи, как, впрочем, и известная задача о дне рождения Шерил, мало отношения имеют к математике. Это больше задачи на логику. Тем не менее, в Интернете все три задачи бурно обсуждались, и их появление способствовало усилению страха перед математикой.

Вьетнамская задача для третьеклассников

Расставьте числа от 1 до 9 в пустые клетки так, чтобы получился верный результат (: обозначает деление)

Читать полностью ‘Еще две задачи из тестов’ »

Еще логические задачи

В связи с интересом к задаче о дне рождения Шерил выкладываю еще две довольно интересные, на мой взгляд, логические задачи :-)

Тайные дары

— Красота? Смелость? Щедрость? Терпение? Мудрость? Что Вы хотите для новорожденной принцессы? — спросила Добрая фея короля-отца. Читать полностью ‘Еще логические задачи’ »

День рождения Шерил

На олимпиаде по математике школьникам старших классов Сингапура была предложена следующая задача: Читать полностью ‘День рождения Шерил’ »