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

[recoder]

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

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

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

Comments

[hazan.livejournal.com]

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

[recoder]

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

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

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

[hazan.livejournal.com]

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

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

[tigerone.livejournal.com]

"Если билет не вставляется до упора в компостер, то можно будет отбросить одинаковые картинки, сдвинутые на несколько гвоздей по вертикали или горизонтали. "
Вот это самый интересный момент. Если закодировать бинарным кодом, то следующие комбинации будут признаны разными, хотя на самом деле - в нашем специфичном приложении их можно принять за одинаковые.
000 111
000 111
111 111
111 000
111 000

Вот исключить такие повторения - имхо не совсем просто.

[tigerone.livejournal.com]

Чтобы не очень было похоже на перевертыш - вот ещё один пример (единицы-дырочки)
011 000
011 110
000 110
000 000
000 000

[hazan.livejournal.com]

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

[tigerone.livejournal.com]

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

[hazan.livejournal.com]

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

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