ноябрь 2007 года

01.11.2007, Вавилов В.В.

Задачи А.Н. Колмогорова

Здесь предложены избранные задачи из числа тех, которые Андрей Николаевич Колмогоров предлагал учащимся спецшколы школы-интерната №18 при МГУ (ныне СУНЦ МГУ), на страницах журнала «Квант» и студентам механико-математического факультета МГУ им. М.В. Ломоносова.

Все эти задачи могут стать началом самостоятельных научных исследований.

199. Какие правильные многоугольники можно получить в пересечении куба плоскостью? Тот же вопрос для других правильных и полуправильных многогранников.

200. Дана центральная проекция каркасного многогранника типа куба (кубоид), на которой стерта одна вершина и три ребра, которые ее содержат. При помощи линейки восстановить весь рисунок.

201. Переключатель (рис.1а) с двумя входами и двумя выходами может находится в двух различных состояниях.

На рис. 1б изображена схема телефонной связи с тремя входами и тремя выходами, которая обладает таким свойством «универсальности»: меняя состояния переключателей, можно осуществить любое из шести соединений с тремя различными выходами, т.е.

1 -> 1, 2 -> 2, 3 -> 3

1 -> 3, 2 -> 1, 3 -> 2

1 -> 2, 2 -> 3, 3 -> 1

1 -> 2, 2 -> 1, 3 -> 3

1 -> 3, 2 -> 2, 3 -> 1

1 -> 1, 2 -> 3, 3 -> 2

(Проверьте это. Заметьте, что общее число различных состояний этой схемы равно 2³ = 8, поскольку каждый из переключателей может находится в двух состояниях.)

А) Постройте схему с четырьмя входами и четырьмя выходами, которая была бы «универсальной», т.е. осуществляла бы любое из 24 возможных соединений выходов и входов.

Б) Какое минимальное число переключателей нужно для такой схемы?

В*) Назовем схему с n входами и n выходами n – универсальной, если она осуществляет любое из n! = 1·2·3 … ·n возможных соединений n входов с n различными выходами.

На рис.1в изображена схема с восемью входами и восемью выходами, где А и В – 4-универсальные схемы. Докажите, что она является 8-универсальной.

Оцените сверху и снизу число переключателей в минимальной n-универсальной схеме.

202. Дан угол и точка М внутри него. Существует ли фигура (отдельный вопрос для выпуклой фигуры), которая при вращении, касаясь сторон угла, будет содержать точку М на своей границе?

203. Назовем гладкой дугу, которая может быть представлена в параметрическом виде Р = F(t), где t пробегает отрезок [a,b], Р – точка плоскости, а F –дифференцируемая (векторная) функция.

А) Это определение очень интересно, но несколько отличается от обычного. Доказать, например, что любая ломаная является гладкой дугой в указанном смысле.

Б) Существуют ли не гладкие дуги конечной длины?

204. Покрытие плоскости правильными многоугольниками, быть может, различными, но с одинаковыми сторонами (без наложений и пропусков) - широко известная задача среди геометров и специалистов по кристаллографии.

А) Установить теорему, которая содержала бы описание всех правильных покрытий (паркетов), т.е. таких, когда в каждой вершине покрытия сходятся одинаковые многоугольники и в том же порядке. Более точно, доказать, что таких различных правильных паркетов на плоскости существует ровно 11. На рисунке показаны, для примера, только два таких паркета.

Б) Представляется интересным исследовать вопрос о правильных паркетах на сфере, т.е. вопрос о заполнении сферы правильными сферическими многоугольниками. Предполагаемый ответ (который может оказаться и неверным!) состоит в том, что таких различных паркетов на сфере имеется ровно 18.

Попробуйте это доказать или опровергнуть.

С) Какие правильные многоугольники можно разместить на каждом из правильных паркетов так, чтобы их вершины находились в узлах паркетов?

Д) На первом рисунке плоскость покрыта квадратами пяти цветов. Центры квадратов одного и того же цвета расположены в вершинах квадратной сетки. При каком числе цветов возможно аналогичное заполнение плоскости?

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

