Алімпіяды. Конкурсы

 

Исследовательские задания

XI областного турнира юных математиков

Важные указания к порядку решения и оформления исследований

по заданиям турнира юных математиков

Обращаем ваше ВНИМАНИЕ на то, что предлагаемые задания (далее – задачи) носят исследовательский характер (в отличие от олимпиадных задач). Полные решения и наилучшие обобщения этих задач неизвестны даже авторам, поэтому: ·        во-первых, для участия необязательно решать все задачи – минимальное количество представляемых в жюри задач – 6, НО итог будет подводиться по всем представленным решенным верно задачам (всего предлагается 13 задач); ·        во-вторых, наиболее полное решение (исследование) задачи не означает, что нужно решить ВСЕ ПУНКТЫ задачи, точнее – решаем «настолько полно насколько можем», имейте в виду, что в ряде задач интерес представляют даже первые пункты или отдельные частные случаи заданий (их пунктов или небольших значений параметров); ·        в-третьих, возможно (это допускается и даже приветствуется) вы сможете усилить ряд утверждений, приведенных непосредственно в формулировках задач; ·        в-четвертых, кроме рассмотрения исходной постановки полезно рассмотреть свои направления, причем ваши исследования НЕОБЯЗАТЕЛЬНО должны совпадать с предложениями авторов; o   оформление каждой задачи должно начинаться С ТИТУЛЬНОГО ЛИСТА, на котором нужно указать номер задачи и ее название, название учреждения образования, название команды (если команда является сборной двух или нескольких учреждений), город, автора(ов) исследования (решения); o   НИЖЕ НА ТИТУЛЬНОМ ЛИСТЕ (или на втором листе) обязательно дайте краткое резюме вашего исследования – какие пункты вы решили, какие сделали обобщения, четко сформулируйте ВАШИ СОБСТВЕННЫЕ ГЛАВНЫЕ ДОСТИЖЕНИЯ (утверждения, примеры, гипотезы); o   ОБЯЗАТЕЛЬНО дайте четкие ссылки на литературу и другие источники, которые вы использовали при проведении исследований (в месте их использования).

 

 

 

СПИСОК заданий,

предлагаемых для XI областного турнира юных математиков

 

Задача 1.   Тройки целых чисел

 

1) Найдите три натуральных числа  x, y, z  таких, что сумма любых двух из них делится на третье число, т.е. x + y делится на z, x + z делится на y, z + y делится на x.

2) Решите пункт 1) с условием, что все три числа x, y, z попарно различны.

3) Найдите все тройки натуральных чисел x, y, z такие, что сумма любых двух из этих чисел делится на третье.

4) Найдите три натуральных чисел  x, y, z  таких, что произведение любых двух из них, увеличенное на 1, делится на третье число. То есть (xy+1) делится на z, (xz+1) делится на y, (yz+1) делится на x.

5) Найдите одиннадцать различных решений пункта 4, то есть одиннадцать троек натуральных чисел  x, y, z  таких, что произведение любых двух из этих чисел, увеличенное на 1, делится на третье.

6) Найдите все решения пункта 4, то есть все тройки натуральных чисел  x, y, z  такие, что произведение любых двух из этих чисел, увеличенное на 1, делится на третье.

7) Предложите свои обобщения и направления исследования в этой задаче и изучите их. Вот некоторые из возможных направлений:

- найдите все натуральные числа  x, y, z  такие, что сумма любых двух из этих чисел, увеличенная на 1, делится на третье число;

- что получиться, если в пунктах 1-3 брать не просто суммы, а некие линейные комбинации типа Аx + Вy делится на z, Аx + Вz делится на y, и т.д. при заданных фиксированных А и В (для начала можно рассмотреть конкретные самостоятельно выбранные значения А и В);

- рассмотрите подобные задачи для четырех чисел и т.д. (точные формулировки задайте сами).

 

Задача 2.   Соседство клеток

Дан клетчатый квадрат n ´ n  клеток (n Î N, n ³ 5). Во всех пунктах задачи интересны как точные значения (количества), так и их верхние или нижние оценки.

