Головоломка Монаха

Монах, ехавший со всей компанией, был большим любителем спорта. "Наездник страстный, он любил охоту и богомолье - только не работу". Однажды, обратясь к паломникам, он сказал:
- Есть одна вещь, которая заставляет меня порой сильно задумываться, хотя, конечно, она не столь и важна. Все же она может служить для проверки остроты ума.


Я имею девять будок для собак, они расположены в форме квадрата, хотя среднюю конуру я не использую. Так вот, головоломка состоит в том, чтобы выяснить, сколькими различными способами могу я поместить своих собак во всех наружных будках так, чтобы число собак на каждой стороне квадрата равнялось десяти.
Небольшие диаграммы, приведенные на рисунке, показывают четыре таких способа, и хотя четвертый способ является лишь перевернутым третьим, он считается отличным от третьего. Любую будку можно оставить пустой. Эта головоломка, очевидно, представляет собой лишь разновидность известной головоломки об аббатисе и ее монахинях.

Ответ

Монах мог поместить собак в конуры 2926 различными способами так, чтобы на каждой стороне было по 10 собак. Число собак может изменяться от 20 до 40; в этих пределах всегда можно расположить собак нужным способом.
Решение этой головоломки в общем виде непросто. В случае n собак на каждой стороне квадрата число различных способов равно


при n нечетном и


при n четном, если считать только те размещения, которые существенно различны. Но если мы будем считать все перевернутые и отраженные размещения различными, как и поступал сам Монах, то n (четное или нечетное) собак можно разместить


способами. Дабы возможно было поместить по n собак на каждой стороне, их число должно быть не меньше 2n и не больше 4n, но внутри этих границ его можно взять любым.
Обобщение принципа, лежащего в основе этой головоломки, приведено в задаче 42.