Таблицы Брадиса

Видно, что эти ожерелья различны.

Видно, что эти ожерелья различны.

Элементы математики в задачах - Г. А. Мерзон

Задача 11*. Сколько существует различных наборов бусинок, из ко­торых можно составить ровно два различных ожерелья?

Во-первых, очень важно разобраться в том, какие наборы счита­ются различными, а какие — нет. Например, наборы {синий, синий, красный} и {оранжевый, зеленый, зеленый} считаются одинаковы­ми, а наборы {красный, синий, зеленый} и {голубой, желтый, голу­бой} — различными. Почему?

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

Решение. Во-первых, наборы бусинок не упорядочены, то есть наборы {синий, синий, красный} и {синий, красный, синий} одинаковы. Во-вторых, наборы, получающиеся друг из друга переименованием цветов, также считаются одинаковыми.

Докажем сначала, что в искомом наборе не может быть слишком много различных цветов, а именно, не может быть более трех различ­ных цветов. Допустим, нашелся набор, содержащий бусинки четырех различных цветов (назовем их красный, желтый, зеленый, синий), из которого можно составить только два различных ожерелья. Рассмот­рим следующие ожерелья:

 

Здесь «К» означает все бусинки красного цвета, «З» — синего и т. д. Видно, что эти ожерелья различны. Следовательно, в искомом наборе не более трех различных цветов. Если все бусинки одноцветны, то можно составить только одно ожерелье. Итак, в искомом наборе бусинок может встречаться или два, или три цвета. Дальше задача является явным перебором. Приведем его для случая двух цветов.