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

[recoder]

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

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

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

Comments

[hazan.livejournal.com]

не понял, это одна комбинация или несколько?

[tigerone.livejournal.com]

В обоих постах - два билетика, рядом, стоя.

[hazan.livejournal.com]

Так про первый билетик я уже сказал - симметричные по горизонтали и вертикали отбрасываем.

Вот для второго как раз надо считать количество комбинаций со сдвигом.