Тег «комбинаторика»

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

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

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

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

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

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

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

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

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

Одна комбинаторная задача

Интересная комбинаторная задача из книги
László Babai, Péter Frankl, Linear Algebra Methods in Combinatorics with Applications to Geometry and Computer Science, Preliminary Version 2 (September 1992), The University of Chicago.

В городе n жителей. Они любят создавать клубы, маленькие и большие, это основная их деятельность. В городе изданы законы, регулирующие образование таких клубов:

1) В каждом клубе может быть только нечетное число членов.
2) Каждые два клуба имеют четное число общих членов.

Какое максимальное число различных клубов может быть создано в этом городе?

Довольно простое и красивое решение этой задачи получается, если воспользоваться методами линейной алгебры. Читать полностью ‘Одна комбинаторная задача’ »

Рождественская лотерея

Это еще одна задачка, предложенная El País.

С 2011 года проводится Рождественская лотерея, в которой разыгрываются призы между сто тысячью билетов с номерами от 00000 до 99999 (числа всегда написаны с использованием пяти цифр). Несмотря на то, что все билеты имеют одинаковые шансы выиграть, часто говорят о красивых номерах и номерах довольно некрасивых. Поскольку оценка красоты является эстетической, является ли число красивым или нет зависит от вкусов каждого.

В нашем случае лотерейный номер будет считаться красивым, если его номер отвечает одному и только одному из следующих трех условий:
а) делится на 5,
б) дает в остатке 2 при делении на 7,
в) сумма его цифр делится на 9. Читать полностью ‘Рождественская лотерея’ »

Число перестановок

Задача. Чему равно число таких перестановок (a_1,a_2,\ldots,a_n) чисел (1,2,\ldots,n), которые удовлетворяют условию a_k\ne k при всех k?

Это довольно известная задача, она встречается в разных формулировках, например, такой:

Несколько человек решили подарить друг другу подарки на Рождество. Каждый приготовил один подарок и подписал на нем свое имя. Друзья решили распределить подарки случайным образом. Они написали свои имена на листочках бумаги и положили в шапку. Каждый тянет листочек, и если получилось так, что у всех имена на вытащенных ими листках не совпали с их собственными именами (а иначе какой же это подарок — самому себе?), то распределение подарков состоялось. Сколькими различными способами могут распределиться подарки между друзьями?

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

О треугольнике Паскаля

Числовые треугольники имеют довольно много различных свойств. И задач, связанных с ними, известно достаточно много. Но вот мне недавно попалось еще одно свойство известного треугольника Паскаля. Надеюсь, вам тоже понравится ;)

Довольно интересные треугольники являются частями треугольника Паскаля. Все числа, из которых они состоят, делятся на одно и то же число. Удивительно, что делимость прослеживается только на простые числа p. Читать полностью ‘О треугольнике Паскаля’ »

Задача с монетами

Это достаточно красивая и интересная, на мой взгляд, задача.

На столе лежат 16 монет, составляющих квадрат 4\times4. Часть из этих монет лежит вверх орлом, а часть — решкой. Монеты можно переворачивать по следующим правилам: можно перевернуть все монеты, находящиеся в одном горизонтальном ряду, в одном вертикальном ряду или на одной диагонали (если монета лежит в углу, она образует диагональ из одной монеты). Целью игры является перевернуть все монеты вверх либо орлом, либо решкой. Всегда ли возможно это сделать или существуют некоторые расположения монет, для которых это невозможно? Читать полностью ‘Задача с монетами’ »