1. Две клетки клетчатого квадрата назовем соседними, если они имеют общую сторону. Какое наибольшее количество клеток можно закрасить внутри квадрата так, чтобы каждая закрашенная клетка имела бы не более k соседних закрашенных клеток, если а) k = 1, б)k = 2, в) k = 3. Начните исследование с частных случаев nÎ{5, 6, 7}.
2. Две клетки клетчатого квадрата назовем диагонально соседними, если они имеют ровно одну общую точку. Решите задачу, аналогичную пункту 1, для диагонально соседних клеток.
3. Две клетки клетчатого квадрата назовем близкими, если они имеют хотя бы одну общую точку, т.е. являются либо соседними, либо диагонально соседними. Решите задачу, аналогичную пункту 1, для близких клеток при kÎ{1, 2, 3. 4, 5, 6, 7}.
4. Под расстоянием между двумя клетками будем понимать минимальное количество ходов, которое необходимо, чтобы из одной клетки попасть в другую, переходя за один ход в соседнюю по стороне клетку. Две клетки клетчатого квадрата назовем 2-соседними, если клетки находятся на расстоянии 2 друг от друга. В частности, 2-соседними являются диагонально соседние клетки. Решите задачу, аналогичную пункту 1, для 2-соседних клеток при kÎ{1, 2, 3. 4, 5, 6, 7}.
5. Исследуйте задачи пунктов 1-4 для клетчатых прямоугольников m ´ n, m ¹ n ³ 3.
6. Предложите свои обобщения и направления исследования. Например, рассмотрите подобную задачу в пространстве. Попробуйте решить обратную задачу: какое наименьшее количество клеток клетчатой доски можно закрасить так, чтобы у каждой закрашенной клетки было бы не менее k закрашенных соседей определенного вида.

 

Задача 3.   Наборы кратных сумм

Пусть дан произвольный набор А вещественных чисел . Набором k‑сумм (или набором кратных сумм, или набором сумм кратности k) назовём совокупность всех чисел вида , где   и обозначим его S(k).

Набором k-сумм  S[k]  c повторениями (или, как и выше, набором сумм с повторениями кратности k) назовём совокупность чисел вида

,   где   .

Например, для набора A = {1, 2, 5, 7} набор 2-сумм S(2) = {3, 6, 7, 8, 9, 12}, а набор 3-сумм  S(3) = {8, 10, 13, 14}.

1. Попарные суммы
   • Из чисел можно образовать 10 попарных сумм: . Докажите, что, зная числа  , но не зная, суммой каких именно двух чисел является каждое из них, можно восстановить числа .
   • a) Приведите пример двух наборов из четырёх чисел каждый, у которых совпадают наборы кратных сумм.

б) Пусть  – набор попарных сумм для некоторого набора из четырёх чисел. Докажите, что существует ещё один набор с тем же набором попарных сумм.

• Докажите, что при n = 2k существуют два набора по n чисел каждый, у которых совпадают наборы попарных сумм. Однозначно ли определяется набор из n чисел набором попарных сумм при n ¹ 2k?
• а) Приведите пример трех наборов из n чисел (n £ 3), у которых совпадают наборы попарных сумм.

б) Докажите, что при n = 8 не существует четырёх наборов, у которых совпадают наборы попарных сумм.

• Докажите, что для набора количество различных сумм вида  может быть любым числом из диапазона [2n – 1; ].

2. Суммы большей кратности
   • Верно ли, что не существует четырёх наборов из 6 чисел, у которых одинаковое семейство 3-сумм?
   • При каких n набор из n чисел однозначно определяется набором своих 3‑сумм?
   • Докажите, что набор из 12 чисел однозначно определяется набором своих 4‑сумм.
   • Верно ли, что набор из 10 чисел однозначно определяется набором своих 5‑сумм? При каких n набор из n чисел однозначно определяется набором своих 5‑сумм?
   • Докажите, что при любом k набор A однозначно определяется набором A[k].
   • Предложите необходимые и достаточные условия для набора S(k), по которому можно однозначно восстановить набор A.
3. Предложите свои обобщения и направления исследования в этой задаче и изучите их.

 

Задача 4.   Суммы в таблицах

