Вопрос от посетителя
Могу больше пунктов дать. Завод выпускает погремушки в виде кольца с надетыми на него тремя красными и четырьмя синими шариками. Сколько видов различных погремушек может быть выпущено? Две погремушки считаются одинаковыми, если одна может быть получена из другой только передвижением шариков по кольцу или переворачиванием кольца.
Отвечает Илюха:
Если представить расположения колец погремушки битовыми последовательностями (0 – для синего кольца, 1 – для красного), то сдвиги колец и перевороты погремушки соответствуют циклическуму сдвигам последовательности вправо и ее зеркальным отображениям (или, что то же самое, чтению справа налево). Все последовательности, полученные из данной таким образом, будут эквивалентными. Признаком (уникальным) последовательности и инвариантом этих преобразований может служить, например, такая “сигнатура” – количество нулей между единицами.
Попробуем проще: Представим окружность, поделенную на 3 равных сектора в 120 градусов. В секторы проставим числа, чтобы их сумма составляла 4. При такой интерпретации наши 3 сектора соответствуют 3-м красным шарикам в погремушке, а число в секторе – числу синих шариков между двумя соответствующими красными. Эквивалентными последовательностями чисел будут те, которые получаются из исходной поворотами на 120 и 240 градусов, а также зеркальным отображением (поднесите рисунок к зеркалу и прочтите последовательность). Комбинация таких преобразований новых последовательностей нам не даст. Уникальные последовательности чисел в этом случае – это (0,0,4), (0,1,3), (0,2,2), (1,0,3) и (1,1,2) (надеюсь, я ничего не пропустил?). Таких последовательностей всего 5. Значит, и различных видов погремушек может быть тоже 5.
А с баллами Вы действительно поскромничали. Мне кажется, что сама задача (да и решение) заслуживают большего 🙂