Головоломка Красильщика

Чосер упоминает среди паломников и Красильщика, хотя больше ничего не говорит о нем, но, очевидно, до него просто не дошел черед - ведь "Рассказы" остались незаконченными. Так вот и от Красильщика компания долго не могла услышать головоломки. Бедняга пытался последовать примеру своих приятелей Обойщика, Ткача и Галантерейщика, но нужная идея все не посещала его голову, а бесплодные усилия изнуряли мозг. Однако все приходит к тому, кто терпелив, и однажды утром в состоянии крайнего возбуждения он объявил, что собирается задать паломникам одну задачку. Красильщик вытащил квадратный кусок шелковой ткани, на котором были изображены расположенные рядами лилии, - вы видите его на рисунке.
- Лорды, - сказал Красильщик, - послушайте мою загадку. С тех пор, как я проснулся на заре от крика петухов (чтоб нашему хозяину было пусто за этот шум!), я все ищу на нее ответа, но, клянусь святым Бернардом, так и не нашел. На этом куске ткани изображены 64 лилии, а вы скажите, как мне удалить шесть лилий, чтобы при этом в каждом вертикальном и горизонтальном ряду осталось по-прежнему четное число цветов.


Красильщик был ошеломлен, когда каждый из присутствующих показал, как это сделать, причем все - по-разному. Но тут заметили, что славный Оксфордский студент что-то шепнул Красильщику, и тот поспешил добавить:
- Постойте, господа хорошие! Я еще не все сказал. Вы должны определить, сколькими разными способами это можно сделать!
Все согласились, что это совсем другое дело. И только несколько человек из всей компании дали правильный ответ.

Ответ

Правильный ответ - это 18 816 различных путей. Общая формула для 6 лилий и любого квадрата, большего 22, такова: 6 умножить на квадрат числа комбинаций из n элементов по 3, где n - число лилий на стороне квадрата. Разумеется, если n четно, то число оставшихся лилий должно быть четным, а если n нечетно, то и это число должно быть нечетным.