1. I. Обозначим a_ij – число, записанное в i-ой строке и j-ом столбце таблицы n´n. При этом известно, что суммы чисел во всех строках и во всех столбцах таблиц одинаковые. Кроме того, и . Найдите сумму всех чисел в таблице в зависимости от n, k, A и B. Если сумма может принимать несколько значений, найдите их все. Решите задачу в случае, если:

1) n = 5, k = 2, A = 10 и B = 15;

2) n = 5, k = 2, A и B — произвольные действительные числа;

3) n = 4, k = 2, A и B — произвольные действительные числа;

4) n = 2k, а k, A и B — произвольные действительные числа;

5) n, k, A и B — произвольные действительные числа.

1. II. Опять суммы чисел во всех строках и во всех столбцах таблиц одинаковые. При этом натуральное число k таково, что 2k<n и сумма чисел в каждом из четырех угловых квадратов k´k таблицы n´n равна A, а сумма чисел в центральном квадрате (n – 2k)´(n – 2k) равна B. Найдите сумму всех чисел в таблице в зависимости от n, k, A и B. Если сумма может принимать несколько значений, найдите их все. Решите задачу в случае, если:

1) n = 7, k = 2, A = 10 и B = 25;

2) n = 7, k = 2, A и B – произвольные действительные числа;

3) n = 6, k = 2, A и B – произвольные действительные числа;

4) n = 8, k = 2, A и B – произвольные действительные числа;

5) n, k, A и B – произвольные действительные числа.

III. Рассмотрите аналогичную задачу, но на шестиугольной таблице. Опять суммы чисел во всех строках таблиц, параллельных одной из сторон, одинаковые. В приведенном примере (см. рисунок справа) в шестиугольнике каждая сторона разбита на n = 2 части и суммы в каждой из двенадцати строк равны 21. Для четкой формализации задачи попробуйте дать определение понятие строк в шестиугольной таблице и нумерации их элементов.

1) Пусть n = 4, то есть каждая сторона разбита на 4 части. Выберем один узел получившейся треугольной решетки, как показано на рисунке. Через него проходят три прямые, параллельные сторонам шестиугольника и разбивающие его на 6 частей. Будем считать, что суммы чисел в трех из этих шести частей нам известны, это A, B и C, как показано на рисунке. Найдите сумму всех чисел в таблице в зависимости от A, B и C. Если сумма может принимать несколько значений, найдите их все.

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

3) Рассмотрите шестиугольные таблицы с другими значениями n.

1. IV. Предложите свои обобщения данной задачи и решите их.

 

Задача 5.   Многочлены и арифметика

1. I. По следу Маркова. Все рассматриваемые в пункте переменные, как и параметры, могут принимать только целые значения. Требуется найти все целые значения параметра a, при которых уравнение имеет не менее двух решений в целых числах. Также требуется найти все целочисленные решения уравнений в этих случаях. Решите эту задачу для уравнений:

1) x₁² + x₂² +…+ x_n² = ax₁x₂…x_n   при   a) n = 2;   б) n = 3;   в) n = 4;   г) при n > 4;

2) xⁿ + yⁿ = ax^n–1y^n–1         при   а) n = 3;   б) при n > 3;

3) xⁿ + yⁿ = axy                при а) n = 3; и б) при n > 3;

4) xⁿ + yⁿ = ax^ky^n–k            для всех натуральных k меньших n;

5) Предложите свои обобщения данной задачи и исследуйте их.

1. II. Хорошие многочлены. Под многочленом мы понимаем многочлен с целыми коэффициентами. Многочлен f (x₁,x₂,…,x_n) назовем хорошим, если для любого натурального m множество натуральных решений уравнения  конечно (напомним, что пустое множество тоже конечно).
2. Докажите что многочлены f₁(x, y) = x² + y² и f₂ (x, y, z) = x² + y² + z² хороши.
3. Верно ли, что многочлен f (x₁,x₂,…, x_n) является хорошим тогда и только тогда, когда для любого натурального m множество натуральных решений неравенства 0 £ f (x₁, x₂,…, x_n) ≤ m конечно?
4. Являются ли хорошими многочлены f₃(x, y) = x² –xy + y² и f₄ (x, y) = x² – 2y²?
5. Для каких натуральных n существует хороший многочлен от n переменных первой степени? Опишите все такие многочлены.
6. Верно ли, что многочлен g(x,y) = ax² + 2bxy + cy² является хорошим, если

   ac – b² > 0?

