Попробуйте ответить на вопрос еще одной логической головоломки.

Если головоломка, которую вы разгадали перед тем, как вы разгадали эту, была труднее, чем головоломка, которую вы разгадали после того, как вы разгадали головоломку, которую вы разгадали перед тем, как вы разгадали эту, то была ли головоломка, которую вы разгадали перед тем, как вы разгадали эту, труднее, чем эта? Ответ: да.

Рис. 4 Головоломка с перемещением шашек. Переместите черную шашку в крайнюю левую клетку, используя свободные боковые поля. На это требуется не менее 28 перемещений шашек.

Рис. 5 Задача на маневрирование. Сколько раз нужно перевести стрелку, чтобы поменять местами вагоны, если через туннель может проходить только паровоз? Решения: 1-14 перемещений.

МАТЕМАТИКА НА ШАХМАТНОЙ ДОСКЕ

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

Нумерация рисунков идет в порядке их расположения.

Задача 1. Обойти конем все поля доски, посетив каждое из них по одному разу.

Этой задачей занимались многие математики XVIII и XIX вв., в том числе и Л. Эйлер. Хотя задача была известна и до Эйлера, лишь он впервые обратил внимание на ее математическую сущность. Неизвестно до сих пор, сколько всего существует маршрутов, хотя доказано, что число их не больше 30млн. Придумано много методов построения маршрутов коня, установлены различные математические закономерности. Приведем три маршрута. На рис. 1, 2 они изображены графически (каждые два соседних поля маршрута соединены отрезком), а на рис. 3 поля маршрута последовательно пронумерованы от 1 до 64. Маршруты на рис. 1, 3 замкнутые (исходное и конечное поля связаны ходом коня), а маршрут на рис. 2 открытый. Маршрут на рис. 3 образует полумагический квадрат 8x8 (сумма чисел на любой вертикали и на любой горизонтали равна числу 260, а на главных диагоналях отлична от этого числа, см. Магические и латинские квадраты) и, кроме того, обладает необычайной симметрией – при повороте доски на 180° первая половина маршрута (от 1 до 32) превращается во вторую (от 33 до 64).

Задачи о маршрутах составлены и для других фигур. На рис. 4 изображен кратчайший замкнутый маршрут ферзя по всей доске, занимающий 14 ходов.

Задача 2. Сколькими способами можно расставить на доске восемь ферзей так, чтобы они не угрожали друг другу, т.е. никакие два из них не стояли бы на одной линии (вертикали, горизонтали или диагонали)?

Найти ту или иную расстановку несложно, труднее подсчитать их общее число. Доказано, что существует 92 требуемые расстановки, причем они получаются из 12 основных поворотами и зеркальными отражениями доски. Одно из решений задачи представлено на рис. 5.

Подобные задачи ставятся для всех шахматных фигур. Сначала выясняется, какое наибольшее число фигур не угрожает на доске друг другу, а затем – сколько имеется расстановок. Ладей, как и ферзей, можно расставить максимум восемь (всего 8! = 40320 расстановок), например, их можно поставить на те же поля, что и ферзей на рис. 5. Максимальное число не угрожающих друг другу слонов равно 14 – рис. 6 (256 расстановок), коней – 32 (две расстановки, на всех белых или на всех черных полях), королей – 16 – рис. 7 (281 571 расстановка).

Другой класс задач на расстановки связан с расположением минимального числа фигур так, чтобы они держали под ударом все свободные поля доски. Для этой цели достаточно взять пять ферзей (рис. 8), восемь ладей (их можно поставить на те же поля, что и ферзи на рис. 5), восемь слонов (рис. 9), двенадцать коней (рис. 10), девять королей (рис. 11). Не обо всех фигурах известно, сколько существует необходимых расстановок.

Для охраны доски меньшим, чем пять, числом фигур не обойтись, однако их состав можно «ослабить», заменив двух ферзей ладьями или даже ладьей с королем или слоном (рис. 12).

МАТРИЦА

Матрица – прямоугольная таблица, составленная из чисел.

Располагать те или иные данные в виде прямоугольных таблиц приходится довольно часто. Например, если три завода выпускают пять различных видов продукции, то отчет о производстве за год может быть дан в виде таблицы

где x_ij – количество продукции j-го вида, выпущенное i-м заводом в течение этого года. Кратко будем обозначать эту таблицу X = (x_ij) и назовем ее прямоугольной матрицей с тремя строками и пятью столбцами. Аналогично определяется понятие прямоугольной матрицы с m строками и n столбцами (или, короче, (m×n)-матрицы). При m=n такую матрицу называют квадратной, а число n - порядком этой матрицы.

Если ассортимент продукции не изменился в течение следующего года, то отчет о производстве за второй год тоже имеет вид матрицы Y = (y_ij). Но тогда выпуск продукции за два года выражается матрицей X + Y = (x_ij + y_ij). Вообще, при сложении двух (m×n)-матриц складываются соответствующие элементы этих матриц. Если же в течение второго года производство каждого вида продукции на каждом заводе увеличилось на 20%, то для любых i,j верно равенство y_ij=1,2·x_ij. В этом случае пишут Y = 1,2X. Чтобы умножить матрицу X на число λ, надо умножить на это число каждый элемент матрицы.

Выпуск продукции можно выражать не только в штуках, метрах или тоннах, но и в рублях. Для этого надо знать цену каждого вида продукции. Поскольку она может меняться от года к году, обозначим через λ_jk цену j-го вида продукции в k-й год. Эти цены можно записать в виде (n×s)-матрицы Λ, где n-число видов продукции и s- число лет. Например, при s=4 имеем матрицу

Выпуск продукции i-м заводом за k-й год, выраженный в рублях, составит величину

a_ik = x_i1λ_1k + x_i2λ_2k + ... + x_inλ_nk, (1)

где каждое слагаемое есть произведение величины выпуска соответствующего вида продукции в выбранных единицах на стоимость единицы этой продукции в рублях. Числа a_ik образуют матрицу A с m (у нас m = 5) строками и s(у нас s = 4) столбцами. Такую матрицу принято называть произведением матриц X и Λ:

A = X ·Λ.

Итак, если X является (m×n)-матрицей, а Λ - (n×s)-матрицей, то их произведением называют (m×s)-матрицу A = X Λ, состоящую из элементов, определяемых по формуле (1). При умножении квадратных матриц n-го порядка снова получается квадратная матрица n-го порядка.

Особую роль играет матрица E

у которой вдоль диагонали из верхнего левого угла в правый нижний стоят единицы, а остальные элементы равны нулю; для любой квадратной матрицы n×n X имеем: XE = EX = X, т.е. она играет роль единицы. Если определитель квадратной матрицы X отличен от нуля, то существует обратная ей матрица X^-1, такая, что XX^-1 = X^-1X = E. Возникает матричная алгебра, в которой верны многие правила обычной алгебры, например (XY)Z = X(YZ), X(Y + Z) = XY + XZ и т.д. Однако умножение не является коммутативным, т.е., вообще говоря, XY ≠ YX.