Старинные математические задачи

 

                               13*3 = 36,       20*3 = 60,

                               60 + 36 = 96,     3 + 3 = 6.

 

Значит, у первого человека было 96:6 = 16 рублей, а у второго 3/2(24 – 16) = 12 рублей.

 

3.Часть  вторая.

3.1 Обход мостов.

Задача 98. Мосты  в Кенигсберге.

Вот перевод латинского текста, который взят из письма Эйлера к  итальянскому математику и инженеру Маринони, отправленного из Петербурга 13 марта 1736 года.

«Некогда мне была предложена задача об острове, расположенном в  городе Кенигсберге и окруженном рекой, через которую перекинуто 8 мостов. Спрашивается, может ли кто-нибудь неправильно обойти их, проходя только однажды через каждый мост. И тут же мне было сообщено,

 

 

 

 

 

 

что никто ещё до сих  пор не смог это проделать, но никто  и не доказал, что это невозможно. Вопрос этот, хотя и банальный, показался  мне, однако, достойным внимания тем, что для его решения недостаточны ни геометрия, ни алгебра, ни комбинаторное  искусство.…После долгих размышлений  я нашел легкое правило, основанное на вполне убедительном доказательстве, с помощью которого можно во всех задачах этого рода тотчас же определить, может ли быть совершенен такой обход через какое угодно число и как угодно расположенных мостов или не может. Кенигсбергские же мосты расположены так, что их можно представить на следующем рисунке (рис.3), на котором A обозначает остров, а B, C и D – части континента, отдельные друг от друга рукавами реки. Семь мостов обозначены буквами a, b, c, d, e, f, g».

По поводу найденного им способа решать подобные задачи Эйлер  писал:

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

Можно ли обойти Кенигсбергские мосты, проходя только однажды через каждый мост?

Продолжим письмо Эйлера к  Маринони:

«Итак, вопрос состоит в  том, чтобы определить можно ли обойти все эти семь мостов, проходя через  каждый однажды, или нельзя. Мое правило  приводит к следующему решению этого  вопроса. Прежде всего, нужно смотреть, сколько есть участков, разделенных  водой, - таких, у которых нет другого  перехода с одного на другой, кроме  как через мост. В данном примере  таких участков четыре, A, B, C, D. Далее нужно различать, является ли число мостов, ведущих к этим отдельным участкам, четным или нечетным. Так, в нашем случае к участку A ведут пять мостов, а к остальным – по три моста, т.е. число мостов, ведущих к отдельным участкам, нечетное, а этого одного уже достаточно для решения задачи. Когда это определено, применяем следующее правило: если бы число мостов, ведущих к каждому отдельному участку, было четным, то тогда обход, о котором идет речь, был бы возможен, и в то же время можно было бы начать этот обход с любого участка. Если же из этих чисел два были бы нечетные, ибо только одно быть не четным не может, то и тогда мог бы совершиться переход, как это предписано, но только начало обхода непременно должно быть взято от одного из тех двух участков, к которым ведет нечетное число мостов. Если бы, наконец, было больше двух участков, к которым ведет нечетное число мостов, то тогда такое движение вообще невозможно. Итак, поскольку в предложенном примере к четырем участкам число мостов нечетное, мы тщетно искали бы такой обход. А вот если бы [Через рукав, разъединяющий части B и D на рис.3] прибавить ещё восьмой мост, то тогда  было бы только два участка, а именно A и C, к которым ведет нечетное число мостов, и поэтому требуемый обход мог бы совершиться, если бы только начало обхода было взято от A или C. Если бы можно было привести здесь другие, более серьезные задачи, этот метод мог бы принести ещё большую пользу и им не следовало бы пренебрегать».

Обоснование правила можно  найти в письме Эйлера к своему другу Элеру от 3 апреля 1736 года. Я  перескажу ниже отрывок из этого  письма.

Рассмотрим произвольный участок разветвления реки, а также  мосты a, b, c, d, e, f, как это указано на рис. 4. Области, отделенные друг от друга водой, назовем буквами A, B и С. Каждый путь, пролегающий по участку, удобно обозначить последовательностью букв A, B и С, указывающих области, последовательно проходимые на этом пути. Так, ABCACAB будет обозначать некоторый переход, начинающийся в области A (рис.4), заканчивающийся в области B и, как легко видеть, совершаемый через все мосты по одному разу. Число букв всегда должно быть на единицу больше числа пересекаемых мостов.

