Обобщённая задача о ферзях

26

Обобщенная задача о ферзях

С. В. БЕЛЫЙ,
Е. А. РОВЕНСКИЙ

Задача о ферзях — на шахматной доске расставить максимальное число ферзей так, чтобы они не угрожали друг друга, и найти число всех таких расставок — давно уже стала классической. В XIX веке этой задачей занимался великий немецкий математик Карл Фридрих Гаусс (1777—1855), а в нашем столетии выдающийся американский математик и киберNETIK Колод Шенон (p. 1916) указал на ее прямое отношение к вопросам помехуостойчивого кодирования.

Недавно появилось интересное обобщение этой задачи, касающейся расставки максимального числа ферзей («Наука и жизнь», 1982, № 3, с. 73; «Квант», 1983, № 1, 3-я стр. обл.): на шахматной доске расставить максимальное число ферзей p так, чтобы каждый из них атаковалровно k ферзей (1≤k≤4). Эта задача была поставлена американским математиком Скоттом Кимом и опубликована в J. Recreational Mathematics, 1979-80, vol. 12, № 1, p. 53 (американский журнал, в котором публикуется статьи и задачи заимателового характера по математике). При k=0 получаем классический задачу, для которой p_max=8. Подумайте, почему в формулировке задачи сделано ограничение k≤4. Задачу Кима удалось решить частную (J. Recreational Mathematics, 1980-81, vol. 13, № 1, p. 61—62). Именено:

$$p_{\text{max}} = 10 \text{ для } k = 1,$$
$$p_{\text{max}} = 14 \text{ для } k = 2.$$

Примеры соответствующих расстановок показаны на рисунках 1 и 2.

Для k=3 и k=4 были найдены расстановки p=16 (там же) и p=21 (Scientific American, 1981, vol. 245, № 6, p. 19) соответственно, но оставалось неизвестным, являлся ли эти числа максимальными.

В данной задаче мы докажем, что $p_{\text{max}} = 18$ для k=3, (3)
$p_{\text{max}} = 21$ для k=4. (4)

Рисунки 3 и 4 показывают, что расстановки с таким числом ферзей существуют. Заметим, что расстановка с p=18 для k=3 равна не была известна. Попробуем теперь найти верхнюю оценку для p.

Пусть p—число ферзей, a q—число рядов (вертикалей, горизонталей и диагоналей), на которых стоит хотя бы один ферзь. Тогда, если бы ферзи не атаковали друг друга, то q=4p. Но так как общее число боев равно pk (каждый ферзь атакуетровно k ферзей), то

$$q = 4p - \frac{pk}{2} \text{ или } r = \frac{2k}{8-k}.$$

Докажем теперь (3). Общее число вертикалей, горизонталей и диагоналей на доске n×n равно 6n−2, поэтому

$$q \leq 6n-2.$$

Из (5) и (6) для доски 8×8 получаем p≤18.

27

Докажем (4). Так как угловые клетки доски не могут быть заняты ферзями (почему?), получаем
$$q \leq 6n - 6.$$

Из (5) и (7) для доски $8 \times 8$ находим $p \leq 21$.

Итак, задача Кима полностью решена. Нам остается добавить, что максимальные расстановки ферзей, показанные на рисунках 3 и 4, были найдены с помощью ЭВМ (на это ушло около 30 минут счета на ЭВМ с числом операций 200 тысяч в секунду). Читатели, умеющие программировать, могут попробовать свои силы в составлении такой программы.

Задача для исследования.
Естественным обобщением задачи С. Кима является следующая задача:
На шахматной доске $n \times n$ расставить максимальное число ферзей $p_{\max} = p(n, k)$ так, чтобы каждый из них атаковалровно $k$ ферзей ($0 \leq k \leq 4$), и найти число $N = N(n, k)$ та-

Оtkрытие рентгеновских лучей

(Начало см. на c. 25)

даноую более интенсивное излучение (по существу это была первая рентгеновская трубка).

Полученные результаты Рентген подытожил в вышедшей в первых числа явваря 1896 года брошюре «О новом рode лучей». Одновременно он разослал ведущим физкам мира перые рентгеновские chimки, в том числе chimок кистей руки своей жены. Пожалуйста, ни одно физическое открытие не вызвало стологомного и всеобщего интереса, как обнаружение Рентгеном лучей, прохождения сквозь стены и позволяющих видеть невидимое. Физики сразу же принялись повторять удивительные опыты, журналисты заполнили страницы газет сенсационными сообщениями. В 1901 году Рентген стал перым луреатом Нобелевской премии по физике.

Современные области применения рентгеновских лучей трудно даже перечислить — медицина, генетика, дефектология, рентгенструктурный анализ, рентгенопектральный анализ, исследования производений-старинной живописи, кримinalистика…

Выдающеся положение занимает открытие рентгеновских лучей в истории науки — именно с него началась зара атомной и ядерной физики. «В начале 1896 года, в тот самый день, когда в Париже стало известно об опытах Рентгена и о необходимости световых лучей, испускаемых лиминесцирующими стенками… трудок, — рассказывал А. Беккерель, — я задумал использовать, не испускает ли также лучи и всякое другое лиминесцирущее вещество». Предположение оказылось неверным, но в опитах Беккереля была открыта радиоактивность.

А Дж. Дж. Томсон вспоминал: «Я исследовал в течение некоторого времени проводимость газов под действием электрических сил, но сталивался с трудностью найти какой-либо такой метод создания проводимости, который был эфективным и надежным. Новые лучи снимали это затруднение… Эксперименты, которые были неозможно трудными до открытия лучей, становились легкими». Результатом этих «легких экспериментов» стало открытие Томсон (весной 1897 года) электрона.

В. Е. Явелов