7. Найдите условие при которых многочлен второй степени двух переменных является хорошим или опишите все хорошие многочлены второй степени двух переменных.
8. Многочлен f (x₁,x₂,…, x_n) назовем:

– почти хорошим, если для любого натурального m множество целых решений уравнения f (x₁, x₂,…, x_n) = m конечно;

– типа хорошим, если для любого целого m множество натуральных решений уравнения f (x₁, x₂,…, x_n) = m конечно;

– очень хорошим, если для любого целого m множество целых решений уравнения f (x₁, x₂,…, x_n) = m конечно.

Как связаны понятия почти хороший многочлен, типа хороший многочлен, очень хороший многочлен и хороший многочлен? Для каждого из приведенных выше типов многочленов, отличного от хорошего, решите задачи 0-5.

7. Исследуйте свои направления в решении этой задачи.

 

Задача 6.   Диагонали

Диагональ многоугольника назовем внутренней, если все её точки (за исключением вершин), лежат строго внутри многоугольника. Диагональ многоугольника назовем внешней, если все её точки (за исключением вершин), лежат строго вне многоугольника. Диагональ многоугольника, которая не является ни внутренней, ни внешней будем называть кочующей.

а) Верно ли, что если все диагонали многоугольника внутренние, то многоугольник — выпуклый?

б) Верно ли что в любом многоугольнике, в котором не менее четырёх вершин, есть хотя бы одна внутренняя диагональ?

в) Для каждого конкретного n ³ 4, или хотя бы для некоторых значений n, выясните, какое наименьшее (наибольшее) количество внутренних/внешних диагоналей может быть в n-угольнике.

г) При каких n и k можно построить n-угольник с k внутренними диагоналями?

д) При каких n и k можно построить n-угольник с k внешними диагоналями?

е) При каких n и k можно построить n-угольник с k кочующими диагоналями?

ж) Предложите свои обобщения и направления исследования в этой задаче и изучите их.

 

Задача 7.   Площади и объемы

 

1. Дан треугольник АВС, у которого АВ = 5, ВС = 6, СА = 9.

а) В треугольник вписана окружность. Пусть М, К, Т – точки касания этой окружности со сторонами АВ, ВС, СА соответственно. Как связаны площади треугольников МКТ и АВС?

б) Пусть М₁, К₁, Т₁ – точки касания вневписанных окружностей со сторонами АВ, ВС, СА соответственно. Как связаны площади треугольников М₁К₁Т₁ и АВС?

2. Те же задачи, если стороны треугольника АВС равны а, b, с.
3. В треугольнике АВС проведены три чевианы АМ, ВК, СТ, пересекающиеся в точке О. Как связаны площади треугольников МКТ и АВС, если стороны треугольника АВС равны а, b, с? Получите ответ в зависимости от отношений, в которых точки M, K и T делят соответствующие стороны (в общем или хотя бы в некоторых конкретных случаях).
4. В трапецию ABCD (AD║BC) вписана окружность, точки касания которой со сторонами AB, BC, CD, DА – соответственно M, K, N, L. Как связаны площади трапеции и четырехугольника MKNL, если известны стороны трапеции AD=a, BC=b, AB=d, CD=c.
5. Предложите свои обобщения задач 2 – 4 и решите их.
6. Пусть SABC – треугольная пирамида с ребрами SA=a, SB=b, SC=c, AB=d, BC=e, CA=f. В пирамиду вписана сфера, точки касания которой с гранями ABC, SAB, SBC, SCA есть соответственно M, N, K, L. Как связаны объемы пирамид SABC и  MNKL. Рассмотреть случаи:

а) SABC – правильный тетраэдр;

1. b) SABC – правильная пирамида;

с) SABC – равногранная пирамида;

