Могу больше пунктов дать. Завод выпускает погремушки в виде кольца с надетыми на него тремя красными и четырьмя синими шариками. Сколько видов различных погремушек может быть выпущено? Две погремушки считаются одинаковыми, если одна может быть получена из другой только передвижением шариков по кольцу или переворачиванием кольца.

1

Ответы и объяснения

2012-03-19T18:19:37+04:00

Если представить расположения колец погремушки битовыми последовательностями (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.

 

А с баллами Вы действительно поскромничали. Мне кажется, что сама задача (да и решение) заслуживают большего :-)