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

[recoder]

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

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

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

Comments

[recoder]

Не... Тут всё гораздо сложнее!

Для одного зубца задача тривиальна - можно пробить только одну дырку.

Для двух, как ни странно, задача проще решается с учётом вращений. Тогда метрикой 'разности' комбинаций можно взять растояние между зубцами. Но и в заданных условиях (3x5) уже можно решать задачу. По-моему, задачу можно неплохо упростить, выделив на рабочем поле зону MxM, симметричную по-многому-как и доп. зону Mx(N-M) которая увеличивает количество комбинаций первой.