Проблема 8 ферзей

Оценка высоты макета Эйфелевой башни, предложенная на прошлой неделе, — один из тех случаев, когда «глаз-алмаз» часто дает сбой. Большинство опрошенных считают, что железный макет весом в килограмм будет примерно размером с обычную литровую бутылку, хотя на самом деле его высота составит около полутора метров. И дело в том, что, если смотреть с нашей крошечной человеческой перспективы, Эйфелева башня — это огромная масса железа, но на самом деле это чрезвычайно изящная конструкция.

Округляя, Эйфелева башня имеет высоту около 300 метров и весит около 8000 тонн, то есть она в 8 миллионов раз больше, чем килограммовый железный макет, и, следовательно, в 200 раз выше (200³ = 8000000). Следовательно, высота макета составит примерно 300/200 = 1,5 м.

Где чаще всего подводит «глаз-алмаз», так это в оценках, связанных с процессами экспоненциального роста, то есть с геометрическими прогрессиями. Самый известный пример — мифический изобретатель шахмат, который просит в награду одно зерно пшеницы за первую клетку доски, два за вторую, четыре за третью и так далее. Нелегко представить, что зернами, соответствующими 64 клеткам доски, можно было бы покрыть Иберийский полуостров слоем пшеницы толщиной в несколько метров. Или что, сложив лист бумаги 43 раза подряд, можно получить толщину, сравнимую с расстоянием от Земли до Луны.

Кстати, знаете ли вы, почему геометрические прогрессии так называются? А арифметические? И если вы этого не знаете (что наиболее вероятно), можете ли вы придумать какое-нибудь разумное объяснение?

Шахматная доска и ее варианты — неисчерпаемые источники головоломок всех видов. Вспомнился мне один пример, который мне недавно прислал друг, отдаленно связанный с классической проблемой 8 ферзей (расставить 8 ферзей на пустой шахматной доске так, чтобы ни один из них не угрожал другому). Речь идет о размещении 18 фишек на доске 6x6 таким образом, чтобы в каждой строке, в каждом столбце и на обеих диагоналях было 3 и только 3 фишки.

На тривиальной доске 2x2 очевидно, что мы не можем разместить 2 фишки в соответствии с условиями задачи: либо они находятся в смежных клетках, либо по диагонали.

Можно ли обобщить задачу на другие доски с четным количеством клеток?

На доске 4x4 можем ли мы разместить 8 фишек так, чтобы в каждой строке, столбце и диагонали было по 2 фишки?

На обычной шахматной доске 8x8 можем ли мы разместить 32 фишки так, чтобы в каждой строке, столбце и диагонали было по 4 фишки?

Еще сложнее:

Можно ли доказать, что на любой доске 2nx2n, где n — любое натуральное число больше 1, мы можем разместить 2n² фишек так, чтобы в каждой строке, столбце и диагонали было n?