Теперь рассмотрим, сколько  раз в указанном ряде букв A, B, C, A, C, A, B, встречается каждая из букв A, B, C. Об этом можно судить по числу мостов, ведущих в каждую из областей. Если буква A стоит внутри последовательности букв, обозначающих переход, то при прохождении через область A на этой части пути нужно пересечь два моста, ведущих в A, один для того, чтобы войти в область A, и другой для того, чтобы из неё выйти. Итак, Если какая – то область не является начальной или конечной, то количество появлений соответствующей буквы в последовательности, обозначающий путь, проходящий через все мосты по одному разу, вдвое меньше числа мостов, ведущих в эту область. Так, в область C на рис.4 ведет 4 моста, и указанной выше последовательности букв буква C встречается два раза. Отсюда следует, что в область, не являющуюся начальной или

 

 

 

 

 

 

конечной для пути, проходящего  через все мосты по одному разу, ведет четное число мостов, значит:

1. если имеется более двух областей, в которые ведет нечетное число мостов, то указанный переход невозможен;
2. если число мостов, ведущих в некоторую область A, нечетно, то переход через все мосты не может совершиться иначе, чем таким образом, чтобы он или начинался в области A или заканчивался в области A;
3. если число мостов, ведущих во все области, четно и указанный переход начинается в области A, то в этой же области A он должен и закончиться.

В случае, если на участке  разветвления реки имеется не более  двух областей, в которые ведет  нечетное число мостов, то требуемый переход возможен. Для того чтобы проще представить себе это, будем стирать на рисунке уже пройденные мосты. Легко проверить, что если мы начнем двигаться в соответствии с правилами Эйлера, пересечем один мост и сотрем его, то на рисунке будет изображен участок, где опять имеется не более двух областей, в которые ведет нечетное число мостов, а при наличии областей с нечетным числом мостов мы будем располагаться в одной из них. Продолжая двигаться так далее, мы пройдем через все мосты по одному разу.

 

Задача 99. Пятнадцать мостов. 

В некоторой местности  через протоки переброшено 15 мостов

(см рис.5).

 

 

 

 

 

 

 

 

Можно ли обойти все мосты, пройдя по каждому из них только один раз?

Подсчитаем, сколько мостов ведет в каждую из областей на рис.5; в A – 8 мостов, в B – 4 моста, в C – 4 моста, в D – 3 моста, в E – 5 мостов.

Итак, имеется только две  области D и E, в которые ведет нечетное число мостов. Обход должен начинаться с одной из них. Вот один из возможных обходов, начинающийся в области E:

a, b, c, d, e, f, g, h, i, k, m, n, p, q, l

(здесь последовательно  указаны проходимые мосты).

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

 

3.2 Шахматы.

Задача 102. Задача с запретом.

Обозначим Q_n , n ≥ 2, количество размещений n ладей на шахматной доске размером n*n клеток с условием,

 

 

 

что каждые две ладьи не угрожают друг другу и ни одна ладья  не стоит на главной диагонали (так  будем называть диагональ, идущую из левого нижнего угла в правый верхний). Тогда Q₂ = 1, Q₃ = 2(рис.6).

Л. Эйлер, занимаясь этой задачей, установил соотношение 

Q_n = (n – 1) (Q_n-1 + Q_n-2), n ≥ 4.

Из него, в частности, следует, что 

Q₄ = 9, Q₅ = 44, Q₆ = 265, Q₇ = 1854, Q₈ = 14 833.

Докажите соотношение  Эйлера.

Задача о подсчете числа  Q_n стала классической в результате математики, называемом комбинаторикой. Для неё существует множество эквивалентных формулировок.

Приведем рассуждения  Эйлера. В каждом столбце из клеток доски должна стоять и притом только одна ладья. В первом столбце ладья  может занимать только n – 1 позицию, ведь самая нижняя клетка этого столбца принадлежит главной диагонали, и ставить на неё ладью запрещено условием.

Поставим ладью на некоторую, скажем, на r-ю, клетку первого столбца. Все расположения ладей, удовлетворяющие условию задачи и такие, что в первом столбце ладья занимает r-ю клетку, разобьем на 2 группы. Рассмотрим клетку, симметричную r-й клетке первого столбца относительно главной диагонали. Если рассматриваемая клетка не занята ладьей, то размещение ладей отнесем в первую группу, если же в рассматриваемой клетке стоит ладья, то размещение отнесем во вторую группу. Так, например, на рис. 7 при n = 4 и r = 2 указаны два размещения ладей. Одно из них относится к первой группе, а другое – ко второй.

