Задачка про компостеры

[recoder]

Ежедневные поездки на троллейбусе навели меня на такую простенькую с виду задачку:

Есть компостер, в котором установлено M x N зубчиков-перфораторов (В случае моего троллейбуса - 3x5). Спрашивается - каков минимальный набор прокомпостированных билетов, покрывающий всё множество различимых комбинаций? То есть - сколько есть комбинаций, различимых сдвигами и поворотами на 90°. Для простоты предположим, что прямоугольный билет всегда прямо укладывается в компостер, так что вариантами с вращением на произвольные углы мы пренебрегаем.

У нас с tigerone не хватило знаний комбинаторики чтобы решить такую задачу (в смысле - решить аналитически, а не полным перебором на компе).

Comments

[hazan.livejournal.com]

Я так думаю, что 2 в степени(NxM) - это без учета поворотов на 90 градусов и не отбрасывая зеркальные изображения.

[hazan.livejournal.com]

Это полное количество комбинаций этой матрицы. Половину можно отбросить сразу - как симметричные по горизонтальной оси.
Если билет не вставляется до упора в компостер, то можно будет отбросить одинаковые картинки, сдвинутые на несколько гвоздей по вертикали или горизонтали. Еще, наверное, можно откинуть симметричные по вертикальной оси - еще половина.

Чем еще можно пренебречь?