Примечание: В первой задаче число цветов может равняться единице (все квадраты одного цвета) и двум (как на шахматной доске). Во второй задаче вы без труда найдете решение с одним цветом и с тремя цветами. Желательно дать полное решение задач, т.е. описать все раскраски, удовлетворяющие указанным условиям. Подумайте, например, существуют ли во второй задаче решение с тринадцатью цветами?

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

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

206. Показанная на рисунке красивая форма решета Эратосфена заимствована из книги М. Гарднера «Математические досуги» (М.: Мир, 1972). Все перечеркнутые числа – простые, кроме числа 121. Объясните почему!

А) Чтобы получить список простых чисел, меньших 1000, надо «отсеять» числа, делящиеся на 2,3,5,7,11,… На каком простом числе при этом остановиться?

Как изменится ответ для случая составления таблицы простых чисел, меньших 10000?

Восклицательным знаком в таблице отмечены пары простых чисел-«близнецов». В нашей таблице их десять. Известно, что простых чисел бесконечно много. Но никто не знает, конечно или бесконечно множество пар близнецов.

Б) Первые две пары близнецов (3,5) и (5,7) имеют общий элемент 5. «Расстояние между второй и третьей парой близнецов (11,13) равно 11 – 7 = 4. расстояние между третьей и четвертой (17,19) равно 17 – 13 = 4, между четвертой и пятой (29,31) равно 29 – 19 = 10.

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

207. По любому натуральному числу n можно построить другое натуральное число m по следующему правилу: запишем число n русскими словами и подсчитаем количество затраченных на эту запись букв – это и будет число m. Например, числу n = 1987 (тысяча девятьсот восемьдесят семь) отвечает число m = 30.

Делая такие сопоставления n -> m для маленьких n, легко найти те из них, которые «переходят» сами в себя (то есть m=n): это n₁ = 3(три), n₂ = 11(одиннадцать). Однако есть еще тройка замечательных чисел, которые указанным преобразованием переводятся друг в друга по циклу. Это тройка состоит из чисел 4,5 и 6:

4(четыре) -> 6(шесть) -> 5(пять) -> 4(четыре).

А что происходит с другими числами?

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

1987 -> 30(тридцать) -> 8(восемь) -> 6 -> 5 -> 4 -> 6.

Первый же взятый пример привел нас к циклу 6 -> 5 -> 4 -> 6. Конечно, имеется также много чисел, сводящихся и к «неподвижным» точкам n₁ = 3 и n₂ = 11 нашего преобразования. Но все ли числа сводятся в конечном счете к этим неподвижным точкам или к циклу 6 -> 5 -> 4 -> 6?

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

А) Найти все неподвижные точки и циклы указанного преобразования (две неподвижные точки уже найдены).

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

Второе утверждение может показаться сомнительным – тогда попытайтесь опровергнуть его!

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

По поводу этой задачи можно ставить и другие вопросы. Например:

В) Каковы классы эквивалентных в смысле рассматриваемого преобразования чисел? (Два числа эквивалентны, если они сводятся к одной и той же неподвижной точке или одному и тому же циклу.)

Г) Оценить число шагов (итераций), за которое данное число «превращается» в неподвижную точку или попадает в цикл.

Эти вопросы уже существенно сложнее…

Литература

1. А. Н. Колмогоров, Математика – наука и профессия. –М.: Наука, 1988 (Библиотечка «Квант», №64).

2. Н.Б. Васильев, А.А. Егоров, Задачи Всесоюзных математических олимпиад. – М.: Наука, 1988.

3. А. Колмогоров, Одна проблема из теории кривых. (В книге: Математическая школа. Лекции и задачи. Вып.YIII). – М: Издательство МГУ, 1966,

4. А.Савин, Просто, как колумбово яйцо. – Журнал «Квант», 1(1993).

5. А. Евдокименко, И. Селиванова, -Учебно-методическая газета»Математика. 1 сентября»,

6. В. Вавилов, Школа математического творчества. – М.: РОХОС, 2003.