1. b) SABC – правильная пирамида;
2. d) SABC – произвольная пирамида.
3. Те же задачи для пирамиды SABC и вневписанных сфер.
4. Предложите свои обобщения задач 6,7 и решите их.

 Задача 8.   Игры с кучками

1. 1) Есть две кучки с n и m камней (m и n не обязательно различны). Двое играют в игру. Каждый игрок на своем ходу должен избавиться от одной из двух кучек (убрать ее), а оставшуюся кучку разделить на две по своему усмотрению (в куче должно быть натуральное число камней). Проигрывает тот, кто не может сделать ход. При каких n и m выигрывает начинающий игру, а при каких игрок, который делает второй ход? Как при этом им нужно играть?

2) Тот же вопрос для случая, если оставшуюся кучку нельзя делить на равные кучи. Например, нельзя кучу из двух камней разделить на две кучи по одному камню.

2. 1) Пусть теперь есть три кучи с n, m, k камней. Игрок на своем ходу должен избавиться от любой (одной) кучки, а одну из двух оставшихся разделить по своему усмотрению. Все также проигрывает тот, кто не может сделать ход. При каких n, m, k выигрывает первый игрок, а при каких второй?

2) У игроков все также три кучи, но теперь за ход нужно избавиться от любых двух кучек, а оставшуюся разделить на три кучки по своему усмотрению.  По-прежнему проигрывает тот, кто не может сделать ход. Ответьте на все тот же вопрос: при какой тройке n, m, k выигрывает первый, а при какой второй?

3. Решите пункт 2 (подпункты 1 и 2), если после своего хода игроку нельзя оставлять хотя бы две кучи с одинаковым количеством камней. Например, если остались кучи с количеством камней 3, 2 и 1, то в пункте а) сделать ход невозможно т.к. можно делить только кучу из 3 камней, но какую бы из куч (1 или 2) игрок не удалил, то либо останется две кучи по 1 камню, либо две кучи по 2 камня. А по пункту б) невозможно делить и кучу из 3 камней, т.к. у нас получиться сразу три кучи по одному камню.
4. Теперь у нас есть два типа игроков: игрок А перед своим ходом имеет две кучи, он должен от одной избавиться и оставшуюся разделить на три по своему усмотрению, игрок В перед своим ходом имеет три кучи, он должен от двух избавиться и оставшуюся разделить на две. Проигрывает тот, кто не может сделать ход. Исследуйте два случая (возможно без разделения на подпункты):

1) Первым делает ход игрок А, а за ним игрок В и в начале имеется две кучи с n и m камней.

2) Первым ход делает игрок В и соответственно в начале три кучи с n, m, k камней. Кроме этого исследуйте данную постановку задачи для случая, когда игрокам нельзя после своего хода оставлять одинаковые кучи.

5. Исследуйте задачи аналогичные пунктам 2 и 3 если имеется 4 кучи и:

1) игрок на своем ходу убирает одну кучу и любую из оставшихся делит на две; 2) игрок на своем ходу убирает две кучи и любую из оставшихся делит на три;

3) игрок на своем ходу убирает две кучи и каждую из оставшихся делит на две;

4) игрок на своем ходу убирает три кучи и любую из оставшихся делит на четыре.

6. Придумайте свои обобщения и направления исследований в этой задаче и изучите их.

 

 

Задача 9.   Котик и многоугольник

 

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

• Кто выиграет при правильной игре?
• Кто выиграет при правильной игре, если кот материализовался в произвольной ограниченной области пятиугольника?
• Изменится ли ответ на второй вопрос, если пятиугольник будет произвольным?
• Кто победит при правильной игре, если первоначально будет нарисован правильный шестиугольник со всеми диагоналями, не проходящими через центр описанной окружности, и кот материализовался в области, содержащей центр описанной окружности.
• Тот же вопрос, для правильного семи-, девяти- и т. д. угольника, а кот материализуется в центре описанной окружности.
• Вопрос, аналогичный четвертому пункту, но для правильного восьми-, десяти- и т. д. угольника.
• Придумайте свои обобщения и направления исследований в этой задаче и изучите их.

 

 

Задача 10.   Цепные дроби

Известно, что каждое рациональное число  можно единственным образом представить в виде конечной цепной дроби