Подсчитаем теперь количество размещений в первой группе. Если удалить  из доски r-ю строку, заменив её первой, а затем отбросить первый столбец, то получится доска размером (n – 1)*(n – 1) клеток. Каждое размещение ладей из первой группы дает после этих преобразований некоторое размещение ладей на новой доске размером (n – 1)*(n – 1) клеток, удовлетворяющее условию задачи. Верно и обратное, по каждому размещению ладей на новой доске, удовлетворяющему условиям задачи, однозначно восстанавливается размещение ладей из первой группы. Следовательно, первая группа размещений ладей содержит в точности Q_n-1 размещений.

Подсчитаем теперь количество размещений во второй группе. Если удалить из доски первый столбец и r-ю строку, а также r-й столбец и первую строку, а оставшиеся строки и столбцы сдвинуть, не меняя их порядка, так чтобы получилась доска размером (n – 2)*(n – 2) клетки, то каждое размещение ладей из второй группы даст при этом некоторое размещение ладей на новой доске размером (n – 2)*(n – 2) клетки, удовлетворяющее условию задачи. Отсюда следует, что вторая группа содержит Q_n-2 размещения ладей.

Итак, имеется Q_n-1 + Q_n-2  размещений ладей на доске размером n*n, которые отвечают условиям задачи и у которых ладья стоит на пересечении первого столбца и r-й строки. Поскольку r может принимать n – 1 значение (2, 3, …, n), находим, что

Q_n = (n – 1) (Q_n-1 + Q_n-2).

 

3.3 Геометрическая  задача Эйлера.

Задача 128. Интересное свойство выпуклого многогранника.

В любом выпуклом многоугольнике число вершин всегда равняется числу сторон. Обозначив буквой B число вершин, а буквой C – число сторон многоугольника, это утверждение можно записать в виде равенства B – C = 0. Доказательство его очевидно.

Рассмотрим теперь какой-нибудь выпуклый многогранник. Число его  вершин обозначим буквой B, число ребер – буквой P, а число граней буквой Г.

Существует ли соотношение  между величинами В, Р и Г, аналогичное  соотношению между числом вершин многоугольника и числом его сторон?

Вычислим выражение В  – Р + Г для несколько типов  многогранников – см. табл. 1.

Обратите внимание, что  в последней колонке табл. 1 все  числа равны 2. Если мы продолжим  эту таблицу,

Таблица 1

Тип многогранника	В	Р	Г	В – Р + Г
1. Куб 2. n-угольная пирамида 3. n угольная призма	8 n+1 2n	12 2n 3n	6 n+1 n+2	2 2 2

 

вычисляя значение  В  – Р + Г для каких-нибудь других выпуклых многогранников, то всегда будете получать в последней колонке  число 2.

Докажите, что для любого выпуклого многогранника имеет  место равенство 

В   Р   Г = 2.

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

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

Будем последовательно окрашивать ребра многогранника в красный  цвет, пользуясь следующими правилами:

а) сначала возьмем любой  замкнутый круг по ребрам многогранника  и окрасим какое-нибудь ребро, входящее в этот путь;

б) если существует замкнутый  круг, проходящий по неокрашенным ребрам многогранника, то окрасим какое-нибудь его ребро;

в) окраску прекратим, как  только не станет замкнутых путей, проходящих по неокрашенным ребрам.                                             рис. 6

На рис.6 показана раскраска  куба, выполненная в соответствии с нашими условиями. Порядок раскраски ребер отмечен номерами; ребра, окрашенные в красный цвет, выделенные на рисунке жирными линиями.

Докажем теперь, что всегда число неокрашенных ребер равняется  В – 1, число окрашенных ребер  равняется Г – 1 и, следовательно,

Р = (В – 1) + (Г – 1), т.е. В  – Р + Г = 2.

Установим для этого два  утверждения.

1) Из любой вершины многогранника в любую другую можно пройти по не закрашенным ребрам единственным способом.

Перед началом окраски  ребер из любой вершины многогранника  в любую другую можно было пройти по неокрашенным ребрам. Это свойство будет сохраняться и после окраски каждого очередного ребра. Действительно, пусть C и D – две вершины многогранника. Если соединяющие их пути по не закрашенным ребрам не содержит очередное раскрашиваемое ребро, то утверждение очевидно. В противном случае можно изменить  путь так, как это указано на рис. 7. Итак, по окончании раскраски любые две вершины многогранника будут соединены путем, проходящим по не закрашенным ребрам.

 

 

 

 

 

Если бы между какими –  то вершинами многогранника существовали два различных пути, проходящих по не закрашенным ребрам, то нашелся  бы замкнутый путь, все ребра которого были бы не окрашены, а это в соответствии с нашими правилами окраски невозможно. Утверждение под номером 1) доказано.