Не все могут принять участие в конференции Турнира Городов - это неминуемый недостаток любых мероприятий, на которые нужно съезжаться в одно место. Турнир Городов сам по себе возник во многом как реакция на недоступность Всесоюзной Олимпиады для многих сильных школьников из крупных математических центров. А теперь, когда появилась Летняя Конференция Турнира Городов, возник особый стиль ее задач и условий проведения, появилось желание сделать такие соревнования доступными для максимального числа желающих.
Предлагаем Вам принять участие в заочном конкурсе Турнира Городов. Вам предлагается четыре задачи, каждая из которых состоит из большого количества пунктов. Конкурс проводится по каждой из предложенных задач в отдельности, оценивается максимальное продвижение в одной из задач. Решать задачи можно в одиночку или командой.
Работы нужно посылать по адресу: 121002, Москва, Большой Власьевский переулок, дом 11, комната 211, Турнир Городов, с пометкой "Заочный конкурс".
Туда же (в 211 комнату или вахтеру) работы можно приносить и лично (при этом они все равно должны быть в конверте с вышеуказанными данными, иначе велика вероятность, что их потеряют).
ВНИМАНИЕ !!! Время решение задач ПРОДЛЕНО.
Работы можно отправлять до 1 марта 1999 года.
Разрешается (и мы рекомендуем так делать) высылать работу частями, по мере решения пунктов в выбранной вами задаче. Тогда у вас будет шанс получить результаты проверки части вашей работы ещё до окончательного срока 1 февраля 1999 года. Дата отправки работы будет определяться по почтовому штемпелю.
Мы надеемся, что нам удалось избежать ошибок в условиях задач (в прошлые годы это не всегда удавалось).
Предложена М. Антоновым
По аллеям зоопарка бегают Заяц и Волк.
По краям аллей густо растут деревья, поэтому Волк не видит Зайца, если тот находится на другой аллее. Цель Волка - поймать Зайца.
Требуется найти все такие отношения скоростей Зайца и Волка, при которых для Волка существует способ действий, гарантирующий поимку Зайца.
При этом есть две существенно разных постановки задачи.
Задача A: дело происходит днем, светло, поэтому Волк видит "до упора", т.е. до конца аллеи.
Задача B: дело происходит ночью, темно, поэтому Волк видит на расстоянии не более 1/2.
Предлагается исследовать обе эти задачи для зоопарков, аллеи которых образуют фигуры, перечисленные ниже.
1. Два равносторонних треугольника, имеющих общую сторону длины 1.
2. Два равносторонних треугольника со стороной 1, имеющих общую вершину и образующих вертикальные углы.
3. Равносторонний треугольник со стороной 1, в котором центр соединен с вершинами.
4. Равносторонний треугольник со стороной 1, в котором проведены медианы.
5. Равносторонний треугольник со стороной 2, в котором проведена средняя линия.
6. Равносторонний треугольник со стороной 2, в котором проведены две средних линии.
7. Единичный квадрат, в котором проведены диагонали.
8. Два единичных квадрата, имеющих общую вершину и образующих вертикальные углы.
9. Два правильных N-угольника, имеющих общую вершину и образующих вертикальные углы. Стороны N-угольников равны 1.
10. Правильный треугольник, разделенный, как предыдущие, на N*N правильных треугольников. Стороны всех маленьких треугольников равны 1.
а) Случай N=2 (правильный треугольник, в котором проведены три средние линии, делящие его на 4 треугольника).
б) Случай N=3 (правильный треугольник, в котором проведены три пары параллельных линий, делящих его на 9 треугольников).
в)* Общий случай.
Следующие фигуры являют собой прямоугольники, составленные из единичных квадратиков, указаны размеры этих прямоугольников.
11. 1*2.
12. 1*N.
13. 2*2.
14. 2*N.
15*. M*N.
В следующих задачах зоопарк трехмерный, аллеи - ребра фигуры.
16. Тетраэдр, сторона равна 1.
17. Октаэдр, сторона равна 1.
Следующие фигуры являют собой параллелепипеды, составленные из единичных кубиков, указаны размеры параллелепипедов.
18. 1*1*1.
19. 1*1*N.
20. 1*2*N.
21. 2*2*N.
22*. K*L*M.
Предложена М. Вялым, В. Гурвичем, А. Кулаковым
Для начала объясним значение всех слов, входящих в название этой задачи.
Граф - это вершины и соединяющие их ребра. Каждое ребро соединяет ровно две вершины, причем мы будем считать, что эти вершины разные. Будем также считать, что каждую пару вершин соединяет не более одного ребра.
Путем называется последовательность различных вершин графа, в которой соседние вершины связаны ребром.
Длина пути равна числу входящих в него ребер.
Циклом называется замкнутый путь (последняя и первая вершины в последовательности связаны ребром).
Дыра - это цикл нечетной длины 5 или больше, у которого нет "диагоналей". Это означает, что ребра графа связывают только последовательные вершины в этом цикле.
Дополнительным графом к некоторому графу G называется граф ~G с тем же множеством вершин и дополнительным множеством ребер, т е. в ~G ребра связывают те, и только те, вершины, которые не связаны ребром в исходном графе G. Антидыра - это дыра в дополнительном графе, т.е. граф, дополнительный к дыре.
Осталось объяснить, какие графы называются вращаемыми. Представим, что вершины графа расположены в вершинах правильного многоугольника. Нарисуем все отрезки, соответствующие ребрам (они могут пересекаться, это нас не заботит). Если при поворотах, переводящих вершины многоугольника в вершины многоугольника, сохраняется множество соответствующих ребрам графа отрезков, то граф называется вращаемым. Если пометить какую-нибудь вершину графа числом 1, то все остальные вершины можно занумеровать числами от 2 до n, двигаясь против часовой стрелки по границе многоугольника. Эта нумерация будет использоваться в дальнейшем без дополнительных оговорок.
Чтобы проверить, что вы поняли определение, посмотрите еще раз на дыру и антидыру, нарисованные выше. Теперь в качестве упражнения докажите, что любая дыра и любая антидыра - вращаемые графы.
1. Придумайте удобный способ задания вращаемых графов.
Если занумеровать вершины графа, то ребра графа можно пометить парами чисел (номера концов ребра). Два графа называются равными или изоморфными, если можно так занумеровать их вершины, чтобы совпадали множества пар чисел, которыми помечены ребра этих графов.
2. Составьте полный список без повторений всех вращаемых графов с а) 5; б) 7; в) 9 вершинами.
3. а) Докажите, что различных (с точностью до изоморфизма) вращаемых графов на 11 вершинах не больше 8 штук.
б) Докажите, что различных (с точностью до изоморфизма) вращаемых графов на 23 вершинах не больше 188.
в)* Сравните число различных (с точностью до изоморфизма) вращаемых графов на 25 вершинах с числом 500.
Основной вопрос данной задачи: какие вращаемые графы не содержат ни дыр, ни антидыр?
Исследование этого вопроса разумно начать с того, чтобы выяснить, в каких вращаемых графах вообще нет циклов нечетной длины.
4. Вращаемый граф не содержит циклов нечетной длины тогда и только тогда, когда общее число его вершин четно, а ребра соединяют вершины разной четности.
Граф называется связным, если в нем любая пара вершин соединена некоторым путем.
5. Докажите, что любой непустой (имеющий хоть одно ребро) вращаемый граф с простым числом вершин связен.
6. Придумайте критерий связности вращаемого графа в общем случае (т.е. число вершин - любое).
Введем еще несколько определений.
Пустой граф не содержит никаких ребер, а в полном любая пара вершин связана ребром.
Наибольшее число попарно связанных ребрами вершин в графе называется кликовым числом (обозначение w), а наибольшее количество попарно не связанных ребрами вершин в графе называется числом независимости (обозначение a).
7. Докажите, что для любого вращаемого графа на n вершинах выполнено неравенство aw< n.
Настало время понять, когда во вращаемом графе есть дыры или антидыры. При нечетном числе вершин дыры или антидыры, как правило, есть. Простой пример графов без дыр и антидыр - это пустой граф и полный граф.
8. Выберите из нарисованных ниже графов графы без дыр и антидыр. Аргументируйте ваш выбор.
9. Найдите бесконечное множество таких графов (вращаемых, с нечетным числом вершин, без дыр и антидыр, отличных от полного и пустого). Попробуйте построить как можно большее такое множество.
10**. Опишите все графы без дыр и антидыр с нечетным числом вершин.
Задача 10 очень трудная. Авторам кажется, что некоторую пользу при ее решении принесут следующие утверждения.
11*. Пусть n - число вершин во вращаемом графе. Если некоторое ребро соединяет вершины с номерами i и j (нумерация вершин определена выше!), то его длиной будем называть наименьшее из чисел |j-i| и n-|j-i|.
Предположим, что в связном вращаемом графе с нечетным числом вершин нашлось ребро длины 1, а максимальная длина ребра равна dmax. Тогда если в этом графе нет дыр, то среди длин его ребер обязательно встретятся числа d, d+1, 2d, где d=(n-1)/2-dmax.
12.а) Докажите, что если в связном вращаемом графе с нечетным числом вершин n нет дыр, то максимальная длина ребра в таком графе не меньше (n-1)/3.
б)* Попробуйте усилить оценку пункта а).
13*. Придумайте и докажите достаточные условия того, что вращаемый граф, отличный от полного или пустого, содержит дыру или антидыру. (Например, рассмотрите такое условие: "число вершин в графе простое".)
Предложена А. Я. Беловым, С. В. Маркеловым
Выражение "фигура (тело) разбита (-о) на части" можно понимать по-разному. Во-первых, можно считать, что пересечение частей пусто (у них нет общих точек).
1. На плоскости дано (возможно, невыпуклое) множество A. Множество B есть результат некоторого движения множества A. Может ли так быть, что объединение A и B есть центрально-симметричное (возможно, невыпуклое) множество, содержащее свой центр симметрии, а пересечение множеств A и B пусто?
Во-вторых, можно допускать пересечения частей.
2. На плоскости дано множество A. Множество B есть результат некоторого движения множества A. Оказалось, что объединение A и B есть плоский прямоугольник (т.е. не ломаная, а контур вместе с внутренностью). Может ли при этом центр прямоугольника принадлежать A, но не принадлежать B?
В дальнейшем мы будем пользоваться в этой задаче естественным определением.
Определение. Фигура (тело) разбита (-о) на части, если объединение этих частей дает всю фигуру, а общие точки частей лежат на их границах.
Следующую задачу нужно исследовать во многих случаях. Задача ЦС. Центрально-симметричное выпуклое тело (фигура) разбито на два конгруэнтных множества. Доказать, что его/её центр лежит на их границе.
При этом граница будет считаться состоящей из участков прямых и окружностей (плоскостей и сфер в пространственном случае). Для многогранников граница будет считаться состоящей из участков плоскости.
3. Несколько точек разбивают отрезок на два конгруэнтных множества (множество может состоять из нескольких кусков). Докажите, что одна из них - в его центре.
4. Круг разбит на 2 части. Доказать, что они переводятся друг в друга либо поворотом относительно центра круга, либо осевой симметрией. Что можно сказать о разбиении на 3 части?
5. Задача ЦС для квадрата.
6. Задача ЦС для правильного 6-угольника.
7. Решите задачу ЦС для 3-мерной (n-мерной) сферы, считая границу разбиения состоящей из участков плоскости.
8. Решите задачу ЦС для сферы.
9. Решите задачу ЦС для куба.
10*. а) Решите задачу ЦС для плоских многоугольников.
б) для произвольных центрально-симметричных плоских фигур.
11. Можно ли фигуру, нарисованную ниже, разбить на две конгруэнтные части?
12.Четырехугольник таков, что его можно разбить на две равные части.
а) Доказать, что это можно сделать одним разрезом (здесь и далее - по прямой линии, как пишут в головоломках, одним разрубом).
б)Верно ли, что он имеет либо осевую, либо центральную симметрию?
13. Многоугольник можно разбить на 2 равные части. Верно ли, что это можно сделать одним разрезом?
14. Выпуклый многоугольник можно разбить на 2 равные части. Верно ли, что это можно сделать одним разрезом?
15. Выпуклый многоугольник можно разбить на 2 равные части, переводящиеся друг в друга движением первого рода (параллельным переносом или поворотом). Верно ли, что это можно сделать одним разрезом?
16. Эта задача для тех, кто знаком с понятием алгоритма.
Ниже приводится алгоритм проверки того, что данный многоугольник можно разбить на две равные части.
Алгоритм.
1o Составим множество критических точек. В это множество включим все вершины многоугольника и все середины его сторон.
2o Найдём самую короткую сторону многоугольника. Её длину обозначим a.
3o Из каждой критической точки проведем маленький отрезок длины a/3 вдоль контура многоугольника. Сделать это можно двумя способами (по часовой стрелке и против часовой стрелки). Получаем множество начальных ломаных.
4o Каждую пару начальных ломаных продолжаем до пары
соответственных ломаных (см. 5o-6o).
Соответственные ломаные строятся так, чтобы они были равны (совмещались
движением).
Построение пары соответственных ломаных
завершается постановкой диагноза (см. 7o-9o): можно ли
разбить многоугольник на две равные части.
5o Пусть есть пара начальных ломаных A1 и A2. Двигаемся по контуру многоугольника в заданных начальными ломаными направлениях, проверяя при проходе каждой вершины, что полученные на данный момент ломаные равны. Это движение заканчивается одним из следующих событий:
- Ломаная A1 достигла критической точки ломаной A2, одновременно с этим ломаная A2 дошла до критической точки ломаной A1. Переходим к шагу 8o.
- Ломаная A1 достигла критической точки ломаной A2, а ломаная A2 не дошла до критической точки ломаной A1. Переходим к шагу 9o.
- Ломаная A2, чтобы остаться равной ломаной A1, должна выйти за пределы многоугольника (или наоборот - за пределы многоугольника должна выйти ломаная A1). Переходим к шагу 9o.
- Ломаная A2, чтобы остаться равной ломаной A1, должна войти внутрь многоугольника (или наоборот - внутрь многоугольника должна войти ломаная A1). Переходим к шагу 6o (в его описании мы считаем, что внутрь вошла ломаная A2, второй случай описывается аналогично).
6o Продолжаем ломаную A1 дальше по контуру, а ломаную A2 - внутри (сохраняя равенство ломаных). Это движение заканчивается одним из следующих событий:
- Ломаная A1 дошла до критической точки ломаной A2. Переходим к шагу 9o.
- Ломаная A2 вновь достигла контура. Это означает, что многоугольник разбит на две части. Осталось проверить их равенство. Переходим к шагу 7o.
7o Проверить, равны ли части, полученные на шаге 6o, можно, например, продолжая ломаную A1 по контуру до критической точки ломаной A2 и следя за продолжением ломаной A2 (которое в оптимистичном варианте дойдет до критической точки ломаной A1 по контуру). Ставим диагноз, после этого переходим к следующей паре начальных ломаных и возвращаемся к 5o.
8o Диагноз: "можно" (фигура либо центрально-симметрична, либо осесимметрична, в зависимости от того, шли мы в одну сторону по конуру, или в разные). Переходим к следующей паре начальных ломаных и возвращаемся к 5o.
9o Диагноз: "нельзя" (при данном выборе начальных ломаных). Переходим к следующей паре начальных ломаных и возвращаемся к 5o.
Исследуйте приведенный алгоритм:
а) убедитесь, что это действительно алгоритм - все шаги может выполнить компьютер и ни для какого входа (многоугольника) не произойдёт "зависание" (лучше всего, если Вы умеете программировать, написать программу для реального компьютера, реализующую этот алгоритм);
б) докажите, что всегда алгоритм находит разбиение многоугольника на две равные части, если оно есть;
в) докажите, если многоугольник не центрально-симметричный, то алгоритм находит все его разбиения на две равные части;
г) сколько действий нужно совершить в этом алгоритме в худшем случае для разбиения N-угольника на две равные части (или доказательства, что такого разбиения нет)?
17**. Эта задача для тех, кто знаком с понятием алгоритма.
Придумайте алгоритм, который проверяет, можно ли разбить заданный многоугольник на 2 подобные части.
18**. Эта задача для тех, кто знаком с понятием алгоритма.
Придумайте алгоритм, который проверяет, можно ли разбить заданный многогранник на 2 равные части.
19. а) Приведите пример разбиения квадрата на 3 конгруэнтные части.
б) То же для 6-угольника.
в) Исследуйте разбиения круга на конгруэнтные части. Верно ли, что они переводятся друг в друга поворотами относительно центра окружности?
г)* Тот же вопрос для сферы.
д)* Тот же вопрос для шара.
20. Как устроено разбиение сферы на несколько частей?
а) Пускай их 1999. Верно ли, что они совмещаются друг с другом поворотами относительно некоторой оси?
б) Исследуйте разбиения сферы а) на 3; б) на 5 равных частей.
21*. Пусть многоугольник разбит на три равные части. Верно ли, что каждая из частей содержит точки границы исходного многоугольника?
22*. Эта задача для тех, кто знаком с понятием алгоритма. Решите задачи, аналогичные задачам 16-18 для разбиений на 3 части.
Хорошо известно следующее понятие:
Определение. Число n называется совершенным, если сумма всех его собственных делителей равна n.
Примером таких чисел являются 6, 28. Но известно про них мало.
1.(Евклид) Пусть 2n+1-1 - простое число. Докажите, что число 2n(2n+1-1) - совершенное.
2.(Эйлер) Докажите, что каждое четное совершенное число имеет евклидов вид, т.е. равно 2n(2n+1-1), где 2n+1-1 - простое число.
Про совершенные числа не известно даже, существуют ли нечетные совершенные числа. Мы, однако, не будем заниматься совершенными числами, а определим новое понятие:
Определение. Назовем натуральное число n сверхсовершенным, если сумма всех его делителей более, чем в 2 раза больше n (= сумма всех собственных делителей больше n).
3. Если число делится на сверхсовершенное, то оно тоже сверхсовершенное.
4. Приведите пример нечетного сверхсовершенного числа.
5. Пусть m1, m2, ... ,mk - различные
числа и
1/m1+1/m2+ ... +1/mk > 2.
Тогда число n=m1*m2*...*mk - сверхсовершенно.
6. Докажите, что существует сколь угодно длинный отрезок натурального ряда, целиком состоящий из сверхсовершенных чисел.
7. Докажите, что среди первых 19983 натуральных чисел не менее 66-ти пар поcледовательных сверхсовершенных чисел.
Определение. Обозначим через c(k,m) число отрезков натурального ряда, состоящих из k последовательных сверхсовершенных чисел, меньших m.
8. Оцените c(1,m).
9. Оцените c(2,m).
10. Оцените c(3,m).
11. Оцените c(k,m).