,

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

1. Найдите или оцените длину k цепной дроби в зависимости от значений числителя и знаменателя m и n несократимой дроби .
2. Пусть дробь является неотрицательной правильной несократимой. Ослабим условия на коэффициенты  цепной дроби, допуская целые ненулевые значения этих  коэффициентов.
   • Для небольших значений k (k = 1, 2, 3) найдите все представления заданной дроби  в виде цепной дроби , ,
   • Для произвольного фиксированного значения k  найдите необходимые и достаточные условия существования разложения дроби  в виде цепной дроби , , .
3. Исследуйте вопросы пп. 1, 2.1, 2.2 в предположении, что числитель и знаменатель дроби являются некоторыми многочленами с действительными коэффициентами, а коэффициенты  цепной дроби  также являются многочленами с действительными коэффициентами.
4. Исследуйте вопросы существования, единственности разложения чисел вида () в цепную дробь  фиксированной длины, где  – ненулевые числа вида  ().

 

 

Задача 11.   Рёберные степенные последовательности графов

Стандартные понятия теории графов, не определяемые в задаче, можно найти в книге [Мельников О.И. Теория графов в занимательных задачах. Изд. 3-е, испр. и доп. – М.: Книжный дом «ЛИБРОКОМ», 2009. – 232 с.].

Графом называется упорядоченная пара G = (V, E), где V — некоторое непустое конечное множество, E — множество неупорядоченных пар различных элементов из V. Элементы множества V называются вершинами графа, элементы множества E — его рёбрами. Множество вершин графа G будем обозначать V(G), множество рёбер — E(G). Подмножество всех вершин графа G, смежных с вершиной u, называется окружением вершины u и обозначается N(u); число deg u = |N(u)| называется степенью вершины u. Степенью ребра e = {u, v} в графе G называется число deg e = deg u + deg v – 2.

Список степеней вершин (рёбер) графа называется его вершинной (рёберной) степенной последовательностью. Порядок членов в этих последовательностях роли не играет. Часто удобно эти последовательности считать невозрастающими. Последовательность p = (d₁, d₂, …, d_m) целых неотрицательных чисел называется вершинной (рёберной) графической последовательностью, если существует граф, вершинная (рёберная) степенная последовательность которого совпадает с p. Этот граф называется вершинной (рёберной) реализацией последовательности p. Если вcе вершинные (рёберные) реализации вершинной (рёберной) графической последовательности изоморфны, то эта последовательность называется вершинной (рёберной) униграфической.

Рёберным графом произвольного графа G называется граф, вершины которого соответствуют рёбрам графа G, и две вершины являются смежными тогда и только тогда, когда соответствующие им рёбра графа G имеют общий конец. Следовательно, рёберный граф имеет столько вершин, сколько рёбер имеет граф G.

Исследуйте следующие задачи.

1) Выясните является ли последовательность (3, 1, 1, 1) рёберной графической? Является ли эта последовательность вершинной графической? Какой вывод можно сделать на основании полученных ответов?

2) Найдите все рёберные реализации (если они существуют) для последовательности (3, 3, 3, 2, 2, 1).

3) Докажите, что в любом графе есть хотя бы два ребра, степени которых равны.

4) Докажите, что сумма степеней всех рёбер графа — чётное число, равное удвоенному числу простых цепей P₃ (не обязательно порождённых).

5) Докажите, что последовательность p = (d₁, d₂, …, d_m) целых неотрицательных чисел является рёберной графической последовательностью тогда и только тогда, когда существует рёберный граф, для которого p является вершинной графической последовательностью.

6) Найдите все рёберные графические последовательности (d₁, d₂, …, d_m), для которых d₁ = m – 1.

7) Какие из последовательностей, найденных в пункте 6, являются рёберными униграфическими?

8) Найдите все рёберные графические последовательности (d₁, d₂, …, d_m), для которых d₁ Î{1, 2, 3} и реализации которых являются связными графами.

9) Предложите свои обобщения или направления исследования в этой задаче и изучите их.

 

 

Задача 12.   Симметричные графы

