Разбиений ровно три; замечание на problems.ru ошибочно; сама регата единственности никогда не утверждала.
1. Лемма о пяти колоннах. Самый тонкий момент первого сообщения — «свободные строки обязаны идти подряд» — был проговорён там скороговоркой; вот аккуратная версия. Вертикальных прямоугольников ровно пять, и два в одном столбце не уживаются: суммарная высота была бы не меньше
. Значит, в каждом из пяти столбцов стоит ровно один вертикальный прямоугольник — пять колонн. Но тогда каждая клетка свободной строки занята колонной своего столбца, то есть каждая колонна проходит через все три свободные строки. Среди колонн есть и
(горизонталей всего две, а троек — три); его высота совпадает с тройкой свободных строк, стало быть, эти строки сплошные. Заодно отпадают «рваные» тройки вроде {2, 3, 5}.
2. Три архитектуры. Пары длин горизонталей — (3,3), (3,4) или (4,4); суммарное перекрытие двух карнизов по столбцам равно
,
и
, то есть 1, 2 и 3. Поскольку горизонтали — интервалы, выбор невелик:
- (3,3): верх {1,2,3}, низ {3,4,5};
- (3,4): верх {1,2,3}, низ {2,3,4,5} — вариант «верх {2,3,4}» отпадает: тогда четвёрке пришлось бы накрыть сразу столбцы 1 и 5, на что интервал длины 4 не способен;
- (4,4): верх {1,2,3,4}, низ {2,3,4,5}.
Дальше всё принудительно: в столбце j колонна — это сплошной блок клеток, не занятых карнизами (строки 2–4, плюс первая, если верхняя горизонталь до столбца j не дотягивается, плюс пятая, если нижняя). Блок автоматически выходит длины 3 или 4, и в каждом из трёх случаев набирается ровно четыре четвёрки и три тройки. Произвола не остаётся ни на клетку.
I: пара длин (3,3) — два горизонтальных 
II: пара длин (3,4) — горизонтальные и 
III: пара длин (4,4) — два горизонтальных 3. Почему классы именно три. Среди двух горизонталей четвёрок может быть 0, 1 или 2. Любая симметрия квадрата переводит пятёрку вертикалей в пятёрку прямоугольников одного направления, а парочку горизонталей — в парочку другого; длины при этом сохраняются. Значит, число четвёрок среди «парочки» — инвариант, и три класса попарно неэквивалентны. Для спокойствия я проделал ещё и глупую машинную проверку: перебор с возвратом (на каждом шаге самая верхняя-левая свободная клетка закрывается всеми возможными способами) с последующей склейкой образов по всем восьми симметриям квадрата. Всего разбиений при фиксированном положении квадрата получается 16, и распадаются они на орбиты размеров 8, 4 и 4: классы (3,3) и (4,4) переходят в себя поворотом на 180°, класс (3,4) асимметричен.
— по формуле орбита–стабилизатор всё сходится. Текст программы — в приложении в конце сообщения.
4. Первоисточник. В официальном решении регаты (задача 1.3,
olympiads.mccme.ru/regata/20142015/Text_7.htm) сказано дословно:
Цитата:
Отметим, что количество прямоугольников каждого вида определяется однозначно, а располагать их можно по-разному.
Там же выведено уравнение
с единственным решением
. Иными словами, регата единственности не утверждала. Фраза «приведённый пример единственный (с точностью до симметрии)» появилась уже на problems.ru (
задача 65214); полагаю, её автор перепутал единственность набора прямоугольников — набор действительно один: четыре
и три
— с единственностью самого разбиения. В напечатанном виде утверждение неверно.
5. Мораль. Все три разбиения устроены одинаково: два карниза, пять колонн, перекрытие карнизов — один, два, три столбца. Свободный параметр ровно один — пара длин карнизов, — и пробегает он ровно три значения. Дворец, стало быть, один; пропорции — разные.
Приложение: машинная проверка. Python 3, ничего кроме стандартной библиотеки, доли секунды. Каждое разбиение порождается перебором ровно один раз: на каждом шаге закрывается самая верхняя-левая свободная клетка, а равные прямоугольники неразличимы. Канонический представитель класса — лексикографический минимум среди восьми симметричных образов, с переименованием букв в порядке первого вхождения.
Код:
#!/usr/bin/env python3
"""Полный перебор разбиений квадрата 5x5 на 4 прямоугольника 1x4 и 3 прямоугольника 1x3.
Прямоугольники можно ориентировать горизонтально (1 строка x k столбцов) или
вертикально (k строк x 1 столбец). Перебираем все разбиения, канонизируем
относительно диэдральной группы D4 (8 симметрий квадрата) и считаем классы
и размеры орбит.
"""
N = 5
RECTS = [4, 4, 4, 4, 3, 3, 3] # длины прямоугольников
def all_placements():
"""Все возможные размещения одного прямоугольника длины k: (клетки, ориентация)."""
res = {}
for k in (3, 4):
placements = []
# горизонтальные: строки 0..4, столбцы c..c+k-1
for r in range(N):
for c in range(N - k + 1):
cells = frozenset((r, c + i) for i in range(k))
placements.append((cells, 'H'))
# вертикальные
for c in range(N):
for r in range(N - k + 1):
cells = frozenset((r + i, c) for i in range(k))
placements.append((cells, 'V'))
res[k] = placements
return res
PLACEMENTS = all_placements()
def solve(cells_used, remaining, current):
"""Генератор всех разбиений. remaining - список длин, current - список размещений."""
if not remaining:
if len(cells_used) == N * N:
yield tuple(current)
return
# выбираем самую верхнюю-левую незанятую клетку
for r in range(N):
for c in range(N):
if (r, c) not in cells_used:
first = (r, c)
break
else:
continue
break
k_sizes = sorted(set(remaining), reverse=True)
for k in k_sizes:
rest = list(remaining)
rest.remove(k)
for cells, orient in PLACEMENTS[k]:
if first in cells and cells.isdisjoint(cells_used):
yield from solve(cells_used | cells, rest, current + [(cells, orient)])
def render(tiling):
"""Кодировка буквами A..G (в порядке первых вхождений)."""
grid = [[None] * N for _ in range(N)]
for idx, (cells, _) in enumerate(tiling):
ch = chr(ord('A') + idx)
for (r, c) in cells:
grid[r][c] = ch
return ''.join(''.join(row) for row in grid)
def transforms(grid_str):
"""8 симметрий квадрата над строкой из 25 символов."""
g = [list(grid_str[i * N:(i + 1) * N]) for i in range(N)]
def rot(m): # поворот на 90 градусов
return [list(row) for row in zip(*m[::-1])]
def fliph(m):
return [row[::-1] for row in m]
out = []
cur = g
for _ in range(4):
out.append(''.join(''.join(row) for row in cur))
out.append(''.join(''.join(row) for row in fliph(cur)))
cur = rot(cur)
return out
def normalize(grid_str):
"""Каноническая форма: минимизируем по 8 симметриям с ПЕРЕИМЕНОВАНИЕМ букв."""
best = None
for t in transforms(grid_str):
# переименование букв в порядке первого вхождения
mapping = {}
s = []
for ch in t:
if ch not in mapping:
mapping[ch] = chr(ord('A') + len(mapping))
s.append(mapping[ch])
s = ''.join(s)
if best is None or s < best:
best = s
return best
def pair_lens(code):
"""Пара длин прямоугольников того направления, которое встречается дважды."""
cells = {}
for i, ch in enumerate(code):
cells.setdefault(ch, []).append((i // N, i % N))
sizes = {}
for ch, pts in cells.items():
rows = {r for r, _ in pts}
sizes[ch] = ('H' if len(rows) == 1 else 'V', len(pts))
for direction in ('H', 'V'):
pair = sorted(n for d, n in sizes.values() if d == direction)
if len(pair) == 2:
return tuple(pair)
raise ValueError("нет направления ровно с двумя прямоугольниками: " + code)
def main():
# Длины прямоугольников фиксированы; прямоугольники одного размера
# неразличимы, поэтому remaining достаточно держать отсортированным.
# Каждое разбиение порождается ровно один раз: закрываемая клетка
# (самая верхняя-левая свободная) определена однозначно, а значит,
# однозначно и покрывающее её размещение в готовом разбиении.
raw = [render(t) for t in solve(frozenset(), sorted(RECTS, reverse=True), [])]
classes = {}
for code in raw:
classes.setdefault(normalize(code), []).append(code)
print(f"Разбиений при фиксированном положении квадрата: {len(raw)}")
print(f"Классов с точностью до симметрий D4: {len(classes)}")
for canon in sorted(classes, key=pair_lens):
print(f" пара длин {pair_lens(canon)}: орбита {len(classes[canon])}, код {canon}")
if __name__ == '__main__':
main()
Вывод программы:
Код:
Разбиений при фиксированном положении квадрата: 16
Классов с точностью до симметрий D4: 3
пара длин (3, 3): орбита 4, код AAAABCCCCBDEEEBDFFFFDGGGG
пара длин (3, 4): орбита 8, код AAAABCCCCBDEEEBDFFFBDGGGG
пара длин (4, 4): орбита 4, код AAAABCDDDBCEEEBCFFFBCGGGG