Пусть G = (V, E) – связный неориентированный граф, где  V и  E  – множества вершин и ребер графа. Будем говорить, что граф  G является вершинно-симметричным, если для любых двух вершин существует взаимно-однозначное отображение , сохраняющее свойство смежности вершин (такое отображение  называется автоморфизмом графа  G ), такое, что . Граф  назовем реберно-симметричным, если для любых ребер существует автоморфизм  графа  такой, что  или . Пусть А – непустое собственное подмножество вершин графа , вершинной границей множества  А  называется множество всех вершин из дополнения , для каждой из которых найдется смежная ей вершина из множества  (напомним, что подмножество   называется собственным, если дополнение  непустое). Вершинную границу множества  А будем обозначать через . Реберной границей непустого собственного подмножества  называется множество всех ребер графа , соединяющих вершины множества  с вершинами дополнения . Реберную границу множества  А  будем обозначать через .

1. Докажите, что полный двудольный граф является реберно-симметричным. При каких соотношениях между и граф  является вершинно-симметричным?
2. Постройте пример графа, который является вершинно-симметричным, но не является реберно-симметричным.
3. При каких значенияхm и n граф прямоугольной решетки  является реберно-симметричным?
4. Пусть – вершинно-симметричный граф, тогда степени всех его вершин равны некоторому числу  (докажите это!). Докажите, что для любого вершинно-симметричного графа  со степенью вершины и любого непустого собственного подмножества вершин   справедливы неравенства , . Являются ли эти оценки точными?
5. Существуют ли постоянные такие, что для любого вершинно-симметричного графа со степенью вершины  для любого непустого собственного подмножества вершин  выполняется неравенство  ?
6. Исследуйте вопрос п. 5 для вершинно-симметричных графов с дополнительными ограничениями: a) ;b) расстояние между любыми двумя вершинами графа не превосходит ; c) граф не содержит полных двудольных подграфов ().
7. Исследуйте аналогичные вопросы для реберно-симметричных графов и реберных границ.

Задача 13.   Конфигурации точек

Конечный набор точек на плоскости будем называть конфигурацией, если никакие три точки не лежат на одной прямой. Будем говорить, что конфигурация  доминирует конфигурацию , если существует отображение , такое что отрезки  и  пересекаются, если пересекаются отрезки  и , где . Далее это будем обозначать . Если конфигурация  доминирует конфигурацию , а конфигурация  доминирует , то будем говорить, что конфигурации  и  изоморфны. Этот факт будем обозначать . Будем называть конфигурацию минимальной, если она не доминируется никакой другой, аналогично введём понятие максимальной конфигурации.

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

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

1. - Приведите пример трёх конфигураций на 6 точках, таких что  и .

- Приведите пример максимальной и минимальной конфигураций на 6 точках.

- Пусть  количество точек пересечения отрезков с концами в точках конфигура-ций. Покажите. что, если , то . Когда достигается равенство?

2. Докажите, что для любых конфигураций точек .

 * ,    ** если , то ,     *** если , то ,

Верны ли такие же утверждения для сильно изоморфных конфигураций?

- Докажите, что, если  и , то , для любых конфигураций точек .

- Покажите, что, если , то . Покажите, что обратное неверно.

3. Множество попарно изоморфных конфигураций будем называть классом изоморфных конфигураций. Аналогично введём класс сильно изоморфных конфигураций.

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

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

- Попробуйте найти как можно больше неизоморфных конфигураций для . Являются ли какие-либо из них минимальными или максимальными?

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

- Покажите, что, если , то .

- Пусть , и  – соответствующее отображение. Верно ли, что ?

- Докажите, что утверждение предыдущего пункта верно в случае .

- Покажите, что в случае ,  и  выполнено неравенство . Верно ли это утверждение, если позволить  принимать произвольные значения?

- Докажите, что, если  и , то .

5. Выпуклой конфигурацией будем называть конфигурацию K, для которой .

- Может ли выпуклая конфигурация доминироваться какой-либо другой?

- Исследуйте вопрос о доминировании выпуклой конфигурацией. Попробуйте найти условиях при которых конфигурация точек доминируется выпуклой конфигурацией.

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

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